# Generalization of Catalan numbers

Some time ago I was trying to find a closed form formula for the number of tuples $$(a_k)_{k=1}^{n+s}$$ of non-negative integers satisfying following conditions:

1. $$\sum_{k=1}^{n+s} a_k = n$$,
2. $$\forall m \in \mathbb{N}_0 \quad m < n \implies \sum_{k=1}^{m+s} a_k > m$$,

where $$n \in \mathbb{N}_0 = \mathbb{N} \cup \{0\}$$ and $$s \in \mathbb{N}$$. I think (a document I've written in Polish wasn't peer reviewed, so it'd just be my claim) I proved that the number of the mentioned tuples is given by

$$\left( \binom{n +s}{n} \right) \frac{s}{n+s},$$

where symbol $$\left( \binom{a}{b} \right)$$ is a so-called multiset coefficient defined by

$$\forall a,b \in \mathbb{N}_0 \quad \left( \binom{a}{b} \right) = \begin{cases} \binom{a+b-1}{b}, &\text{ for }a, b \in \mathbb{N}, \\ 0, &\text{ for } a = 0, b \in \mathbb{N}, \\ 1, &\text{ for } a \in \mathbb{N}_0, b = 0. \end{cases}$$

If we were to substitute $$s = 1$$ in the formula for the tuples, we would get the formula for the $$n^\text{th}$$ Catalan number.

Also, using the mentioned formula I claimed that the following holds:

$$\forall s \in \mathbb{N} \quad \sum_{n=0}^\infty \left( 2^{-(2n+s)} \left( \binom{n +s}{n} \right) \frac{s}{n+s} \right) = 1.$$

I would like to ask whether either of these results are known (if they are correct) and if so, where could I find some paper regarding it. The proof (, which, I hope, is correct) of the first claim which I've written in the mentioned document is rather cumbersome, so I would be interested if this result could be proven in some relatively easy way.

• When I substitute $s = 1$ I get that your expression is just $1$, which doesn't sound very correct. Perhaps you meant $\left( \binom{n + s}{n} \right)$ instead of $\left( \binom{n + s}{s} \right)$? Jul 13, 2021 at 21:49
• Yes, thank you for noticing, I meant $\left( \binom{n+s}{n} \right)$ I edited the question Jul 13, 2021 at 21:59
• The sum can be rearranged to $2^{-s} {}_2F_1(\tfrac{s+1}2, \tfrac s2; s+1; 1)$ and then computer algebra packages are able to simplify that to $1$ as desired. Jul 14, 2021 at 6:53
• When $s$ and $n$ are coprime, the number $\left( \binom{n+s}{n} \right) \frac{s}{n+s}$ happens to be equal to $s$ times the rational Catalan number $C_{n,n+s}$ as defined by Armstrong-Rhoades-Williams in arxiv.org/abs/1305.7286. Rational Catalan numbers count certain partitions but in a way that does not seem obviously connected to the ones you have defined. Jul 17, 2021 at 5:12

Let $$a_k$$ be such a sequence and define $$\lambda_k := n - \sum_{i=1}^{k}a_i$$ for $$k=1,\ldots,n+s-1$$. Then $$\lambda = (\lambda_1,\ldots,\lambda_{n+s-1})$$ is a partition with $$\lambda_1 \leq n$$ and $$\lambda_{s+m} \leq n- 1- m$$ for all $$0 \leq m < n$$. Its transpose partition $$\lambda^t = (\lambda^t_1,\ldots,\lambda^t_{n})$$ satisfies $$\lambda^t_i \leq n+s-2-i$$ for all $$i=1,\ldots,n$$. In this way we obtain a bijection between your sequences $$a_k$$ and partitions contained in (i.e., with Young diagram is contained in) the "staircase shape" partition $$(n+s-2,n+s-3,\ldots,s)$$.
There are various formulas for the number of partitions contained in a given partition shape: for instance, a determinantal formula due to MacMahon. However, in your particular case the staircase shape has a straight product formula for this number, which is special. This is probably vast overkill, but the number of partitions contained in the staircase shape is the same as the number of plane partitions of this shape, with entries at most one. In general, the number of plane partitions of staircase shape with entries at most $$m$$ has a product formula, due to Proctor; see Corollary 4.1 of his paper "Odd symplectic groups" (https://doi.org/10.1007/BF01404455) or exercerise 7.101 of Stanley's Enumerative Combinatorics, Vol. 2.