# Expanding into monomials

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 (pdf)

shows (and it is easy) that $$N(f_n)=C_n$$ (the Catalan numbers) 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).

Question. What about $$N(h_n)$$?

• I get 3,11,46,210,1018,... which is not in OEIS. What do you get? My counting might not be as accurate as yours... – Kevin Buzzard Jan 19 '17 at 18:22
• Yes, that is right: 3, 11, 46, 210, 1018, 5150, 26889 – T. Amdeberhan Jan 19 '17 at 18:47
• some more terms: 3, 11, 46, 210, 1018, 5150, 26889, 143829, 784167 – Per Alexandersson Jan 19 '17 at 19:32
• How can one tell whether a monomial $M$ is present in the expansion of $h_n$ (with some non-zero coefficient)? Let's call the $x$-indeterminates $y_{-i}:=x_{i+2}$ for $0\le i\le n$; let's denote the degree wrto $y_i$, $\delta_i:=\operatorname{deg}(M,y_i)$ for $|i|\le n$. Of course it's needed $\sum_{|i|\le n} \delta_i=n$, and $\delta_i \le 2$ for $i\le0$ and $\delta_i \le n+1-i$ for $i>0$ but also, for instance, $\delta_{n-1}+\delta_n\le2$. Can you characterize the $M$ in $h_n$ by their degrees $\{\delta_i\}_{|i|\le n}$? This seems already more difficult than the analog $f$ or $g$ question. – Pietro Majer Jan 22 '17 at 21:53

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 to the OEIS.

• This is interesting. We've a recursive formula for $N(w_n)$ where $w_n=\prod_{i=1}^n(y_1+\cdots+y_i+x_{i+1}+x_{i+2}+x_{i+3})$. See page 33 of (www-math.mit.edu/~rstan/papers/coef.pdf). Can you get a formula in the above style for it? – T. Amdeberhan Jan 22 '17 at 16:31
• @T.Amdeberhan: I'll check if it can be extended. However, something is wrong with the formula in the referenced paper. First, there is a term $\nu_{n-i}$ in the recurrence formula while $i$ is undefined; and if it's replaced by $\nu_{n-j}$ the values do not quite match $2\cdot N(D_{n-2,2})$. For the first few terms of $N(D_{n-2,2})$, my calculations give [4, 17, 78, 380, 1938, 10238]. – Max Alekseyev Jan 23 '17 at 3:10
• Actually, you are right. I need to write (as in the paper): $w_n=\prod_{i=1}^n(y_1+\cdots+y_{i-1}+x_i+x_{i+1}+x_{i+2})$. – T. Amdeberhan Jan 23 '17 at 3:29