

A156043


A(n,n), where A(n,k) is the number of compositions (ordered partitions) of n into k parts (parts of size 0 being allowed), with the first part being greater than or equal to all the rest.


5



1, 2, 4, 11, 32, 102, 331, 1101, 3724, 12782, 44444, 156334, 555531, 1991784, 7197369, 26186491, 95847772, 352670170, 1303661995, 4838822931, 18025920971, 67371021603, 252538273442, 949164364575, 3576145084531, 13503991775252
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The value is smaller than the number of compositions of n into k parts and at least the number of (unordered) partitions.
It is also at least the number of compositions of n into n parts divided by n. From these bounds: C(2*n1,n1)/n <= a(n) <= C(2*n1,n1).  Robert Gerbicz, Apr 06 2011
a(n) is also the number of Dyck paths of semilength 2n such that each level has exactly n peaks or no peaks. a(3) = 4: //\\//\\//\\, ///\\//\/\\\, ///\/\\//\\\, ////\/\/\\\\.  Alois P. Heinz, Jun 04 2017


LINKS

Robert Gerbicz, Table of n, a(n) for n = 1..500


EXAMPLE

a(4) = 11: the 11 compositions of this type of 4 into 4 parts being
(4,0,0,0); (3,1,0,0); (3,0,1,0); (3,0,0,1);
(2,2,0,0); (2,0,2,0); (2,0,0,2); (2,1,1,0);
(2,1,0,1); (2,0,1,1); (1,1,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(nk, i1, m), k=0..m) fi end: A:= (n, k)> add(b(nm, k1, m), m=ceil(n/k)..n): seq(A(n, n), n=1..30); # Alois P. Heinz, Jun 14 2009


MATHEMATICA

b[n_, i_, m_] := b[n, i, m] = Which[n<0, 0, n==0, 1, i==1, If[n <= m, 1, 0], True, Sum[b[nk, i1, m], {k, 0, m}]]; A[n_, k_] := Sum[b[nm, k1, m], {m, Ceiling[n/k], n}]; Table[A[n, n], {n, 1, 30}] (* JeanFrançois Alcover, Jul 15 2015, after Alois P. Heinz *)


PROG

(PARI) N=120; v=vector(N, i, 0); for(d=1, N, A=matrix(N, N, i, j, 0); A[1, 1]=1; for(i=1, N1, for(j=0, N1, s=0; for(k=0, min(j, d), s+=A[i, jk+1]); A[i+1, j+1]=s)); for(i=d, N, v[i]+=A[i, id+1])); for(i=1, N, print1(v[i]", ")) \\ Robert Gerbicz, Apr 06 2011


CROSSREFS

A156041 gives the full array A(n, k). See also A156039, A156040 and A156042.
One of two bisections of A188624 (see also A188625).
Sequence in context: A120848 A135339 A148170 * A268322 A148171 A113774
Adjacent sequences: A156040 A156041 A156042 * A156044 A156045 A156046


KEYWORD

nonn


AUTHOR

Jack W Grahl, Feb 02 2009


EXTENSIONS

More terms from Alois P. Heinz, Jun 14 2009
Edited by N. J. A. Sloane, Apr 06 2011


STATUS

approved



