login
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

%I #38 Jun 04 2017 19:01:32

%S 1,2,4,11,32,102,331,1101,3724,12782,44444,156334,555531,1991784,

%T 7197369,26186491,95847772,352670170,1303661995,4838822931,

%U 18025920971,67371021603,252538273442,949164364575,3576145084531,13503991775252

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

%C The value is smaller than the number of compositions of n into k parts and at least the number of (unordered) partitions.

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

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

%H Robert Gerbicz, <a href="/A156043/b156043.txt">Table of n, a(n) for n = 1..500</a>

%e a(4) = 11: the 11 compositions of this type of 4 into 4 parts being

%e (4,0,0,0); (3,1,0,0); (3,0,1,0); (3,0,0,1);

%e (2,2,0,0); (2,0,2,0); (2,0,0,2); (2,1,1,0);

%e (2,1,0,1); (2,0,1,1); (1,1,1,1)

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

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

%o (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

%Y A156041 gives the full array A(n, k). See also A156039, A156040 and A156042.

%Y One of two bisections of A188624 (see also A188625).

%K nonn

%O 1,2

%A _Jack W Grahl_, Feb 02 2009

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

%E Edited by _N. J. A. Sloane_, Apr 06 2011