BinaryBracelets
Binary strings of length up to rotation AND reflection — the dihedral-group orbits of , a lazy indexed family.
BinaryBracelets(n)the bracelets of black-or-white beads on a necklace that can flip.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<binary_word> | combinatorics | always |
Details
- A lazy indexed collection; the count follows Burnside's lemma over the dihedral group — a rotation sum shared with binary necklaces, plus a reflection sum that splits on the parity of (OEIS A000029). See Totient, used in the rotation sum.
- Each element is the lexicographically-least word in its rotation-and-reflection orbit; that canonical word's 1-count is an invariant of the whole orbit.
- unranks over these canonical words in ascending lexicographic order.
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.
Enumeration
Examples
1 more kept as data, checked against the oracles See also: KBracelets, Totient, Count, At