|
| |
|
|
A072574
|
|
Triangle T(n,k) of number of compositions (ordered partitions) of n into exactly k distinct parts, 1<=k<=n.
|
|
19
|
|
|
|
1, 1, 0, 1, 2, 0, 1, 2, 0, 0, 1, 4, 0, 0, 0, 1, 4, 6, 0, 0, 0, 1, 6, 6, 0, 0, 0, 0, 1, 6, 12, 0, 0, 0, 0, 0, 1, 8, 18, 0, 0, 0, 0, 0, 0, 1, 8, 24, 24, 0, 0, 0, 0, 0, 0, 1, 10, 30, 24, 0, 0, 0, 0, 0, 0, 0, 1, 10, 42, 48, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12, 48, 72, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12, 60, 120, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
If terms in the compositions did not need to be distinct then the triangle would have values C(n-1,k-1), essentially A007318 offset.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n, k) = T(n-k, k)+k*T(n-k, k-1) [with T(n, 0)=1 if n=0 and 0 otherwise] = A000142(k)*A060016(n, k).
G.f.: sum(n>=0, n! * z^n * q^((n^2+n)/2) / prod(k=1..n, 1-q^k ) ), rows by powers of q, columns by powers of z; includes row 0 (drop term for n=0 for this triangle, see PARI code); setting z=1 gives g.f. for A032020. [Joerg Arndt, Oct 20 2012]
|
|
|
EXAMPLE
|
T(6,2)=4 since 6 can be written as 1+5=2+4=4+2=5+1.
Triangle starts (trailing zeros omitted for n>=10):
[ 1] 1;
[ 2] 1, 0;
[ 3] 1, 2, 0;
[ 4] 1, 2, 0, 0;
[ 5] 1, 4, 0, 0, 0;
[ 6] 1, 4, 6, 0, 0, 0;
[ 7] 1, 6, 6, 0, 0, 0, 0;
[ 8] 1, 6, 12, 0, 0, 0, 0, 0;
[ 9] 1, 8, 18, 0, 0, 0, 0, 0, 0;
[10] 1, 8, 24, 24, 0, 0, ...;
[11] 1, 10, 30, 24, 0, 0, ...;
[12] 1, 10, 42, 48, 0, 0, ...;
[13] 1, 12, 48, 72, 0, 0, ...;
[14] 1, 12, 60, 120, 0, 0, ...;
[15] 1, 14, 72, 144, 120, 0, 0, ...;
[16] 1, 14, 84, 216, 120, 0, 0, ...;
[17] 1, 16, 96, 264, 240, 0, 0, ...;
[18] 1, 16, 114, 360, 360, 0, 0, ...;
[19] 1, 18, 126, 432, 600, 0, 0, ...;
[20] 1, 18, 144, 552, 840, 0, 0, ...;
These rows (without the zeros) are shown in the Richmond/Knopfmacher reference.
Column n = 8 counts the following compositions.
(8) (1,7) (1,2,5)
(2,6) (1,3,4)
(3,5) (1,4,3)
(5,3) (1,5,2)
(6,2) (2,1,5)
(7,1) (2,5,1)
(3,1,4)
(3,4,1)
(4,1,3)
(4,3,1)
(5,1,2)
(5,2,1)
(End)
|
|
|
MATHEMATICA
|
Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n], UnsameQ@@#&], Length[#]==k&]], {n, 0, 15}, {k, 1, n}] (* Gus Wiseman, Oct 17 2022 *)
|
|
|
PROG
|
(PARI)
N=21; q='q+O('q^N);
gf=sum(n=0, N, n! * z^n * q^((n^2+n)/2) / prod(k=1, n, 1-q^k ) );
/* print triangle: */
gf -= 1; /* remove row zero */
P=Pol(gf, 'q);
{ for (n=1, N-1,
p = Pol(polcoeff(P, n), 'z);
p += 'z^(n+1); /* preserve trailing zeros */
v = Vec(polrecip(p));
v = vector(n, k, v[k]); /* trim to size n */
print(v);
); }
|
|
|
CROSSREFS
|
A008289 is the version for partitions (zeros removed).
A072575 counts strict compositions by maximum.
A113704 is the constant instead of strict version.
A216652 is a condensed version (zeros removed).
A336131 counts splittings of partitions with distinct sums.
A336139 counts strict compositions of each part of a strict composition.
Cf. A075900, A097910, A307068, A336127, A336128, A336130, A336132, A336141, A336142, A336342, A336343.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
