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.'s discontentment 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$ – user47870 Mar 27 '18 at 14:00
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
    $\begingroup$ It's better to use Quotient[n, 2] than Floor[n/2]. $\endgroup$ – J. M.'s discontentment 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