Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to solve the recursion:

$$p[n,m] = p[n-1,m-1] + p[n+1,m-1] + p[n,m-1]$$

Ideally in general, but if you need base cases:

$$p[n,0] = 0 \text{ (for } n \neq 0),$$ $$p[0,0] = 1$$

I've asked a similar question previously and believe $n^{m-2}$ is somehow involved.

Would turning this into a DFQ help?

share|cite|improve this question
Very similar question:… – lhf Jun 4 '11 at 1:04

See OEIS A027907 and references on trinomial coefficients. If you just start making the triangle in a spreadsheet and type the numbers into OEIS you will find it.

share|cite|improve this answer

Given your boundary conditions, if we open up the recurrence relation then we discover an $m$-step process, where at each step we change $n$ by $0$ or $\pm 1$. For every walk that ends up at $0$, we "score" one point.

How many such walks exist? There is an equal number $k$ of $+1$s and $-1$s, and so we get

$\displaystyle \sum_{k=0}^{\lfloor m/2 \rfloor} \binom{m}{k,k} = \sum_{k=0}^{\lfloor m/2 \rfloor} \frac{m!}{k!k!(m-2k)!}$

In order to estimate it, let's calculate the largest coefficient, assuming $m$ is divisible by $3$. It is

$\displaystyle \frac{m!}{(m/3)!} \approx \frac{\sqrt{2\pi m}(m/e)^m}{\sqrt{2\pi (m/3)}^3 (m/3e)^m} = \frac{3^m}{(2\pi/3^{1.5})m}$

Roughly, we expect about $O(\sqrt{m})$ of the summands to be of comparable size, so a conjectured upper bound would be $O(3^m/\sqrt{m})$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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