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



And, yet, another evaluation to Catalan numbers
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}$.


