11
$\begingroup$

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$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

Yes, this is true.

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}$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Noam D. Elkies
    Dec 13, 2022 at 3:52
  • 1
    $\begingroup$ This is great. I was expecting $C_{n+1}$, not $C_n$. Is something missing? $\endgroup$
    – T. Amdeberhan
    Dec 13, 2022 at 14:55
  • 2
    $\begingroup$ 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$.] $\endgroup$
    – Noam D. Elkies
    Dec 14, 2022 at 17:01
  • 2
    $\begingroup$ That's quite remarkable that $\binom{2n}{n}-\binom{2n}{n-2}$ is also a Catalan number - I did not know it either! $\endgroup$
    – Vladimir Dotsenko
    Dec 14, 2022 at 17:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .