Two variable recurrence relations with conditionals

67 Views Asked by At

Is it possible to obtain a generating function for the sequence described 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}$

: $f(0,m) = 0$

The recurrence arises from enumerating certain types of ballot paths. The recurrence $f(n,m) = f(n,m-1) + f(n-m,m-1)$ alone I believe counts the number of partitions of $n$ into distinct parts bounded by $m$. The generating function for that recurrence should be $$ \prod_{i=1}^m (1+q^i). $$

One may also formulate the sequence in question as counting certain types of partitions (if that helps). The sequence $f(n,m)$ is the number of partitions $\lambda = (\lambda_1, \dots, \lambda_k)$ such that

(1) $\lambda_1,\dots, \lambda_k \leq m$ are pairwise distinct,

(2) $\lambda_1 + \cdots + \lambda_k = n$ and

(3) $\lambda_1 + \cdots + \lambda_i \leq \frac{\binom{\lambda_i+1}{2}}{2}$ for all $1 \leq i \leq k$.