|
| |
|
|
A037306
|
|
Triangle T(n,k) read by rows: the number of compositions of n into k parts, modulo cyclic shifts.
|
|
6
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,8
|
|
|
COMMENTS
| 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.
|
|
|
REFERENCES
| R. Baumann, Computer-Knobelei, LOGIN, 163/164 (2010), 141-142. - Paul Weisenhorn, Apr 06 2011
|
|
|
LINKS
| D. Wasserman, Proof of the symmetry
|
|
|
FORMULA
| T(n,k) = sum_{d|gcd(n,k)} phi(d) *binomial(n/d,k/d)) /n = A047996(n,k) with phi=A000010 Euler's totient. - 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 the 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, 1, 13}, {k, 1, n}]] (* From Jean-François Alcover, Sep 08 2011, after formula *)
|
|
|
CROSSREFS
| T(n, 1) + ... + T(n, n) = A008965(n).
Sequence in context: A114087 A008284 A114088 * A194799 A007424 A085424
Adjacent sequences: A037303 A037304 A037305 * A037307 A037308 A037309
|
|
|
KEYWORD
| easy,nonn,tabl,nice
|
|
|
AUTHOR
| Jens Voss (jens.voss(AT)poet.de), Jun 30 2001
|
|
|
EXTENSIONS
| More terms from David Wasserman (wasserma(AT)spawar.navy.mil), Mar 11 2002
Comments, reference, example from Paul Weisenhorn, Dec 18 2010
|
| |
|
|
