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?

$\endgroup$
  • 2
    $\begingroup$ Do you want to solve this with Mathematica? $\endgroup$ – J. M. is away Mar 27 '18 at 13:45
  • $\begingroup$ @J.M. Both by a pencil and mma, especially the latter, for here is the site of mma. $\endgroup$ – Jireh Wong Mar 27 '18 at 14:00
2
$\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}

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.