TriStrings

Binary strings of length $n$ with no run of 3 consecutive 1s, a lazy indexed family counted by the tribonacci recurrence.

OEISA000073↗

TriStrings(n)the length-$n$ binary strings avoiding three 1s in a row.

Typed signatures

Type	Package	Applies
(integer<0..>) -> indexed_collection<binary_word>	combinatorics	always

Domain: Collections

Details

• A lazy indexed collection; the count $T(n)$ satisfies $T(n)=T(n-1)+T(n-2)+T(n-3)$ with $T(0)=1$, $T(1)=2$, $T(2)=4$ — a tribonacci-style recurrence (OEIS A000073, shifted).
• Each element is the bit string itself, as a list of 0s and 1s.
• $At$ unranks via the same combinatorial-number-system walk as the other binary-word families: at each position, the number of valid completions with a leading 0 sizes the block that sorts first.

Definition

Epsil, as the implementation runs it.

count(_n)

_tables[_n * 3 + 0 + 1]

unrank(_n, _r)

Drop(
      Fold(Function(
                     Apply(
                            (zb: integer) => Join(
                                                   [zs[1] - zb],
                                                   Drop(zs, 1),
                                                   [1],
                                                 ) if zs[1] >= zb else Join(
                                                                            [zs[1]],
                                                                            Drop(zs, 1),
                                                                            [0],
                                                                          ),
                            _tables[(_n - zj) * 3 + 0 + 1],
                          ),
                     zs,
                     zj,
                   ), [_r], Range(1, _n, 1)),
      1,
    )

rank(_n, _x)

Fold(Function(
               acc + (_tables[(_n - j) * 3 + 0 + 1] if _x[j] == 1 else 0),
               acc,
               j,
             ), 0, Range(1, _n, 1))

valid(_n, _x)

Length(_x) == _n && Fold(
                          Function(ok_j && 0 <= _x[j] && _x[j] <= 1, ok_j, j),
                          True,
                          Range(1, Length(_x), 1),
                        ) && Fold(
                                  Function(ok_w && _x[w - 0] + _x[w - 1] + _x[w -
                                                                              2] <
                                                   3, ok_w, w),
                                  True,
                                  Range(3, Length(_x), 1),
                                )

tables(_n)

Fold(
      Function(Join(
                     tw_t,
                     Fold(
                           Function(ReplaceAt(
                                               tw_row,
                                               tw_c + 1,
                                               tw_t[(tw_s - 1) * 3 + 0 + 1] +
                                               (tw_t[(tw_s - 1) * 3 +
                                                     tw_c + 1 + 1] if tw_c < 2 else 0),
                                             ), tw_row, tw_c),
                           Map(Function(0, tw_z), Range(0, 3 - 1, 1)),
                           Range(0, 3 - 1, 1),
                         ),
                   ), tw_t, tw_s),
      Fold(
            Function(ReplaceAt(tw_row, tw_c + 1, 1), tw_row, tw_c),
            Map(Function(0, tw_z), Range(0, 3 - 1, 1)),
            Range(0, 3 - 1, 1),
          ),
      Range(1, _n + 1 - 1, 1),
    )

Statistics

On BinaryWord, called as CombinatorialStat(x, "Name").

