2
$\begingroup$

I have arrived at the combinatorial problem of enumerating certain types of ballot paths. This has led to analyzing the sequence defined by the following recurrence

$$ f(n,m) = \begin{cases} f(n, \thinspace m-1) + f(n-m, \thinspace m-1), & \text{ if } n \leq \left \lceil \binom{m}{2}/2 \right \rceil \\ f(n-m, \thinspace m-1), & \text{ if } n > \lceil \binom{m}{2}/2 \rceil \end{cases} $$

where $f(n,0) = \begin{cases} 1, & \text{ if } n = 0 \\ 0, & \text{ if } n \neq 0 \end{cases}$

I note that the recurrence $f(n, \thinspace m) = f(n, \thinspace m-1) + f(n-m, \thinspace m-1)$ alone counts the number of partitions of $n$ into distinct parts bounded by $m$, so a closed formula for my sequence is probably out of the question.

Question: Is it possible to obtain a generating function for this sequence?

I have seen many threads here regarding generating functions for recurrences with two parameters, but none of them deals with recurrences including a conditional.

In fact, any useful info regarding such recurrences would be appreciated.

$\endgroup$
7
  • $\begingroup$ I am having some difficulty seeing your recurrence producing more than $f(n,m) = 1$ when $n=\frac{m(m+1)}{2}$ and $0$ otherwise. What do you think are the values of for example $f(0,1)$, $f(1,3)$, $f(4,3)$ or $f(5,4)$? Perhaps I have misunderstood, or you may have a typo $\endgroup$
    – Henry
    Jun 29, 2016 at 0:37
  • $\begingroup$ The examples you mention are all zero. What you are expressing with e.g $f(5,4)$ is how many ways you can partition the integer $5$ into distinct parts $\lambda = (\lambda_1, \dots, \lambda_k)$ from the set $\{1,2,3,4 \}$ such that $\lambda_1 + \cdots + \lambda_i \leq \binom{\lambda_i}{2}/2$ for all $1 \leq i \leq k$. You can check that there are no such partitions. $\endgroup$
    – user94267
    Jun 29, 2016 at 5:31
  • $\begingroup$ I got zero too. So are there any non-zero values except $f\left(\frac{m(m+1)}{2},m\right)=1$? $\endgroup$
    – Henry
    Jun 29, 2016 at 6:43
  • $\begingroup$ Yes, there are plenty. e.g $f(10,7) = 2$ (I believe these are the smallest parameters such that $f(n,m) > 1$). Also $f\left ( \frac{m(m+1)}{2}, m \right ) = 0$ for all $m$ since there is only one way of writing $m(m+1)/2$ into a sum of distinct parts from $\{1, \dots, m \}$, namely $1 + 2 + \cdots + m$ and these parts do not satsify the condition mentioned in the previous comment. $\endgroup$
    – user94267
    Jun 29, 2016 at 10:20
  • $\begingroup$ The correct formulation of the condition should be $\lambda_1 + \cdots + \lambda_i \leq \binom{\lambda_i+1}{2}/2$ for all $1 \leq i \leq k$. $\endgroup$
    – user94267
    Jun 29, 2016 at 10:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.