I'm trying to count the number of ways of arranging a sequence of length $N+2L$ made of "$+1$" and "$-1$", with the following two conditions:

1) the total has to sum to $N$

2) no partial sum is allowed to be negative or exceed $N$.

I can deal with the first condition by using $N+L$ occurrences of "$+1$" and $L$ occurrences of "$-1$" so that the number of possible combinations is $$\frac{(N+2L)!}{(N+L)!L!}={N+2L\choose L}$$ But some of these combinations have negative partial sums (e.g. if I start with a "$-1$"), or they exceed $N$ (e.g. if I start with all the "$+1$"), and I don't know how to count these and subtract them from the total.

EDIT: on mathworld.wolfram.com, the entry on Nonnegative partial sums mentions the Catalan triangle, which solves "half" of the problem by counting the sequences whose partial sum is bounded below by zero. I would need to additionally bound it above.


migrated from stats.stackexchange.com Sep 28 '14 at 7:37

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • 2
    $\begingroup$ Nice question but it should be better for math.stackexchange $\endgroup$ – Stéphane Laurent Sep 27 '14 at 18:11
  • $\begingroup$ Is is possible to ask a moderator to migrate it? $\endgroup$ – Ziofil Sep 27 '14 at 19:16
  • 1
    $\begingroup$ In Statistical Mechanics, there is a similar problem related to spins. $\endgroup$ – Felix Marin Sep 29 '14 at 1:41

I think there may be a generating function: some empirical calculations suggest you may be looking for the coefficient of $x^L$ in something like the expansion of $$\dfrac{1}{1-Nx+{N-1 \choose 2}x^2-{N-2 \choose 3}x^3+\cdots}=\dfrac{1}{\displaystyle \sum_{k=0}^{\lceil N/2 \rceil}(-1)^k {N+1-k \choose k} x^k} $$

For example with $N=7$ you get: $$1+7\,x+34\,{x}^{2}+143\,{x}^{3}+560\,{x}^{4}+2108\,{x}^{5}+7752\,{x}^{6}+28101\,{x}^{7}+100947\,{x}^{8}+360526\,{x}^{9}+1282735\,{x}^{10}+4552624\,{x}^{11}+\cdots$$ which look like the values in OEIS A005023 "Number of walks of length 2n+7 in the path graph P_8 from one end to the other".

  • $\begingroup$ I don't quite understand what is M here. Is it $2N$? $\endgroup$ – Ziofil Sep 29 '14 at 3:01
  • $\begingroup$ $M$ should be $N$ - I will edit $\endgroup$ – Henry Sep 29 '14 at 7:12
  • $\begingroup$ Very nice! It seems to be working! The nice thing is that the sum at the denominator has a closed form (which is different for $N$ even or odd). $\endgroup$ – Ziofil Sep 29 '14 at 19:43

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.