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
    Commented 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
    Commented 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
    Commented 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
    Commented Dec 14, 2022 at 17:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.