Constructing a generating function using a series with all negative and positive powers of a variable

Question

Trying to count certain combinatorial structures, I arrived at a construction of their generating function through a very inconvenient procedure.

I realize that anybody who will read this has right to demand disclosing the problem as originally stated, and in the end I will briefly describe it, but my main interest is to formulate the procedure itself since what I want to ask is whether there exist methods to transform such constructions into something more manageable.

My generating function has form $$ F(t)=F_1(t,1)+F_2(t,1)+F_3(t,1)+... $$ where each summand comes from a series in two variables, $F_k(t,z)$ having nonzero coefficients only at positive powers of $t$ and $z$. They are determined inductively as follows: $F_1(t,z)=tz+t^2z^2+t^3z^3+...=tz/(1-tz)$, while each subsequent $F_{k+1}(t,z)$ is obtained from the product $F_k(t,zt)G_\pm(t,zt)$ by dropping all terms containing nonpositive powers of either $t$ or $z$.

Here $G_\pm(t,z)$ has form $G(t,z)+1+G(t,z^{-1})$ where $G$ is an explicitly given rational function whose power series expansion also only contains positive powers of the variables; however as you see $G_\pm$ contains both positive and negative powers, so the product $F_k(t,zt)G_\pm(t,zt)$, although well-defined (i. e. there are only finitely many contributions to each monomial), will contain both positive and negative powers too, and the nonpositive ones have to be simply erased.

If not this erasing, $F$ would be nicely obtained as an infinite product, something like $(1+G(t,t))(1+G(t,t^2))(1+G(t,t^3))\cdots$, but unfortunately without the negative power terms (although they are thrown out after forming the products) I cannot obtain correct answer.

So my question is whether there exist methods to deal with similar situations. I've seen some series with both negative and positive powers in the context of vertex algebras, there such series seem to be somehow tamed from the very beginning, but I have no idea whether I can use this in my situation or whether there is any connection at all.

If this helps, explicit form of $G$ is this: $$ G(t,z)=\frac z{1-2t}\left(\frac{1-t}{1-z}-\frac{t^2(1-2t^2)}{(1-3t^2)(1-2tz)}\right) $$

Briefly, the problem itself: with $F(t)=\sum_nF(n)t^n$, the number $F(n)$ is the number of pairs $(C,S)$ where $C=(c_1,...,c_m)$ is a composition of $n$ (i. e. $c_1,...,c_m$ are natural numbers with $c_1+...+c_m=n$) and $S=\{s_1,...,s_k\}$ is a subset of $\{1,...,m\}$ containing $1$ and $m$ (i. e. $1=s_1<\cdots<s_k=m$), with the following property: for any fragment $(c_{s_i},c_{s_i+1},...,c_{s_{i+1}-1},c_{s_{i+1}})$ of $C$ placed between any two parts of $C$ with adjacent indices from $S$, and for any $s_i\leqslant j<j'\leqslant s_{i+1}$, the equality $c_{s_i}+...+c_j=c_{j'}+...+c_{s_{i+1}}$ is only allowed to hold if $j'-j=1$. The sequence of the numbers $F(n)-1$, $n>0$ (which I finally need) starts with $1, 3, 9, 23, 62, 157, 412, 1053, 2734, ...$ (needless to say, it is not on OEIS).

I realize this looks very uninspiring and cryptic but it is a long story to explain why this particular problem is interesting for me. It arose in an attempt to find an upper bound for the numbers I described in a question here before ("Special" meanders)

Just to connect it with the series from the beginning, - coefficient at $t^nz^c$ of $F_k(t,z)$ is the number of pairs $(C,S)$ as above (with $n$ and $k$ as there), and with the last part $c_m=c_{s_k}$ equal to $c$.

Update

In view of the answer by Max Alekseyev and of the comment by Richard Stanley, here is a reformulation, hopefully slightly more manageable. In principle I could modify the above text but decided to leave it as it was.

So, let us rewrite our two-variable generating function as follows: $$ FF(t,z):=\sum_{k,m,c}\left([t^{m+c}z^c]F_k(t,z)\right)t^mz^c. $$ (This clearly contains all the needed information, as $F(t)=FF(t,t)$.) Then this $FF$ satisfies $$ FF(t,z)=1+\operatorname{Pos}\left(G_\pm(t,z)FF(t,zt)\right) $$ where "$\operatorname{Pos}$" means only leaving terms with powers of $t$ and $z$ both positive, and $G_\pm$ is as above.

From this it follows that $FF$ can be obtained as "$\lim$"$FF^{(n)}$, where $FF^{(0)}=1$ and $FF^{(n+1)}(t,z)=1+\operatorname{Pos}\left(G_\pm(t,z)FF^{(n)}(t,zt)\right)$ and "$\lim$" means that $FF^{(n+1)}\equiv FF^{(n)}\mod z^{n+1}$.

Thus in a sense $FF$ is like the infinite product $\prod_nG_\pm(t,zt^n)$ except that after multiplying by each subsequent factor one has to apply $\operatorname{Pos}$.

I remain wondering - cannot this $FF$ after all actually be given by an infinite product of rational functions like $G(t,zt^n)$ or similar?

Answer 1

This is not a complete answer, but a simpler analogous example with a known solution.

Consider a $n\times n$ square grid and let us compute the number of paths (known as Dyck paths) from the bottom left corner $(0,0)$ to the top right corner $(n,n)$ that never go below the diagonal, where each step is done either right or upper direction.

Let $$F_k(x,y) = \sum_{i,j\geq 0} c^{(k)}_{i,j} x^i y^j,$$ where $c^{(k)}_{i,j}$ is the number of paths of length $k$ from $(0,0)$ to $(i,i+j)$ (notice that $c^{(k)}_{i,j}$ is nonzero only if $2i+j=k$).

Clearly, we have $F_0(x,y)=1$ and $F_{k+1}(x,y)$ can be obtained as the restriction of $F_k(x,y)\cdot(xy^{-1}+y)$ to the terms with nonnegative powers of both $x$ and $y$. First few $F_k(x,y)$ are listed below: $$F_0(x,y) = 1$$ $$F_1(x,y) = y$$ $$F_2(x,y) = x + y^2$$ $$F_3(x,y) = 2xy + y^3$$ $$F_4(x,y) = 2x^2 + 3xy^2 + y^4$$

The number of Dyck paths (of length $2n$) is given by the coefficient of $x^ny^0$ in $F_{2n}(x,y)$, which is the same as the coefficient of $x^ny^0$ in $$\mathcal{F}(x,y) = \sum_{k=0}^{\infty} F_k(x,y).$$

Without the restriction to nonnegative powers $F_{k}(x,y)$ would be simply $(xy^{-1}+y)^k$. In reality, the coefficient of $x^iy^j$ in $\mathcal{F}(x,y)$ is known to be $\binom{2i+j}{i}\frac{j+1}{i+j+1}$. In particular, the coefficient of $x^ny^0$ is the Catalan number $C_n$.

This gives a hope that it may be possible to employ the approaches for enumerating Dyck paths to the problem posed in this MO question.