***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St001916 ----------------------------------------------------------------------------- Collection: Binary words ----------------------------------------------------------------------------- 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] (service unreachable) [[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()) ----------------------------------------------------------------------------- Statistic 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 100111 => 316 101000 => 81 101001 => 59 101010 => 24 101011 => 127 101100 => 74 101101 => 32 101110 => 127 101111 => 621 110000 => 179 110001 => 208 110010 => 74 110011 => 316 110100 => 59 110101 => 127 110110 => 32 110111 => 621 111000 => 208 111001 => 316 111010 => 127 111011 => 621 111100 => 316 111101 => 621 111110 => 621 111111 => 791 0000000 => 791 0000001 => 995 0000010 => 995 0000011 => 804 0000100 => 995 0000101 => 287 0000110 => 804 0000111 => 770 0001000 => 995 0001001 => 143 0001010 => 287 0001011 => 329 0001100 => 804 0001101 => 182 0001110 => 770 0001111 => 1107 0010000 => 995 0010001 => 143 0010010 => 143 0010011 => 118 0010100 => 287 0010101 => 141 0010110 => 329 0010111 => 279 0011000 => 804 0011001 => 118 0011010 => 182 0011011 => 138 0011100 => 770 0011101 => 248 0011110 => 1107 0011111 => 1630 0100000 => 995 0100001 => 287 0100010 => 143 0100011 => 182 0100100 => 143 0100101 => 141 0100110 => 118 0100111 => 248 0101000 => 287 0101001 => 141 0101010 => 141 0101011 => 151 0101100 => 329 0101101 => 151 0101110 => 279 0101111 => 537 0110000 => 804 0110001 => 329 0110010 => 118 0110011 => 138 0110100 => 182 0110101 => 151 0110110 => 138 0110111 => 248 0111000 => 770 0111001 => 279 0111010 => 248 0111011 => 248 0111100 => 1107 0111101 => 537 0111110 => 1630 0111111 => 3003 1000000 => 995 1000001 => 804 1000010 => 287 1000011 => 770 1000100 => 143 1000101 => 329 1000110 => 182 1000111 => 1107 1001000 => 143 1001001 => 118 1001010 => 141 1001011 => 279 1001100 => 118 1001101 => 138 1001110 => 248 1001111 => 1630 1010000 => 287 1010001 => 182 1010010 => 141 1010011 => 248 1010100 => 141 1010101 => 151 1010110 => 151 1010111 => 537 1011000 => 329 1011001 => 138 1011010 => 151 1011011 => 248 1011100 => 279 1011101 => 248 1011110 => 537 1011111 => 3003 1100000 => 804 1100001 => 770 1100010 => 329 1100011 => 1107 1100100 => 118 1100101 => 279 1100110 => 138 1100111 => 1630 1101000 => 182 1101001 => 248 1101010 => 151 1101011 => 537 1101100 => 138 1101101 => 248 1101110 => 248 1101111 => 3003 1110000 => 770 1110001 => 1107 1110010 => 279 1110011 => 1630 1110100 => 248 1110101 => 537 1110110 => 248 1110111 => 3003 1111000 => 1107 1111001 => 1630 1111010 => 537 1111011 => 3003 1111100 => 1630 1111101 => 3003 1111110 => 3003 1111111 => 3717 00000000 => 3717 00000001 => 4557 00000010 => 4557 00000011 => 3719 00000100 => 4557 00000101 => 1144 00000110 => 3719 00000111 => 3872 00001000 => 4557 00001001 => 492 00001010 => 1144 00001011 => 807 00001100 => 3719 00001101 => 739 00001110 => 3872 00001111 => 4412 00010000 => 4557 00010001 => 221 00010010 => 492 00010011 => 367 00010100 => 1144 00010101 => 412 00010110 => 807 00010111 => 1068 00011000 => 3719 00011001 => 352 00011010 => 739 00011011 => 406 00011100 => 3872 00011101 => 794 00011110 => 4412 00011111 => 5964 00100000 => 4557 00100001 => 492 00100010 => 221 00100011 => 352 00100100 => 492 00100101 => 237 00100110 => 367 00100111 => 462 00101000 => 1144 00101001 => 237 00101010 => 412 00101011 => 301 00101100 => 807 00101101 => 308 00101110 => 1068 00101111 => 1074 00110000 => 3719 00110001 => 367 00110010 => 352 00110011 => 146 00110100 => 739 00110101 => 287 00110110 => 406 00110111 => 517 00111000 => 3872 00111001 => 462 00111010 => 794 00111011 => 516 00111100 => 4412 00111101 => 1150 00111110 => 5964 00111111 => 8455 01000000 => 4557 01000001 => 1144 01000010 => 492 01000011 => 739 01000100 => 221 01000101 => 412 01000110 => 352 01000111 => 794 01001000 => 492 01001001 => 237 01001010 => 237 01001011 => 308 01001100 => 367 01001101 => 287 01001110 => 462 01001111 => 1150 01010000 => 1144 01010001 => 412 01010010 => 237 01010011 => 287 01010100 => 412 01010101 => 95 01010110 => 301 01010111 => 585 01011000 => 807 01011001 => 301 01011010 => 308 01011011 => 281 01011100 => 1068 01011101 => 585 01011110 => 1074 01011111 => 2406 01100000 => 3719 01100001 => 807 01100010 => 367 01100011 => 406 01100100 => 352 01100101 => 301 01100110 => 146 01100111 => 516 01101000 => 739 01101001 => 308 01101010 => 287 01101011 => 281 01101100 => 406 01101101 => 281 01101110 => 517 01101111 => 975 01110000 => 3872 01110001 => 1068 01110010 => 462 01110011 => 517 01110100 => 794 01110101 => 585 01110110 => 516 01110111 => 446 01111000 => 4412 01111001 => 1074 01111010 => 1150 01111011 => 975 01111100 => 5964 01111101 => 2406 01111110 => 8455 01111111 => 14875 10000000 => 4557 10000001 => 3719 10000010 => 1144 10000011 => 3872 10000100 => 492 10000101 => 807 10000110 => 739 10000111 => 4412 10001000 => 221 10001001 => 367 10001010 => 412 10001011 => 1068 10001100 => 352 10001101 => 406 10001110 => 794 10001111 => 5964 10010000 => 492 10010001 => 352 10010010 => 237 10010011 => 462 10010100 => 237 10010101 => 301 10010110 => 308 10010111 => 1074 10011000 => 367 10011001 => 146 10011010 => 287 10011011 => 517 10011100 => 462 10011101 => 516 10011110 => 1150 10011111 => 8455 10100000 => 1144 10100001 => 739 10100010 => 412 10100011 => 794 10100100 => 237 10100101 => 308 10100110 => 287 10100111 => 1150 10101000 => 412 10101001 => 287 10101010 => 95 10101011 => 585 10101100 => 301 10101101 => 281 10101110 => 585 10101111 => 2406 10110000 => 807 10110001 => 406 10110010 => 301 10110011 => 516 10110100 => 308 10110101 => 281 10110110 => 281 10110111 => 975 10111000 => 1068 10111001 => 517 10111010 => 585 10111011 => 446 10111100 => 1074 10111101 => 975 10111110 => 2406 10111111 => 14875 11000000 => 3719 11000001 => 3872 11000010 => 807 11000011 => 4412 11000100 => 367 11000101 => 1068 11000110 => 406 11000111 => 5964 11001000 => 352 11001001 => 462 11001010 => 301 11001011 => 1074 11001100 => 146 11001101 => 517 11001110 => 516 11001111 => 8455 11010000 => 739 11010001 => 794 11010010 => 308 11010011 => 1150 11010100 => 287 11010101 => 585 11010110 => 281 11010111 => 2406 11011000 => 406 11011001 => 516 11011010 => 281 11011011 => 975 11011100 => 517 11011101 => 446 11011110 => 975 11011111 => 14875 11100000 => 3872 11100001 => 4412 11100010 => 1068 11100011 => 5964 11100100 => 462 11100101 => 1074 11100110 => 517 11100111 => 8455 11101000 => 794 11101001 => 1150 11101010 => 585 11101011 => 2406 11101100 => 516 11101101 => 975 11101110 => 446 11101111 => 14875 11110000 => 4412 11110001 => 5964 11110010 => 1074 11110011 => 8455 11110100 => 1150 11110101 => 2406 11110110 => 975 11110111 => 14875 11111000 => 5964 11111001 => 8455 11111010 => 2406 11111011 => 14875 11111100 => 8455 11111101 => 14875 11111110 => 14875 11111111 => 17976 000000000 => 17976 ----------------------------------------------------------------------------- Created: Aug 16, 2023 at 09:15 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Aug 16, 2023 at 09:15 by Martin Rubey