login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A185700 The number of periods in a reshuffling operation for compositions of n. 21
1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 7, 8, 7, 3, 1, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,12

COMMENTS

n has 2^(n-1) compositions. For each composition remove the largest part and redistribute it by adding 1 to subsequently smaller parts (creating 1's if needed) to get a new composition of n. (This is reversing the operation in A188160.) Repeat. Eventually this sequence of compositions will cycle. We are interested in the length of the period.

Let the indices k and j be uniquely associated with n using the triangular numbers T=A000217: T(k-1) < n <= T(k) and n = T(k-1) + j with 0 < j <= k.

a(n) with T(k-1) < n <= T(k) is the number of periods with length k for 1 < k.

If k is prime then all periods of the numbers T(k-1) < n < T(k) have length k.

If k is not prime, then the length of the periods is k or a divisor of k.

n = T(k-1) + j has binomial(k,j) partitions in its periods with 0 < j < k.

n = T(k-1) + j has c(n) = Sum_{d|gcd(k,j)} (phi(d)*binomial(k/d,j/d))/k periods of length k or a divisor of k as tabulated in A047996; phi is Euler's totient function. If k is prime then a(n)=c(n) gives the number of periods with length k. If k is not prime, subtract all periods of length < k from c(n).

Obtained from A092964 by adding an initial column of 1's and appending a 1 and 0 to each row. Obtained from A051168 by reading the array downwards along antidiagonals. - R. J. Mathar, Apr 14 2011

As a regular triangle, T(n,k) is the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and length k. Row sums are A059966. - Gus Wiseman, Dec 19 2017

REFERENCES

R. Baumann, Computer-Knobelei, LOGIN (1987), 483-486 (in German).

LINKS

Table of n, a(n) for n=1..104.

Ethan Akin, Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250

J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982) 483-486

FORMULA

a(T(k))=0 with k > 1. a(1)=1.

If k is a prime number and n = T(k-1) + j with 0 < j < k, then a(n) = binomial(k,j)/k.

If k is not prime, subtract the sum of partitions in all periods of n with length < k from the term binomial(k,j). The difference divided by k gives the number of periods for n=T(k-1)+j: a(n)=( binomial(k,j) -sum {a(T(k/q-1)+j/q) *k/q })/k summed over all 1 < q|gcd(k,j).

If k is not prime, subtract the sum of all periods of n with length < k from the term c(n) = sum{ phi(d)*binomial(k/d,j/d) }/k summed over d|gcd(k,j), namely

  a(n) = c(n)-sum{a(T(k/q-1)+j))} summed over all 1 < q|gcd(k,j).

EXAMPLE

For k=5: T(4)=10 < n < T(5)=15 and all periods are of length 5:

a(11)=1 period: [(4+3+2+1+1), (4+3+2+2), (4+3+3+1), (4+4+2+1), (5+3+2+1)];

a(12)=2 periods: [(4+3+2+2+1), (4+3+3+2), (4+4+3+1), (5+4+2+1), (5+3+2+1+1)]; and [(4+4+2+2), (5+3+3+1), (4+4+2+1+1), (5+3+2+2), (4+3+3+1+1)];

a(13)=2 periods: [(4+4+2+2+1), (5+3+3+2), (4+4+3+1+1), (5+4+2+2), (5+3+3+1+1)]; and [(5+4+3+1), (5+4+2+1+1), (5+3+2+2+1), (4+3+3+2+1), (4+4+3+2)];

a(14)=1 period: [(5+4+3+2), (5+4+3+1+1), (5+4+2+2+1), (5+3+3+2+1), (4+4+3+2+1)].

For k=16; j=8; n=T(k-1)+j=128; 1<q|(16,8) --> {2,4,8} a(128) = c(128) - a(T(7)+4) - a(T(3)+2) - a(T(1)+1) =  810 - 8 - 1 - 1 = 800.

  (binomial(16,8)-8*a(T(7)+4)-4*a(T(3)+2)-2*a(T(1)+1))/16 = (12870-64-4-2)/16 = 800 = a(128).

Triangular view, with a(n) distributed in rows k=1,2,3.. according to T(k-1)< n <= T(k):

1;     k=1, n=1

1, 0;    k=2, n=2..3

1, 1,  0;    k=3, n=4..6

1, 1,  1,  0;    k=4, n=7..10

1, 2,  2,  1,   0;    k=5, n=11..15

1, 2,  3,  2,   1,   0;    k=6, n=16..21

1, 3,  5,  5,   3,   1,   0;

1, 3,  7,  8,   7,   3,   1,   0;

1, 4,  9, 14,  14,   9,   4,   1,   0;

1, 4, 12, 20,  25,  20,  12,   4,   1,  0;

1, 5, 15, 30,  42,  42,  30,  15,   5,  1,  0;

1, 5, 18, 40,  66,  75,  66,  40,  18,  5,  1, 0;

1, 6, 22, 55,  99, 132, 132,  99,  55, 22,  6, 1, 0;

1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1, 0;

MAPLE

A000217 := proc(n) n*(n+1)/2 ; end proc:

A185700 := proc(n) local k, j, a, q; k := ceil( (-1+sqrt(1+8*n))/2 ) ; j := n-A000217(k-1) ; if n = 1 then return 1; elif j = k then return 0 ; end if; a := binomial(k, j) ; if not isprime(k) then for q in numtheory[divisors]( igcd(k, j)) minus {1} do a := a- procname(j/q+A000217(k/q-1))*k/q ; end do: end if; a/k ; end proc:

seq(A185700(n), n=1..80) ; # R. J. Mathar, Jun 11 2011

MATHEMATICA

LyndonQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And]&&Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];

Table[Length@Select[Join@@Permutations/@Select[IntegerPartitions[n], Length[#]===k&], LyndonQ], {n, 10}, {k, n}] (* Gus Wiseman, Dec 19 2017 *)

CROSSREFS

Cf. A000740, A001037, A008965, A051168, A059966, A060223, A245558, A294859, A296302, A296373.

Sequence in context: A116403 A123149 A185158 * A061926 A180835 A053188

Adjacent sequences:  A185697 A185698 A185699 * A185701 A185702 A185703

KEYWORD

nonn,tabl

AUTHOR

Paul Weisenhorn, Feb 10 2011

EXTENSIONS

I have added a comment and deleted a Jun 11 2011 question from R. J. Mathar. - Paul Weisenhorn, Jan 08 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 9 10:38 EDT 2020. Contains 336323 sequences. (Running on oeis4.)