|
%I #44 Oct 25 2021 14:33:42
%S 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,
%T 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,
%U 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
%N The number of periods in a reshuffling operation for compositions of n.
%C 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.
%C 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.
%C a(n) with T(k-1) < n <= T(k) is the number of periods with length k for 1 < k.
%C If k is prime then all periods of the numbers T(k-1) < n < T(k) have length k.
%C If k is not prime, then the length of the periods is k or a divisor of k.
%C n = T(k-1) + j has binomial(k,j) partitions in its periods with 0 < j < k.
%C 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).
%C 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
%C 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
%D R. Baumann, Computer-Knobelei, LOGIN (1987), 483-486 (in German).
%H Ethan Akin, Morton Davis, <a href="http://www.jstor.org/stable/2323643">Bulgarian solitaire</a>, Am. Math. Monthly 92 (4) (1985) 237-250
%H J. Brandt, <a href="http://dx.doi.org/10.1090/S0002-9939-1982-0656129-5">Cycles of partitions</a>, Proc. Am. Math. Soc. 85 (3) (1982) 483-486
%F a(T(k))=0 with k > 1. a(1)=1.
%F If k is a prime number and n = T(k-1) + j with 0 < j < k, then a(n) = binomial(k,j)/k.
%F 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).
%F 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
%F a(n) = c(n)-sum{a(T(k/q-1)+j))} summed over all 1 < q|gcd(k,j).
%e For k=5: T(4)=10 < n < T(5)=15 and all periods are of length 5:
%e 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)];
%e 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)];
%e 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)];
%e 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)].
%e 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.
%e (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).
%e Triangular view, with a(n) distributed in rows k=1,2,3.. according to T(k-1)< n <= T(k):
%e 1; k=1, n=1
%e 1, 0; k=2, n=2..3
%e 1, 1, 0; k=3, n=4..6
%e 1, 1, 1, 0; k=4, n=7..10
%e 1, 2, 2, 1, 0; k=5, n=11..15
%e 1, 2, 3, 2, 1, 0; k=6, n=16..21
%e 1, 3, 5, 5, 3, 1, 0;
%e 1, 3, 7, 8, 7, 3, 1, 0;
%e 1, 4, 9, 14, 14, 9, 4, 1, 0;
%e 1, 4, 12, 20, 25, 20, 12, 4, 1, 0;
%e 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0;
%e 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0;
%e 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0;
%e 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1, 0;
%p A000217 := proc(n) n*(n+1)/2 ; end proc:
%p 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:
%p seq(A185700(n),n=1..80) ; # _R. J. Mathar_, Jun 11 2011
%t LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
%t Table[Length@Select[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]===k&],LyndonQ],{n,10},{k,n}] (* _Gus Wiseman_, Dec 19 2017 *)
%Y Cf. A000740, A001037, A008965, A051168, A059966, A060223, A245558, A294859, A296302, A296373, A092964, A245559, A245558.
%K nonn,tabl
%O 1,12
%A _Paul Weisenhorn_, Feb 10 2011
%E I have added a comment and deleted a Jun 11 2011 question from _R. J. Mathar_. - _Paul Weisenhorn_, Jan 08 2017
|
