6
$\begingroup$

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)$?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$
    – Kevin Buzzard
    Jan 19, 2017 at 18:22
  • $\begingroup$ Yes, that is right: 3, 11, 46, 210, 1018, 5150, 26889 $\endgroup$
    – T. Amdeberhan
    Jan 19, 2017 at 18:47
  • $\begingroup$ some more terms: 3, 11, 46, 210, 1018, 5150, 26889, 143829, 784167 $\endgroup$
    – Per Alexandersson
    Jan 19, 2017 at 19:32
  • $\begingroup$ 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. $\endgroup$
    – Pietro Majer
    Jan 22, 2017 at 21:53

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – T. Amdeberhan
    Jan 22, 2017 at 16:31
  • $\begingroup$ @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]. $\endgroup$
    – Max Alekseyev
    Jan 23, 2017 at 3:10
  • $\begingroup$ 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})$. $\endgroup$
    – T. Amdeberhan
    Jan 23, 2017 at 3:29

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.