• AscentsSt000292Positions i with w(i) < w(i+1).
• BalanceSt000628The least q such that any two factors of one length differ by at most q ones.
• BalancedPrefixCountSt001355The nonempty prefixes with as many 0s as 1s.
• BaselineCrossingsSt001730The times the path, a 1 a step up and a 0 a step down, crosses the baseline.
• BorderCountSt001884The prefixes shorter than the word that are also suffixes, the empty one included.
• BorderLengthSt000295The length of the longest proper prefix that is also a suffix; 0 for none.
• CatalanFactorCountSt000876The factors in the Catalan factorization: the critical steps, and the middle Dyck word if it is not empty.
• ChangeCountSt000691The positions i where the letters i and i + 1 differ.
• CriticalStepCountSt000885The critical steps l + m in the Catalan factorization (D 0)^l D (1 D)^m.
• CyclicShiftIndexSt001436The position of the word among its distinct cyclic shifts in lexicographic order, from 0.
• DecimalRepresentationSt000289The word read as a binary numeral.
• DecimalRepresentationWithLeadingOneSt000827The word with a 1 put in front, read as a binary numeral.
• DescentWordPreimageCountSt000529The permutations whose descent word is this word.
• DistinctCubeCountSt001423The distinct nonempty words u with uuu a factor.
• DistinctFactorCountSt000294The distinct factors, the empty one included: the subword complexity.
• DistinctSquareCountSt001424The distinct nonempty words u with uu a factor.
• DistinctSubsequenceCountSt000518The distinct subsequences, the empty one included.
• EvenPalindromicPrefixHalfLengthSt001413Half the length of the longest palindromic prefix of even length.
• FirstOnePositionAfterAppendedOneSt000326The position of the first 1 once a 1 is appended to the word: one more than the leading zeros.
• FlexSt001437The product of the word's lex (its position among its distinct cyclic shifts, from 1) and its frequency.
• HammingWeightSt000288The number of ones.
• InternalInversionsSt000921The pairs i < j with w(i) > w(j) that lie in the same block of the sorted word.
• InversionsSt000293Pairs i < j with w(i) > w(j).
• InversionSumSt000347The sum of j - i over the pairs i < j with w(i) > w(j).
• LatticePathsAboveWordCountSt001365The paths of the word's length, ending anywhere, that stay weakly above the path the word gives.
• LeadingOnesCountSt000297The number of ones before the first 0.
• LongestAlternatingFactorSt000983The length of the longest factor in which every two neighboring letters differ.
• LongestCatalanFactorSemilengthSt000875The semilength of the longest Dyck word in the Catalan factorization.
• LongestConstantRunSt000982The length of the longest run of equal letters.
• LongestPalindromicFactorSt001416The length of the longest factor that reads the same backwards.
• LongestPalindromicFactorStartingWithOneSt001419The length of the longest palindromic factor that begins with a 1.
• LongestPalindromicPrefixSt001415The length of the longest prefix that reads the same backwards.
• LongestPalindromicSubsequenceSt001417The length of the longest subsequence that reads the same backwards.
• LongestRunOfOnesSt000392The length of the longest run of ones.
• LongestYamanouchiPrefixSt001371The length of the longest prefix in which no prefix has more ones than zeros.
• LyndonFactorizationLengthSt001267The factors in the Lyndon factorization.
• MajorIndexSt000290The sum of the positions i with w(i) > w(i+1).
• MinimalPeriodSt000626The least p with w(i) = w(i + p) wherever both are letters.
• ModularMajorIndexSt001485The major index modulo the length of the word.
• NonInversionSumSt000348The sum of j - i over the pairs i < j with w(i) < w(j).
• OddOneRunCountSt000389The number of maximal runs of ones of odd length.
• OddPalindromicPrefixHalfLengthSt001414The largest j such that the prefix of length 2 j + 1 is a palindrome.
• OnePositionSumSt000391The sum of the positions of the ones.
• OneRunCountSt000390The number of maximal runs of ones.
• OnesMinusZerosSt000878The number of ones less the number of zeros.
• PalindromicDecompositionCountSt000631The ways to write the word as a concatenation of palindromic factors.
• PathDepthSt000877The most zeros less ones among the prefixes.
• PrimitiveFactorCountSt001838The distinct nonempty factors that are not a power of a shorter word.
• RepetitionExponentSt000627The largest e such that the word is e copies of one word.
• ReverseComplementFactorHalfLengthSt001420Half the length of the longest factor that is its own reverse complement.
• ReverseComplementFactorHalfLengthStartingWithOneSt001421Half the length of the longest factor that is its own reverse complement and begins with a 1.
• SameEndpointPathsAboveWordCountSt001313The paths with the word's number of ones and zeros that stay weakly above the path the word gives.
• ShortestPalindromicDecompositionLengthSt000630The fewest palindromic factors the word is a concatenation of.
• StrictlyIncreasingRunsSt000393The maximal runs of strictly increasing letters.
• SymmetricBorderLengthSt000296The length of the longest prefix whose reverse is a suffix.
• SymmetryDegreeSt001524The positions i up to half the length where the letters i and n + 1 - i agree.
• UniqueFactorLengthSt000922The least length for which all factors of that length are different.
• ValleyFillingDegreeSt001721The number of times every valley 01 must be swapped for a peak 10, and a trailing 0 made a 1, to leave no zeros.
• WeakMajorIndexSt001930The sum of the positions i with w(i) >= w(i+1).

Maps

Into and out of BinaryWord, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.

From BinaryWord

