login
A156041
Array A(n,k) (n>=1, k>=1) read by antidiagonals, where A(n,k) is the number of compositions (ordered partitions) of n into exactly k parts, some of which may be zero, with the first part greater than or equal to all the rest.
8
1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 3, 4, 4, 1, 1, 3, 6, 7, 5, 1, 1, 4, 8, 11, 11, 6, 1, 1, 4, 11, 17, 19, 16, 7, 1, 1, 5, 13, 26, 32, 31, 22, 8, 1, 1, 5, 17, 35, 54, 56, 48, 29, 9, 1, 1, 6, 20, 48, 82, 102, 93, 71, 37, 10, 1, 1, 6, 24, 63, 120, 172, 180, 148, 101, 46, 11, 1, 1, 7, 28, 81, 170
OFFSET
1,5
COMMENTS
A(n,k) is of course smaller than the number of ordered partitions of n into k parts and at least the number of partitions into k parts in descending order.
The sums of the antidiagonals give A079500 - 1. - N. J. A. Sloane, Feb 26 2011
For an alternative definition of essentially the same sequence, as a triangle, and which avoids the use of parts of size zero, see A184957. - N. J. A. Sloane, Feb 27 2011
LINKS
FORMULA
A(n,k)= [[x^n]]Sum_{i=0..n} x^i*((1 - x^(i+1))/(1-x))^(k-1). - Geoffrey Critzer, Jul 15 2013
EXAMPLE
The array A(n,k) begins:
1 1 1 1 1 1 1 1 1 ...
1 2 3 4 5 6 7 8 9 ...
1 2 4 7 11 16 22 29 ...
1 3 6 11 19 31 48 ...
1 3 8 17 32 56 ...
1 4 11 26 54 ...
1 4 13 35 ...
...
The antidiagonals are:
1,
1, 1,
1, 2, 1,
1, 2, 3, 1,
1, 3, 4, 4, 1,
1, 3, 6, 7, 5, 1,
1, 4, 8, 11, 11, 6, 1,
1, 4, 11, 17, 19, 16, 7, 1,
1, 5, 13, 26, 32, 31, 22, 8, 1,
...
A(3,5) = 11 and the 11 partition of 3 into 5 parts of this type are: (3,0,0,0,0), (2,1,0,0,0), (2,0,1,0,0), (2,0,0,1,0), (2,0,0,0,1), (1,1,1,0,0), (1,1,0,1,0), (1,1,0,0,1), (1,0,1,1,0), (1,0,1,0,1), (1,0,0,1,1).
MAPLE
b:= proc(n, i, m) option remember;
if n<0 then 0
elif n=0 then 1
elif i=1 then `if`(n<=m, 1, 0)
else add(b(n-k, i-1, m), k=0..m)
fi
end:
A:= (n, k)-> add(b(n-m, k-1, m), m=ceil(n/k)..n):
seq(seq(A(d-k, k), k=1..d-1), d=1..14); # Alois P. Heinz, Jun 14 2009
MATHEMATICA
(* Returns rectangular array *) nn=10; Table[Table[Coefficient[Series[Sum[x^i((1-x^(i+1))/(1-x))^(k-1), {i, 0, n}], {x, 0, nn}], x^n], {k, 1, nn}], {n, 1, nn}]//Grid (* Geoffrey Critzer, Jul 15 2013 *)
CROSSREFS
A156039 gives A(n,4) and A156040 gives A(n,3). A156042 is the part on or below the main diagonal. A(n,2) is A008619. A(2,n) is A000027. A(3,n) is A000124.
Cf. A079500.
Sequence in context: A202175 A202176 A168443 * A306210 A133255 A354273
KEYWORD
nonn,tabl
AUTHOR
Jack W Grahl, Feb 02 2009, Feb 11 2009
EXTENSIONS
More terms from Alois P. Heinz, Jun 14 2009
Edited by N. J. A. Sloane, Feb 26 2011
STATUS
approved