|
%I #110 Jan 19 2023 11:01:27
%S 1,1,1,1,1,1,1,2,1,1,1,2,2,1,1,1,3,4,3,1,1,1,3,5,5,3,1,1,1,4,7,10,7,4,
%T 1,1,1,4,10,14,14,10,4,1,1,1,5,12,22,26,22,12,5,1,1,1,5,15,30,42,42,
%U 30,15,5,1,1,1,6,19,43,66,80,66,43,19,6,1,1,1,6,22,55,99,132,132,99,55,22,6,1
%N Triangle T(n,k) read by rows: the number of compositions of n into k parts, modulo cyclic shifts.
%C Triangle obtained from A047996 by dropping the first column (k=0), and row (n=0).
%C T(n, k) = number of different ways the number n can be expressed as ordered sums of k positive integers, counting only once those ordered sums that can be transformed into each other by a cyclic permutation.
%C These might be described as cyclic compositions, or more loosely as cyclic partitions. - _N. J. A. Sloane_, Sep 05 2012
%D N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
%H Reinhard Zumkeller, <a href="/A037306/b037306.txt">Rows n = 1..125 of triangle, flattened</a>
%H Ethan Akin and Morton Davis, <a href="http://www.jstor.org/stable/2323643">Bulgarian solitaire</a>, Am. Math. Monthly 92 (4) (1985) 237-250.
%H R. Baumann, <a href="https://www.yumpu.com/de/document/read/1860388/nr-163-164">Computer-Knobelei, </a>, LOGIN, 163/164 (2010), 141-142 (in German).
%H R. Bekes, J. Pedersen and B. Shao, <a href="http://dx.doi.org/10.4169/college.math.j.43.1.025">Mad tea party cyclic partitions</a>, College Math. J., 43 (2012), 24-36.
%H A. Elashvili, M. Jibladze, <a href="http://dx.doi.org/10.1016/S0019-3577(98)80021-9">Hermite reciprocity for the regular representations of cyclic groups</a>, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006)
%H A. Elashvili, M. Jibladze, D. Pataraia, <a href="http://dx.doi.org/10.1023/A:1018727630642">Combinatorics of necklaces and "Hermite reciprocity"</a>, J. Algebraic Combin. 10 (1999), no. 2, 173-188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
%H P. Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence</a>, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
%H Arnold Knopfmacher and Neville Robbins, <a href="http://www.fq.math.ca/Papers1/48-3/Knopfmacher_Robbins.pdf">Some Properties of Cyclic Compositions</a>, Fibonacci Quart. 48 (2010), no. 3, 249-255.
%H D. M. Y. Sommerville, <a href="http://dx.doi.org/10.1112/plms/s2-7.1.263">On Certain Periodic Properties of Cyclic Compositions of Numbers</a>, Proc. London Math. Soc., s2-7, No. 1 (1909), 263-313.
%H R. Razen, J. Seberry, and K. Wehrhahn, <a href="http://dx.doi.org/10.1016/0097-3165(79)90021-9">Ordered partitions and codes generated by circulant matrices</a>, J. Combin. Theory Ser. A, 27 (1979), 333-341.
%H D. Wasserman, <a href="http://home.earthlink.net/~dwasserm/A037306.html">Proof of the symmetry</a> [Broken link]
%H D. Wasserman, <a href="/A037306/a037306.txt">Proof of the symmetry</a> [Cached copy]
%F T(n,k) = Sum_{d|gcd(n,k)} phi(d)*binomial(n/d,k/d))/n, where phi = A000010 = Euler's totient function. Also T(n,k) = A047996(n,k). - _Paul Weisenhorn_, Apr 06 2011
%e Triangle begins
%e 1;
%e 1, 1;
%e 1, 1, 1;
%e 1, 2, 1, 1;
%e 1, 2, 2, 1, 1;
%e 1, 3, 4, 3, 1, 1;
%e 1, 3, 5, 5, 3, 1, 1;
%e 1, 4, 7, 10, 7, 4, 1, 1;
%e 1, 4, 10, 14, 14, 10, 4, 1, 1;
%e 1, 5, 12, 22, 26, 22, 12, 5, 1, 1;
%e 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1;
%e T(6,3) = 4, since there are 4 essentially different ways 1+1+4, 1+2+3, 1+3+2 and 2+2+2 of expressing 6 as a sum of 3 summands (all others can be obtained by cyclically permuting the summands in one of the above sums).
%p A037306 := proc(n,k) local a,d; a := 0; for d in numtheory[divisors]( igcd(n,k)) do a := a+numtheory[phi](d)*binomial(n/d,k/d); end do: a/n; end proc:
%p seq(seq(A037306(n,k), k=1..n), n=1..20); # _R. J. Mathar_, Jun 11 2011
%t t[n_, k_] := Total[EulerPhi[#]*Binomial[n/#, k/#] & /@ Divisors[GCD[n, k]]]/n; Flatten[Table[t[n, k], {n, 13}, {k, n}]] (* _Jean-François Alcover_, Sep 08 2011, after formula *)
%t nn=15;f[list_]:=Select[list,#>0&];Map[f,Transpose[Table[Drop[CoefficientList[Series[CycleIndex[CyclicGroup[n],s]/.Table[s[i]->x^i/(1-x^i),{i,1,n}],{x,0,nn}],x],1],{n,1,nn}]]]//Grid (* _Geoffrey Critzer_, Oct 30 2012 *)
%o (Haskell)
%o a037306 n k = div (sum $ map f $ a027750_row $ gcd n k) n where
%o f d = a000010 d * a007318' (div n d) (div k d)
%o a037306_row n = map (a037306 n) [1..n]
%o a037306_tabl = map a037306_row [1..]
%o -- _Reinhard Zumkeller_, Feb 06 2014
%o (PARI) T(n, k) = sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d, k/d))/n; \\ _Michel Marcus_, Feb 10 2016
%Y A047996 and A241926 are essentially identical to this entry.
%Y Cf. A008965 (row sums), A000010, A007318, A027750, A215251, A004526 (column 2), A007997 (column 3), A008610 (column 4), A008646 (column 5), A032191 (column 6).
%Y See A245558, A245559 for a closely related array.
%Y See A052307 for compositions modulo cyclic shifts and reversal.
%K easy,nonn,tabl,nice
%O 1,8
%A _Jens Voß_, Jun 30 2001
%E More terms from _David Wasserman_, Mar 11 2002
%E Comments, reference, example from _Paul Weisenhorn_, Dec 18 2010
|
