LyndonWords

The binary Lyndon words of length $n$: words strictly less than every one of their nontrivial rotations.

OEISA001037↗SageMathLyndonWords(2, n)↗

LyndonWords(n)the binary Lyndon words of length $n$: words strictly less than every one of their nontrivial rotations

Typed signatures

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

Domain: Collections

Details

• Count is A001037, via Möbius inversion over the divisors of $n$.

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(LyndonWords(5)) = 6$

live ↗

In$\mathrm{Count}(\mathrm{LyndonWords}(5))$Out$6$

The first element in enumeration order

live ↗

In$\mathrm{LyndonWords}(5)[1]$Out${\operatorname{BinaryWord}}([0, 0, 0, 0, 1])$

About

Examples	3
Crosswalk	OEISSageMath

See also: BinaryNecklaces, KLyndonWords