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.

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

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*n-1,n-1)/n <= a(n) <= C(2*n-1,n-1). - 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(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(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[n-k, i-1, m], {k, 0, m}]]; A[n_, k_] := Sum[b[n-m, k-1, m], {m, Ceiling[n/k], n}]; Table[A[n, n], {n, 1, 30}] (* Jean-Franç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, N-1, for(j=0, N-1, s=0; for(k=0, min(j, d), s+=A[i, j-k+1]); A[i+1, j+1]=s)); for(i=d, N, v[i]+=A[i, i-d+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: A320567 A135339 A148170 * A268322 A148171 A318644

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