Given a multi-variable function $F$, denote the number of monomials by $N(F)$. For example, $N(x(x+y))=N(x^2+xy)=2$ and 
$$
N(x(x+y)(x+y+z))=N(x^3+2x^2y+x^2z+xy^2+xyz)=5.
$$


Define the functions $f\_n=\prod\_{i=1}^n(y\_1+\cdots+y\_i)$ and $g\_n=\prod\_{i=1}^n(y\_1+\cdots+y\_i+x\_{i+1})$ and 
$$
h\_n=\prod\_{i=1}^n(y\_1+\cdots+y\_i+x\_{i+1}+x\_{i+2}).
$$


This work



> 
> Tewodros Amdeberhan and Richard P. Stanley, *Polynomial Coefficient Enumeration*, preprint (2008) arXiv:[0811.3652](https://arxiv.org/abs/0811.3652) ([pdf](http://dauns.math.tulane.edu/~tamdeberhan/PCE.pdf))
> 
> 
> 


shows (and it is easy) that $N(f\_n)=C\_n$ ([the Catalan numbers](https://en.wikipedia.org/wiki/Catalan_number)) and with a little bit of effort $N(g\_n)=\frac1n\sum\_{k=0}^n2^k\binom{n}k\binom{n}{k-1}$ ([the large Schröder numbers](https://en.wikipedia.org/wiki/Schr%C3%B6der_number)).



> 
> **Question.** What about $N(h\_n)$?
> 
> 
> 



Expanding into monomials
Let $\mathrm{CC}\_n$ denotes the set of Catalan codes of length $n$, i.e.
$$\mathrm{CC}\_n = \left\{ (c\_0, \dots, c\_{n-1})\in \mathbb{Z}\_{\geq 0}^n\ :\ c\_0+\dots+c\_i\leq i\ \text{for all}\ i=0,1,\dots,n-1 \right\}.$$
For $c\in \mathrm{CC}\_n$, denote $s(c) = n-c\_0-\dots-c\_{n-1}$.


Then
$$N(h\_n) = \sum\_{k=0}^n [x^k]\ \sum\_{c\in \mathrm{CC}\_{n-k}} (1-2x)^{-s(c)-1} \cdot\prod\_{i=0}^{n-k-1} \frac{1+(1-2x)^{-c\_i-1}}{2},$$
where $[x^k]$ is the operator taking the coefficient of $x^k$. (I did not think much about simplifying this expression.)


Notice that there is a similar expression for $N(g\_n)$, which indeed simplifies to the large Schröder number $S\_n$:
$$
\begin{split}
N(g\_n) &= \sum\_{k=0}^n [x^k]\ \sum\_{c\in \mathrm{CC}\_{n-k}} (1-x)^{-s(c)-1} \cdot\prod\_{i=0}^{n-k-1} (1-x)^{-c\_i-1} \\
& = \sum\_{k=0}^n [x^k]\ C\_{n-k}\cdot (1-x)^{-2(n-k)-1} \\
& = \sum\_{k=0}^n C\_{n-k}\cdot \binom{2n-k}{k} \\
& = S\_n.
\end{split}$$


This is my SAGE code implementing the aforementioned formula for $N(h\_n)$:



```
def myNh(n):
  R.<x> = PowerSeriesRing(ZZ)
  return sum( \
    sum( \
        ( prod( \
            1 + (1-2*x+O(x^(k+1)))^(-c[i]-1) \
          for i in range(n-k) ) \
        ) * (1-2*x+O(x^(k+1)))^(-(n-k-sum(c))-1) / 2^(n-k) \
     for c in map(lambda x: x.to_Catalan_code(), DyckWords(n-k)) )[k] \
  for k in range(n+1) )

```

For $n=0,1,\dots,14$, it gives


1, 3, 11, 46, 210, 1018, 5150, 26889, 143829, 784167, 4341843, 24348352, 138007784, 789375504, 4550522248


which match the values computed by others in the comments. I've added it as the sequence [A281548](http://oeis.org/A281548) to the OEIS.


