Let $f_n(q)$ be the generating function of the number of Zigzag permutations of size $n$ that start with an up-step, according to the inv statistic. Prove that :
$$1. f_{n+1}(q)= \sum_{j=0,\dots, n\\ \text{$j$ odd}} \binom{n}{j}_q q^{n-j}f_j(q)f_{n-j}(q).$$ 2.Find the q_exponential generating function of $f_n(q)$.
Here are some definitions we are using:
An up-down permutation of size $n$ that starts with an up-step means a permutation $\pi = \pi_1 \pi_2 \cdots \pi_n$ (written in one-line notation) with $\pi_1 < \pi_2 > \pi_3 < \pi_4 > \pi_5 \cdots \pi_n$.
For example, for $n=2$, the only such permutation is $\pi = 12$.
For $n=3$, the only two such permutations are $132$ and $231$.
The inv statistic sends a permutation $\pi$ to $\operatorname{inv}(\pi) := \left| \left\{ (i,j) \mid 1 \leq i < j \leq n,\ \pi_i > \pi_j \right\} \right|$.
For example, for $\pi = 1$, we have $\operatorname{inv}(\pi) = 0$.
For $\pi = 12$, we have $\operatorname{inv}(\pi) = 0$. For $\pi = 21$, we have $\operatorname{inv}(\pi) = 1$.
Can someone suggest a clear solution to this question? For 2 I substituted the $f_{n}(q)$ formula from the 1st part in : $f(x,q)= \sum_{n=0}^{\infty} \frac{f_n(q) x^n}{[n]_q!}$ And I got: $x*\sum_{n=1}^{\infty}(\sum_{j=0}^{n-1}\frac{q^{n-j-1}f_j(q) x^j f_{n-j-1} x^{n-j-1}}{[n]_q [j]_q! [n-j-1]_q!})$
Can someone help me in 2, i tried hard but I did not get a simplification to this.
Define the standard finite sets $\,[n]:=\{1,2,\dots,n\}.\,$ We need the definition from Wikipedia of an inversion. For a function $\,s:[n]\to[m]\,$ an inversion is a pair $\,i<j\,$ such that $\,s(i)>s(j).\,$ Call an injective function $\,s\,$ "up-down" if $\,s(j)<s(j+1)\,$ iff $\,j\,$ is odd. Important examples include the alternating permutations.
The Wikipedia article Gaussian binomial coefficient defines $\,[n]_q := 1+q+...+q^{n-1},\;$ $\,[n]_q! := [1]_q[2]_q\cdots[n]_q,\;$ and $\,\binom{n}{m}_q := [n]_q!/([m]_q![n-m]_q!).\,$ The "Combinatorial description" section of the Wikipedia article gives an interpretation of "inversion" for "words". This is equivalent to the following interpretation. Each $m$-subset $\,A\,$ (a subset with $\,m\,$ elments) of $\,[n]\,$ is uniquely determined by $\textbf{1}_A$, its indicator function. An inversion of $\,A\,$ is defined as an inversion of $\textbf{1}_A.$ That is, a pair $\,i<j\,$ where $\,i\in A\,$ and $\,j\in [n]\setminus A.\,$ In other words, $\textbf{1}_A(i)=1>\textbf{1}_A(j)=0.$ Every $m$-subset with $\,k\,$ inversions adds $\,q^k\,$ to the total sum $\,\binom{n}{m}_q.\,$ The Wikipedia article on Guassian binomial coefficient has more inversions details.
Given any up-down permutation $\,s\,$ on $\,[n\!+\!1]\,$ there is a unique number $\,j\in[n]\,$ such that $\,s(j\!+\!1)=n\!+\!1\,$ since $\,s\,$ is a bijection and this $\,j\,$ can not be even since if $\,j\,$ is even then that would imply $\,s(j)>n\!+\!1\,$ which is impossible. This splits the domain $\,[n\!+\!1]\,$ into three connected intervals as follows $$ [n\!+\!1]=[j]\cup\{j\!+\!1\} \cup\{j\!+\!2,\dots,n\!+\!1\}. \tag{1} $$ Because $\,s\,$ is a bijection, the image is partitioned into three sets as follows $$ [n\!+\!1]=s([j])\cup\{n\!+\!1\} \cup s(\{j\!+\!2,\dots,n\!+\!1\}). \tag{2} $$ The function $\,s\,$ restricted to the first domain is an up-down function, and restricted to the third domain is an up-down function since $\,1\,$ and $\,j\!+\!2\,$ are both odd.
The first image is a $j$-subset of $\,[n]\,$ and the third image is its complementary subset in $\,[n]\,$. The number of inversions of $\,s\,$ is the sum of the inversions contributed by the first and third images alone, then the inversions formed by the first and third images compared (included in $\,\binom{n}{j}_q\,$), and finally, the second image $\,\{n+1\}\,$ contributes $\,n-j\,$ inversions since $\,n+1\,$ is greater than all of elements in the third image. All of this is combined into the equation $$ f_{n+1}(q) = \sum_{j\; \text{odd}} \binom{n}{j}_q q^{n-j}f_j(q)f_{n-j}(q) \tag{3}$$ where $\,f_n(q)\,$ is defined to be the sum over all the up-down permutations $\,s\,$ on $\,[n]\,$ with each $\,s\,$ adding $q$ raised to the number of inversions of $\,s\,$ to the sum.