# counting combinations of {+1, -1} with constraints

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.comSep 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.

• Nice question but it should be better for math.stackexchange – Stéphane Laurent Sep 27 '14 at 18:11
• Is is possible to ask a moderator to migrate it? – Ziofil Sep 27 '14 at 19:16
• In Statistical Mechanics, there is a similar problem related to spins. – 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".
• I don't quite understand what is M here. Is it $2N$? – Ziofil Sep 29 '14 at 3:01
• $M$ should be $N$ - I will edit – Henry Sep 29 '14 at 7:12
• 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). – Ziofil Sep 29 '14 at 19:43