|
|
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
|
|
|
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:
|
|
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..]
(PARI) T(n, k) = sumdiv(gcd(n, k), d, eulerphi(d)*binomial(n/d, k/d))/n; \\ Michel Marcus, Feb 10 2016
|
|
CROSSREFS
|
See A052307 for compositions modulo cyclic shifts and reversal.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|