I came across these numbers : $$ T(p,q)= \sum_{k=0}^{q-1} {p+k-1 \choose p-1} + \sum_{l=0}^{p-1} {q+l-1 \choose q-1} \quad p,q \in \mathbb{N} $$ While trying to solve this recurrence relation : $$ \left\{ \begin{array}{c} T(p,q) = T(p-1,q) + T(p,q-1) \quad \forall p,q \in \mathbb{N}^{*} \\ T(p,0) = 1 \quad \forall p \in \mathbb{N}^{*} \\ T(0,q) = 1 \quad \forall q \in \mathbb{N}^{*} \\ \end{array} \right. $$ As both the relation and the expression are fairly simple, I'm certain these numbers have been studied already, but I can't seem to find their name, or if they have a simpler expression.

  • $\begingroup$ Pascal's triangle? $\endgroup$ – user72012 Jul 1 '15 at 22:45
  • $\begingroup$ Indeed, using Pascal's triangle it looks like the expression can be simplified to $T(p,q) = {p+q \choose p}$. Thank you. $\endgroup$ – Quarint Jul 1 '15 at 23:16
  • $\begingroup$ I solved the problem with a bit different boundary values here, and another poster mentioned Pascal's triangle there as well. $\endgroup$ – krvolok Jul 2 '15 at 11:08
  • $\begingroup$ Thanks for the alternative resolution. I found my formula by counting the leaves of the recursion tree. $\endgroup$ – Quarint Jul 2 '15 at 20:14

There is no in my knowledge a name for these numbers. Using the formula you have given, the sums can be computed and we can conclude that : $$T(p,q)={p+q-1\choose q}+{q+p-1 \choose p}={p+q \choose p}$$

(when $p$ and $q$ are both positive)

  • $\begingroup$ Thanks to user72012 I found that this simplifies to $T(p,q) = {p+q \choose p}$ which, I guess, explains why they don't have a name. Thanks. $\endgroup$ – Quarint Jul 1 '15 at 23:17

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.