0
$\begingroup$

{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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Do you want to solve this with Mathematica? $\endgroup$ Commented Mar 27, 2018 at 13:45
  • $\begingroup$ @J.M. Both by a pencil and mma, especially the latter, for here is the site of mma. $\endgroup$ Commented Mar 27, 2018 at 14:00

1 Answer 1

Reset to default
1
$\begingroup$

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}

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ It's better to use Quotient[n, 2] than Floor[n/2]. $\endgroup$ Commented Mar 28, 2018 at 1:15