A problem of a sequence and its sum

{a(n)} is such a sequence, satisfying,

1. For all a(i) ∈ {a(n)}, a(i) =1 or -1

2. Let S(j) = Sum[a(i) , {i ,1, j}], then for all 1<=j<=n ,S(j)>=0.

For a given n , how many {a(n)} are there?

• Do you want to solve this with Mathematica? – J. M. is away Mar 27 '18 at 13:45
• @J.M. Both by a pencil and mma, especially the latter, for here is the site of mma. – Jireh Wong Mar 27 '18 at 14:00

From Sloane's A001405 and A210736, your sequence a[n] is the number of length n words on {-1,1} such that the sum of any of its prefixes is always nonnegative. The count given there is written in Mathematica as follows.

Binomial[n,Floor[n/2]]


For example,

Table[Binomial[n,Floor[n/2]],{n,1,10}]


{1, 2, 3, 6, 10, 20, 35, 70, 126, 252}

One, far less efficient, way to generate and count the sequences uses the following functions.

u[v_?MatrixQ] := Map[And @@ NonNegative[#] &, v]
w[n_] := Pick[#, u[#]] &[Map[Accumulate, Tuples[{1, -1}, n]]]

Table[Length[w[n]],{n,1,10}]


{1, 2, 3, 6, 10, 20, 35, 70, 126, 252}

• It's better to use Quotient[n, 2] than Floor[n/2]. – J. M. is away Mar 28 '18 at 1:15