Nonnegative Partial Sum

Author

Eric W. Weisstein
January 3, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/NonnegativePartialSum.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/NonnegativePartialSum.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<DiscreteMath`Combinatorica`

n 1s and n -1s

Ones[n_,k_]:=Permutations[Join[Table[1,{n}],Table[-1,{k}]]]
Ones[n_]:=Ones[n,n]

Table[Count[Ones[n],_?(NonNegative/@And@@Rest[FoldList[Plus,0,#]]&)],{n,0,9}]//Timing

Table[Select[Ones[n],(And@@NonNegative/@Rest[FoldList[Plus,0,#]]&)],{n,0,3}]//ColumnForm

Table[CatalanNumber[n],{n,0,7}]

n 1s and k -1s

(t=Table[Count[Ones[n,k],_?(And@@NonNegative/@Rest[FoldList[Plus,0,#]]&)],{n,0,6},{k,0,n}])//TableForm

Flatten[t]

f[n_,k_]:=Product[n+i,{i,2,k}](n+1-k)/k!

f[n,k]

FullSimplify[FunctionExpand[f[n,n]]-Binomial[2n,n]/(n+1)]

Table[f[n,k],{n,0,6},{k,0,n}]//TableForm

Table[(((n+k)!(n-k+1))/(k!(n+1)!)),{n,0,6},{k,0,n}]//TableForm