• AlternatingComplementBinaryWord → BinaryWordinvolutionBijectionGraded mapInvolutionMp00158Every second letter swapped for the other, starting with the second.
• CodeCompositionBinaryWord → IntegerCompositionInjectionGraded mapMp00178The composition whose code is the word with a 1 put in front: each 1 opens a part, of 1 plus the zeros after it.
• ComplementBinaryWord → BinaryWordinvolutionBijectionGraded mapInvolutionMp00105Each letter swapped for the other: 0 for 1 and 1 for 0.
• CyclicShiftBinaryWord → BinaryWordinverseBijectionGraded mapMp00135Rotate the word one place to the left: the first letter moves to the end.
• FinsetBinaryWord → FinsetinverseThe subset of 1..m a binary word of length m marks: the positions holding 1.
• FlagZerosToZerosBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00269The word with as many zeros as this one, prepended with its reverse complement, has occurrences of 10.
• FoataInversionsToMajorBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00316The inverse of Foata's bijection on words: peel off the last letter, rotate the blocks of the rest back.
• FoataMajorToInversionsBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00096Foata's bijection on words: each letter is put on the end of the image so far, which is cut into blocks, and every block is rotated one place right.
• GrayNextBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00272The next word in the Gray code: flip the first letter when the ones are even in number, else the letter after the first one.
• GrayPreviousBinaryWord → BinaryWordinverseBijectionMp00273The previous word in the Gray code: flip the first letter when the ones are odd in number, else the letter after the first one.
• IntegerCompositionBinaryWord → IntegerCompositioninverseThe composition of m + 1 a binary word of length m cuts out.
• InverseCyclicShiftBinaryWord → BinaryWordinverseBijectionGraded mapMp00136Rotate the word one place to the right: the last letter moves to the front.
• PathRowmotionBinaryWord → BinaryWordbijectionBijectionGraded mapMp00280Rowmotion of the word as a lattice path: the path whose peaks are the original's valleys with an up step appended.
• ReverseBinaryWord → BinaryWordinvolutionBijectionGraded mapInvolutionMp00104The word read backwards.
• RowmotionBinaryWord → BinaryWordbijectionBijectionGraded mapMp00278Rowmotion of the word as an order ideal of a product of two chains: the stretches between valleys reversed, each valley written 10.
• RunCompositionBinaryWord → IntegerCompositionsurjectionSurjectionGraded mapMp00097The lengths of the maximal runs of equal letters, left to right.
• RunSortBinaryWord → BinaryWordidempotentIdempotentGraded mapMp00224The word with its weakly increasing runs sorted lexicographically.
• StandardPermutationBinaryWord → PermutationGraded mapMp00336The permutation ranking the letters of the word, equal letters from left to right.
• TwistBinaryWord → BinaryWordinvolutionBijectionGraded mapInvolutionMp00200The first letter swapped for the other.
• ValleysToPeaksBinaryWord → BinaryWordGraded mapMp00234Every valley 01 swapped for a peak 10, and a trailing 0 made a 1.
• ZerosToFlagZerosBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00268The word whose reverse complement, prepended, has as many occurrences of 10 as this has zeros.

To BinaryWord

• BinaryWordDyckPath → BinaryWordInjectionGraded mapMp00093The Dyck word as a binary word: 1 for an up step, 0 for a down step.
• BinaryWordIntegerPartition → BinaryWordInjectionMp00095The shape's boundary read from the first row down: 1 for a step down, 0 for a step left.
• BinaryWordFinset → BinaryWordinverseA subset of 1..n as its characteristic word: letter i is 1 when i is a member.
• CodeWordIntegerComposition → BinaryWordInjectionGraded mapMp00094The word that writes each part i as a one followed by i - 1 zeros.
• ConnectivityWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00114Letter i is 1 when the first i entries are all smaller than the rest: the connectivity set as a binary word.
• CutWordIntegerComposition → BinaryWordinverseA composition of n as the binary word of length n - 1 marking where it is cut.
• DescentBottomWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00131Letter v is 1 when value v is a descent bottom: some larger value immediately precedes it.
• DescentTopWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00130Letter v - 1 is 1 when value v is a descent top: some smaller value immediately follows it.
• DescentWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00109Letter i is 1 when the word falls between positions i and i + 1: the descent set as a binary word.
• OddPartsWordIntegerPartition → BinaryWordSurjectionMp00317The binary word marking which parts are odd, the parts taken largest first.
• SignWordSignedPermutation → BinaryWordsurjectionSurjectionGraded mapMp00267The signs as a binary word: letter i is 1 when entry i is negative.
• TableauDescentWordStandardTableau → BinaryWordsurjectionSurjectionGraded mapMp00134Letter i is 1 when entry i + 1 sits in a lower row than entry i.

2 more in FindStat, not implemented here

• Mp00261BinaryWord → BinaryWordGraded mapBurrows-Wheeler
• Mp00262BinaryWord → Posetsposet of factors

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

$Count(TriStrings(6)) = 44$: binary strings of length 6 with no run of 3 consecutive 1s

live ↗

In$\mathrm{Count}(\mathrm{TriStrings}(6))$Out$44$

About

Examples	2
Crosswalk	OEIS

See also: PrimitiveBinaryStrings, Count, At