I am currently studying and tyring to understand the proof of the derangement of descent sets, and in this particular paper:
http://emis.ams.org/journals/EJC/Volume_16/PDF/v16i1r32.pdf
I am reading the proof to the theorem 2.3 (on page 5). I am stuck at understanding few parts to the proof of theorem 2.3:
Question 1: Why is $\binom{n}{a_1,....,a_k}$ the coefficient of the expansion $$1+(\sum x_i)+(\sum x_i)^2+\cdots, \text{furthermore why is }1+(\sum x_i)+(\sum x_i)^2+\cdots=\frac{1}{1-x_1-\cdots-x_k}$$
Question 2: How come the identity $|D_j(\alpha)|=|D_j(\alpha)|+|D_j(a_1,...,a_{j-1},a_j-1,a_{j+1},...a_k)|$ hold, furthermore how did this lead to the recursion $F_{j-1}(\mathbb{x})=(1+x_j)F_j(\mathbb{x})?$
I would really appreciate some clear clarification to why the above holds, as I just cant seem to understand why it is the case. Thank you in advance.
$\newcommand\x{\boldsymbol{x}}$ The following is my soft interpretation of the part of the paper in question. Please see the link in the question for more details.
First off it is a good idea to establish some meaning of the generating function
$$F_0(\x)=\frac{1}{1-\sum_{j=1}^{k}x_j}=1+\left(\sum_{j=1}^{k}x_j\right)+\left(\sum_{j=1}^{k}x_j\right)^{\!\!2}+\cdots$$
in this context.
To understand this let's look at just one of the terms
$$\left(\sum_{j=1}^{k}x_j\right)^{\!\!n}$$
which has the interpretation of distributing the $n$ elements of $[n]$ into $k$ subsets $A_1,\ldots,A_k$. Each successive factor $x_1+x_2+\cdots+x_k$ in the product $(x_1+x_2+\cdots+x_k)^n$ represents the possible assignment of each successive element of $[n]$ to the $k$ subsets.
So, the coefficient of $x_1^{a_1}\cdots x_k^{a_k}$ in the expansion of this term is $n!/(a_1!\cdots a_k!)$ which is the number of ways to distribute elements of $[n]$ into $k$ subsets (or blocks) $A_1,\ldots,A_k$ of respective sizes $a_1,a_2,\ldots, a_k$.
In the paper these blocks always have elements of $[n]$ in descending order left to right within each block. Also, the blocks and themselves appear in left-to-right order $A_1,A_2,\ldots,A_k$, therefore displaying as a permutation of $[n]$. These permutations of $[n]$ clearly have descents between adjacent pairs of the first $a_1$ elements elements, the next $a_2$ elements and so forth. The only possible ascents positions being between $a_1$ and $a_1+1$, $a_2$ and $a_2+1$ etc.
So we see that $(x_1+x_2+\cdots+x_k)^n$ is interpreted by the paper as generating permutations of $[n]$ with descents in the aforementioned prescribed positions. Hence $F_0(\x)$ generates all such permutations for all possible $n$. Granted it only really makes sense for terms $n\ge k$ otherwise there are more blocks than elements but we will not concern ourselves with that here.
The paper calls another (as yet unknown) generating function $F_j(\x)$ which generates permutations of a given block type $A_1,A_2,\ldots,A_k$ with no fixed points in blocks $A_1$ to $A_{j}$. It is important to note that any descending block $A_j$ can have at most 1 fixed point simply because it is descending. It is also worth noting that the permutations generated by $F_j(\x)$ include those with no fixed points in blocks $A_{j+1}$ to $A_k$ (i.e. derangements) and all permutations with their fixed point combinations only in blocks $A_{j+1}$ to $A_k$.
The paper establishes a lovely bijection which takes any permutation length $n$ of type $x_1^{a_1}\cdots x_k^{a_k}$ generated by $F_{j}(\x)$ and inserts a fixed point in block $A_{j}$ to give a permutation length $n+1$. Since such a permutation has a fixed point in block $A_j$ it must be generated by $F_{j-1}(\x)$ and it is represented by the contribution $x_jF_j(\x)$ to $F_{j-1}(\x)$. But, of course, a length $n+1$ permutation generated by $F_{j-1}(\x)$ may also include all of the length $n+1$ permutations generated by $F_j(\x)$, as these have no fixed points in blocks $A_1$ to $A_j$, this adds a contribution $F_j(\x)$ to $F_{j-1}(\x)$.
Hence, to summarise, we have described permutations length $n+1$ that have either no fixed points or fixed points in blocks to the right of $A_{j-1}$ (these are generated by $F_{j-1}(\x)$) as the sum of permutations length $n+1$ that have a leftmost fixed point in block $A_j$ (generated by $x_jF_{j}(\x)$) and permutations of length $n+1$ that either have no fixed points or fixed points in blocks to the right of $A_j$ (generated by $F_{j}(\x)$). Or simply:
$$F_{j-1}(\x)=F_j(\x)+x_jF_j(\x)=(1+x_j)F_j(\x)\, .$$
Iterating:
$$F_0(\x)=(1+x_1)(1+x_2)\cdots(1+x_j)F_j(\x)\, .$$
This gives:
$$\begin{align}F_j(\x)&=\frac{F_0(\x)}{(1+x_1)(1+x_2)\cdots(1+x_j)}\\[1ex]&=\frac{F_0(\x)}{(1+x_1)(1+x_2)\cdots(1+x_j)\left(1-\sum_{j=1}^{k}x_j\right)}\end{align}$$
The result of Theorem 2.1 is a special case of this for $j=k$:
$$\begin{align}F_k(\x)&=\frac{F_0(\x)}{(1+x_1)(1+x_2)\cdots(1+x_k)}\\[1ex]&=\frac{1}{(1+x_1)(1+x_2)\cdots(1+x_k)\left(1-\sum_{j=1}^{k}x_j\right)}\end{align}$$
this is the generating function for permutations with no fixed points and descents in at least the aforementioned prescribed positions.