|
|
A371417
|
|
Triangle read by rows: T(n,k) is the number of complete compositions of n with k parts.
|
|
0
|
|
|
1, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 1, 0, 0, 0, 3, 4, 1, 0, 0, 0, 6, 6, 5, 1, 0, 0, 0, 0, 16, 10, 6, 1, 0, 0, 0, 0, 12, 30, 15, 7, 1, 0, 0, 0, 0, 12, 35, 50, 21, 8, 1, 0, 0, 0, 0, 24, 50, 75, 77, 28, 9, 1, 0, 0, 0, 0, 0, 90, 126, 140, 112, 36, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
A composition (ordered partition) is complete if the set of parts both covers an interval (is gap-free) and contains 1.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = k!*[z^n*t^k] Sum_{i>0} z^(i*(i+1)/2)*t^i * Product_{j=1..i} Sum_{k>=0} (z^(j*k)*t^k)/(k+1)!.
|
|
EXAMPLE
|
The triangle begins:
k=0 1 2 3 4 5 6 7 8 9 10
n=0: 1;
n=1: 0, 1;
n=2: 0, 0, 1;
n=3: 0, 0, 2, 1;
n=4: 0, 0, 0, 3, 1;
n=5: 0, 0, 0, 3, 4, 1;
n=6: 0, 0, 0, 6, 6, 5, 1;
n=7: 0, 0, 0, 0, 16, 10, 6, 1;
n=8: 0, 0, 0, 0, 12, 30, 15, 7, 1;
n=9: 0, 0, 0, 0, 12, 35, 50, 21, 8, 1;
n=10: 0, 0, 0, 0, 24, 50, 75, 77, 28, 9, 1;
...
For n = 5 there are a total of 8 complete compositions:
T(5,3) = 3: (221), (212), (122)
T(5,4) = 4: (2111), (1211), (1121), (1112)
T(5,5) = 1: (11111)
|
|
MAPLE
|
b:= proc(n, i, t) option remember; `if`(n=0,
`if`(i=0, t!, 0), `if`(i<1 or n<i, 0, add(
expand(x^j*b(n-i*j, i-1, t+j)/j!), j=1..n/i)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(add(b(n, i, 0), i=0..n)):
|
|
PROG
|
(PARI)
G(N)={ my(z='z+O('z^N)); Vec(sum(i=1, N, z^(i*(i+1)/2)*t^i*prod(j=1, i, sum(k=0, N, (z^(j*k)*t^k)/(k+1)!))))}
my(v=G(10)); for(n=0, #v, if(n<1, print([1]), my(p=v[n], r=vector(n+1)); for(k=0, n, r[k+1] =k!*polcoeff(p, k)); print(r)))
|
|
CROSSREFS
|
A107428 counts gap-free compositions.
A251729 counts gap-free but not complete compositions.
Cf. A107429 (row sums give complete compositions of n), A000670 (column sums), A152947 (number of nonzero terms per column).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|