- FindStat

Identifier

St001916: Binary words ⟶ ℤ

Values

0 => 0

1 => 0

00 => 0

01 => 0

10 => 0

11 => 2

000 => 2

001 => 2

010 => 2

011 => 4

100 => 2

101 => 4

110 => 4

111 => 10

0000 => 10

0001 => 11

0010 => 11

0011 => 11

0100 => 11

0101 => 5

0110 => 11

0111 => 26

1000 => 11

1001 => 11

1010 => 5

1011 => 26

1100 => 11

1101 => 26

1110 => 26

1111 => 41

00000 => 41

00001 => 51

00010 => 51

00011 => 40

00100 => 51

00101 => 27

00110 => 40

00111 => 62

01000 => 51

01001 => 27

01010 => 27

01011 => 29

01100 => 40

01101 => 29

01110 => 62

01111 => 130

10000 => 51

10001 => 40

10010 => 27

10011 => 62

10100 => 27

10101 => 29

10110 => 29

10111 => 130

11000 => 40

11001 => 62

11010 => 29

11011 => 130

11100 => 62

11101 => 130

11110 => 130

11111 => 175

000000 => 175

000001 => 225

000010 => 225

000011 => 179

000100 => 225

000101 => 81

000110 => 179

000111 => 208

001000 => 225

001001 => 22

001010 => 81

001011 => 74

001100 => 179

001101 => 59

001110 => 208

001111 => 316

010000 => 225

010001 => 81

010010 => 22

010011 => 59

010100 => 81

010101 => 24

010110 => 74

010111 => 127

011000 => 179

011001 => 74

011010 => 59

011011 => 32

011100 => 208

011101 => 127

011110 => 316

011111 => 621

100000 => 225

100001 => 179

100010 => 81

100011 => 208

100100 => 22

100101 => 74

100110 => 59

>>> Load all 511 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The number of transient elements in the orbit of Bulgarian solitaire corresponding to a necklace.
A move in Bulgarian solitaire consists of removing the first column of the Ferrers diagram and inserting it as a new row.
The connected components of the corresponding discrete dynamical system are indexed by necklaces in a natural way. The binary words corresponding to a necklace index the recurrent elements in a component, the remaining elements are called transient.

References

[1] Brandt, Jør. Cycles of partitions MathSciNet:0656129
[2] Society, pages 483–486, 1982

Code

def move(la):
    return Partition(sorted([p-1 for p in la] + [len(la)], reverse=True))

def necklace_to_partition(w):
    m = len(w)
    la = [m - i + b for i, b in enumerate(w, 1)]
    return Partition(la)

def orbit(la):
    la = Partition(la)
    n = la.size()
    B = DiscreteDynamicalSystem(Partitions(n), move)
    return B.orbit(la)

@cached_function
def components(n):
    B = DiscreteDynamicalSystem(Partitions(n), move)
    C = {frozenset(c): set(c) for c in B.cycles()}
    E = set(B).difference(*C.values())
    while E:
        e = E.pop()
        if not any(e in c for c in C.values()):
            o, k = B.orbit(e, True)
            c = frozenset(o[k:])
            r = o[:k]
            C[c].update(r)
            E.difference_update(r)
    return C

def component(la):
    la = Partition(la)
    n = la.size()
    B = DiscreteDynamicalSystem(Partitions(n), move)
    o, k = B.orbit(la, preperiod=True)
    return components(n)[frozenset(o[k:])]

def statistic(w):
    return len(component(necklace_to_partition(w))) - len(w.conjugates())

Created

Aug 16, 2023 at 09:15 by Martin Rubey

Updated

Aug 16, 2023 at 09:15 by Martin Rubey