login
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

%I #47 Feb 27 2018 03:32:58

%S 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,

%T 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,

%U 82,102,93,71,37,10,1,1,6,24,63,120,172,180,148,101,46,11,1,1,7,28,81,170

%N 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.

%C 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.

%C The sums of the antidiagonals give A079500 - 1. - _N. J. A. Sloane_, Feb 26 2011

%C 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

%H R. H. Hardin, <a href="/A156041/b156041.txt">Table of n, a(n) for n = 1..2278</a>

%F A(n,k)= [[x^n]]Sum_{i=0..n} x^i*((1 - x^(i+1))/(1-x))^(k-1). - _Geoffrey Critzer_, Jul 15 2013

%e The array A(n,k) begins:

%e 1 1 1 1 1 1 1 1 1 ...

%e 1 2 3 4 5 6 7 8 9 ...

%e 1 2 4 7 11 16 22 29 ...

%e 1 3 6 11 19 31 48 ...

%e 1 3 8 17 32 56 ...

%e 1 4 11 26 54 ...

%e 1 4 13 35 ...

%e ...

%e The antidiagonals are:

%e 1,

%e 1, 1,

%e 1, 2, 1,

%e 1, 2, 3, 1,

%e 1, 3, 4, 4, 1,

%e 1, 3, 6, 7, 5, 1,

%e 1, 4, 8, 11, 11, 6, 1,

%e 1, 4, 11, 17, 19, 16, 7, 1,

%e 1, 5, 13, 26, 32, 31, 22, 8, 1,

%e ...

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

%p b:= proc(n, i, m) option remember;

%p if n<0 then 0

%p elif n=0 then 1

%p elif i=1 then `if`(n<=m, 1, 0)

%p else add(b(n-k, i-1, m), k=0..m)

%p fi

%p end:

%p A:= (n, k)-> add(b(n-m, k-1, m), m=ceil(n/k)..n):

%p seq(seq(A(d-k, k), k=1..d-1), d=1..14); # _Alois P. Heinz_, Jun 14 2009

%t (* 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 *)

%Y 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.

%Y Cf. A079500.

%K nonn,tabl

%O 1,5

%A _Jack W Grahl_, Feb 02 2009, Feb 11 2009

%E More terms from _Alois P. Heinz_, Jun 14 2009

%E Edited by _N. J. A. Sloane_, Feb 26 2011