| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

3. Generating functions

    1.     Suppose $R(x,y,z)=\frac{P(x,y,z)}{Q(x,y,z)}$ is a rational generating function, and $C(z)$ is a non-analytic generating function (for example $C(z)=\sum_n n! z^n$). Let $F(x,y)={R(x,y,z) \odot_z C(z)}{|_{z=1}}$, where $\odot$ denotes the Hadamard product.

      Add remark

      Problem 3.1.

      [Jay Pantone] Can ACSV do anything with this?

        • Embedding algebraic generating functions

              Suppose $F(x)$ is an algebraic generating function. It is known that it can be written as the diagonal of a rational generating function $R(x,y)$.

          Add remark

          Problem 3.2.

          [Mark Wilson] If $F(x)$ is combinatorial (that is $F(x)=\sum_n a_n x^n, a_n \in \mathbb Q_{\geq 0}$), does there exist $R(x,y)$ that is also combinatorial?
              For example if $F(x)=\frac{x}{\sqrt{1-x}}$, then we can take $R(x,y)=\frac{2xy}{2-x-y}$, but none of the general methods find this. A subprogram of ACSV is to reduce the case of algebraic generating functions to that of rational generating functions, and combinatorial ones are much nicer.


            • Add remark

              Problem 3.3.

              [Mark Wilson] If the answer to Problem 3.2 is yes, then does there exist an efficient way to find these?

                • $\mathbb N$-D-finiteness

                      Suppose $F(x)=\sum_n a_n x^n, a_n \in \mathbb Z_{\geq 0}$. $F$ is said to be $\mathbb N$-algebraic if \begin{align*} F_0&=P_o(x,F_0,F_1,\dots,F_n)\\ F_1&=P_1(x,F_0,F_1,\dots,F_n)\\ &\vdots\\ F_k&=P_k(x,F_0,F_1,\dots,F_n) \end{align*} where the coefficient of $P_0,P_1,\dots,P_k$ are nonnegative integers.

                  Add remark

                  Problem 3.4.

                  [Igor Pak] What is the $D$-finite analog of that? Replace $P_i$’s with ODE’s. What would be the asymptotics of this?


                    • Add remark

                      Problem 3.5.

                      [Igor Pak] It is known that the diagonal of a rational generating function is still $D$-finite. We want to define $\mathbb N$-D-finite. Is it the diagonal of a rational generating function $R(z)=\sum_{\omega} b_\omega z^\omega, b_\omega \in \mathbb Z_{\geq 0}$?

                        •     Suppose we have $F_{2n}(t,x,y)$ defined recursively as follows: \begin{align*} F_2(t,x,y)&=t^2 x+ty\\ q_{2n}(x,y)&=\frac 1 2 (F_{2n}(t,x,y)+F_{2n}(t,x,-u))\\ r_{2n}(x,y)&=[t^{2n}]q_{2n}(x,y)\\ F_{2n+2}(t,x,y)&=t^{2n} r_{2n}(x(t^2 x+ty+1),tx+y)-F_{2n}(t,x,y). \end{align*}

                          Add remark

                          Problem 3.6.

                          [Sheila Sundaram] Conjecturally, the coefficients of $q_{2n}(x,y)$ are nonnegative. Can ACSV help with this?
                            1. Remark. [Sheila Sundaram] Thank you to Stefan Trandafir for verifying the conjecture up to degree 200!

                              The reference for this problem is

                              Sundaram, Sheila The homology of partitions with an even number of blocks. J. Algebraic Combin. 4 (1995), no. 1, 69–92.

                              The polynomials in t,x,y are generated according to Algorithm 2.11. They originate in a plethystic recurrence involving the homogeneous symmetric functions.

                              The coefficient of t^{2n} in q_{2n} is r_{2n}(x,y), for whose coefficients I can give an explicit recurrence, see Conjecture 3.1. Those particular coefficients were later proved to be nonnegative in Benjamin Joseph’s MIT thesis.

                              But the main conjecture, that ALL the coefficients in q_{2n}(t,x,y) are nonnegative, is still open.

                                  Cite this as: AimPL: Analytic combinatorics in several variables, available at http://aimpl.org/combinseveral.