login
This site is supported by donations 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. 15
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

R. Baumann, Computer-Knobelei, LOGIN, 163/164 (2010), 141-142.

Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016) #16.8.2.

N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

LINKS

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened

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

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

Row sums = T(n, 1) + ... + T(n, n) = A008965(n).

A047996 and A241926 are essentially identical to this entry.

Cf. A000010, A007318, A027750, A215251.

See A245558, A245559 for a closely related array.

Sequence in context: A114088 A208245 A274190 * A194799 A291119 A007424

Adjacent sequences:  A037303 A037304 A037305 * A037307 A037308 A037309

KEYWORD

easy,nonn,tabl,nice,changed

AUTHOR

Jens Voß, Jun 30 2001

EXTENSIONS

More terms from David Wasserman, Mar 11 2002

Comments, reference, example from Paul Weisenhorn, Dec 18 2010

Elashvili et al. references supplied by Vladimir Popov, May 17 2014

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 19 16:51 EDT 2017. Contains 292243 sequences.