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.

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

R. H. Hardin, Table of n, a(n) for n = 1..2278

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

Adjacent sequences: A156038 A156039 A156040 * A156042 A156043 A156044

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