login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A037306 Triangle T(n,k) read by rows: the number of compositions of n into k parts, modulo cyclic shifts. 18
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, 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, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,8
COMMENTS
Triangle obtained from A047996 by dropping the first column (k=0), and row (n=0).
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.
These might be described as cyclic compositions, or more loosely as cyclic partitions. - N. J. A. Sloane, Sep 05 2012
REFERENCES
N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
LINKS
Ethan Akin and Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250.
R. Baumann, Computer-Knobelei, , LOGIN, 163/164 (2010), 141-142 (in German).
R. Bekes, J. Pedersen and B. Shao, Mad tea party cyclic partitions, College Math. J., 43 (2012), 24-36.
A. Elashvili, M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006)
A. Elashvili, M. Jibladze, D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173-188. MR1719140 (2000j:05009). See p. 174. - N. J. A. Sloane, Aug 06 2014
P. Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
Arnold Knopfmacher and Neville Robbins, Some Properties of Cyclic Compositions, Fibonacci Quart. 48 (2010), no. 3, 249-255.
D. M. Y. Sommerville, On Certain Periodic Properties of Cyclic Compositions of Numbers, Proc. London Math. Soc., s2-7, No. 1 (1909), 263-313.
R. Razen, J. Seberry, and K. Wehrhahn, Ordered partitions and codes generated by circulant matrices, J. Combin. Theory Ser. A, 27 (1979), 333-341.
D. Wasserman, Proof of the symmetry [Broken link]
D. Wasserman, Proof of the symmetry [Cached copy]
FORMULA
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
EXAMPLE
Triangle begins
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, 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, 30, 15, 5, 1, 1;
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).
MAPLE
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:
seq(seq(A037306(n, k), k=1..n), n=1..20); # R. J. Mathar, Jun 11 2011
MATHEMATICA
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 *)
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 *)
PROG
(Haskell)
a037306 n k = div (sum $ map f $ a027750_row $ gcd n k) n where
f d = a000010 d * a007318' (div n d) (div k d)
a037306_row n = map (a037306 n) [1..n]
a037306_tabl = map a037306_row [1..]
-- Reinhard Zumkeller, Feb 06 2014
(PARI) T(n, k) = sumdiv(gcd(n, k), d, eulerphi(d)*binomial(n/d, k/d))/n; \\ Michel Marcus, Feb 10 2016
CROSSREFS
A047996 and A241926 are essentially identical to this entry.
Cf. A008965 (row sums), A000010, A007318, A027750, A215251, A004526 (column 2), A007997 (column 3), A008610 (column 4), A008646 (column 5), A032191 (column 6).
See A245558, A245559 for a closely related array.
See A052307 for compositions modulo cyclic shifts and reversal.
Sequence in context: A309049 A274190 A322596 * A194799 A291119 A366309
KEYWORD
easy,nonn,tabl,nice
AUTHOR
Jens Voß, Jun 30 2001
EXTENSIONS
More terms from David Wasserman, Mar 11 2002
Comments, reference, example from Paul Weisenhorn, Dec 18 2010
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)