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

Author

Jack W Grahl, Feb 02 2009, Feb 11 2009

Keywords

• nonn
• tabl

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

Examples

			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).
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..2278
• Michele Graffeo, Sergej Monavari, Riccardo Moschetti, and Andrea T. Ricolfi, Enumeration of partitions via socle reduction, arXiv:2501.10267 [math.CO], 2025. See p. 32.

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.

Programs

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 *)

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

Extensions

More terms from Alois P. Heinz, Jun 14 2009

Edited by N. J. A. Sloane, Feb 26 2011