# And, yet, another evaluation to Catalan numbers

Construct the $$n$$-tuple Cartesian product of the ternary set $$X_n=\{0,1,2\}\times\cdots\times\{0,1,2\}=\{0,1,2\}^n$$. Define its subset $$W_n$$ according to the rule (here $$y=(y_1,\dots,y_n)$$ is made use of) $$W_n=\{y\in X_n: y_1\leq1, y_1+y_2\leq2,\dots,y_1+\cdots+y_{n-1}\leq n-1, y_1+\cdots+y_n=n\}.$$ Introduce the one-variable polynomial $$P_n(x)=\sum_{y\in W_n}x^{\prod_{j=1}^n\binom{2}{y_j}}.$$

QUESTION. If $$C_n$$ stands for the Catalan numbers, is this true? $$\frac{dP_n}{dx}(1)=C_{n+1}.$$

Examples. $$P_1(x)=x^2, P_2(x)=x^4+x, P_3(x)=x^8+3x^2, P_4(x)=x^{16}+6x^4+2x$$.

Write each $$y_j = 1 - x_j$$ with $$x_j \in \{-1, 0, 1\}$$, so the condition is that $$\sum_{j=1}^n x_n = 0$$ and no partial sum is negative. This can be viewed as an n-move king path from $$(0,0)$$ to $$(n,0)$$ that never goes below the horizontal axis. We want the sum over such $$(x_1,\ldots,x_n)$$ of $$2^h$$ where $$h$$ is the number of indices $$j$$ for which $$y_j = 1$$, i.e. $$x_j = 0$$ (the number of horizontal king steps).
If we drop the nonnegativity condition, then for each $$k$$ the sum of $$2^h$$ over paths from $$(0,0)$$ to $$(n,k)$$ is the $$t^k$$ cofficient in the generating function $$(t^{-1} + 2 + t)^n$$; since that's just $$(t+1)^{2n} / t^n$$, the sum is $$2n \choose n+k$$.
By a reflection argument familiar from the Catalan enumeration of Dyck paths, it follows that for $$k=0$$ restricted to nonnegative paths is the difference between the unrestricted $$k=0$$ and $$k=-1$$ sums, which is $${2n \choose n} - {2n \choose n-2} = C_{n+1}$$.
• Alternatively we can reduce to Dyck paths of length $2(n+1)$: the first step must be $\nearrow$, the last must be $\searrow$, and the 2n intermediate steps are grouped in pairs to get $n$ steps each of which is a double $\nearrow$, double $\searrow$, or (with multiplicity $2$) double $\rightarrow$, etc. Dec 13, 2022 at 3:52
• This is great. I was expecting $C_{n+1}$, not $C_n$. Is something missing? Dec 13, 2022 at 14:55
• You're right; I'll correct this. The reflection argument gives ${2n \choose n} - {2n \choose n-2}$, not ${2n \choose n} - {2n \choose n-1}$. I recognized ${2n \choose n} - {2n \choose n-1}$ as a Catalan number, but didn't check that it's the correct one, and didn't notice that I'm reflecting about the line $y = -1$, not $y = -1/2$. I don't think I ever knew or noticed that ${2n \choose n} - {2n \choose n-2}$ is a Catalan number too! [It makes sense that it should be about $4$ times as large, because ${2n \choose n} - {2n \choose n-m} \sim C_n m^2$ for small $m$ and large $n$.] Dec 14, 2022 at 17:01
• That's quite remarkable that $\binom{2n}{n}-\binom{2n}{n-2}$ is also a Catalan number - I did not know it either! Dec 14, 2022 at 17:28