|
| |
|
|
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
|
|
|
|
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:
|
|
|
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, A092964, A245559, A245558.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
