# Generating functions in combinatorics topic: Pascal triangle for bivariate function

Let $$\displaystyle \left[\frac{n}{k}\right]$$ a combinatorial element meaning the number of permutations with exactly $$k$$ increasing sequences. Find a Pascal Triangle type recurence formula for the combinatorial element. Source: Theoretical Algorithmics and Mathematical Computer Science European Contest (TAMCSEC) 2011

Background and motivation:

I have found this problem related to the topic Generating Functions in a textbook in Combinatorics. Even though I have some (but not very advanced) training in this topic, especially in the theoretical field (definitions, relations, properties of both $$\text{ordgen}$$ and $$\text{expgen}$$, with formulae for manipulating different sequences, as well as knowledge of Differential Calculus topics needed here - series expansions especially). However, I did not encouner any problem of this type so far related to generating functions. I am searching for a solution related with the topic of generating function, as well as some explanations connecting this theoretical topic with combinatorics.

Edit: I am also familiar with normal combinatorial elements (binomials and multinomials, arrangements, including Pascal recursivity) and with some info about permutations and there properties in combinatorics and probability.

• Can you be more explicit about what you mean by "$k$ increasing sequences"? Must they be consecutive, or not? For example, does $\pi=[1,2,5,6,3,4,7,8]$ have exactly $2$ increasing sequences (namely $1,2,3,4$ and $5,6,7,8$), or does it have $4$ increasing sequences (namely $[1,2]$, $[5,6]$, $[3,4]$ and $[7,8]$)? Commented Mar 17, 2022 at 1:32
• @MikeEarnest Consecutive blocks Commented Mar 17, 2022 at 5:35
• Exactly $k$ increasing runs means exactly $k-1$ descents, and vice versa. So, check Eulerian numbers. Commented Mar 17, 2022 at 23:45

#### $$\displaystyle \left[\frac{n}{k}\right]=(n-k+1)\left[\frac{n-1}{k-1}\right]+k\left[\frac{n-1}{k}\right]$$ for $$1\le k\le n$$

$$\left[\frac{n}{k}\right]$$ is the same as the Eulerian number $$A(n, k-1)$$, as Alexander Burstein points out. While $$\left[\frac n0\right]=\left[\frac {n-1}{n}\right]=0$$ if $$n\gt0$$ by definition, we stipulate $$\left[\frac00\right]=1$$.

Since $$A(n,m) = (n-m)A(n-1,m-1)+(m+1)A(n-1,m)$$ for $$1\le m\le n-1$$ as mentioned in the Wikipedia article, we have, for $$2\le k\le n$$, \begin{aligned} \left[\frac{n}{k}\right]&=A(n,k-1)\\ &=(n-k+1)A(n-1,k-2)+kA(n-1,k-1)\\ &=(n-k+1)\left[\frac{n-1}{k-1}\right]+k\left[\frac{n-1}{k}\right] \end{aligned} This is the wanted "Pascal Triangle type recurrence formula".

#### A simple direct proof

Given a sequence, let us call a consecutive increasing subsequence that cannot be extended to a longer consecutive increasing subsequence a block of the given sequence. $$\left[\frac{n}{k}\right]$$ is the number of permutations of $$(1,2,\cdots,n)$$ with $$k$$ blocks.

Note that every permutation of $$(1,2,\cdots, n)$$ can be obtain from a permutation of $$(1,2,\cdots, n-1)$$ by inserting $$n$$ somewhere.

• If $$n$$ is inserted right after the end of a block, the number of blocks will not change.

• Otherwise, $$n$$ is inserted elsewhere, i.e.,

• inside some block, in which case that block will split into two blocks;
• or at the very front of the whole permutation, in which case $$n$$ itself forms a new block.

The number of blocks will increase by $$1$$.

So, to obtain permutations of $$1,2,\cdots,n$$ with $$k$$ blocks, we can

• either insert $$n$$ right after the end of one of $$k$$ blocks of a permutation of $$1,2\cdots,n-1$$ with $$k$$ blocks,
• or insert $$n$$ at one of all $$n$$ positions except right after the end of one of $$k-1$$ blocks of a permutation of $$1,2,\cdots, n-1$$ with $$k-1$$ blocks.

Combining the two cases above, we obtain $$\left[\frac{n}{k}\right]=k\left[\frac{n-1}{k}\right]+(n-(k-1))\left[\frac{n-1}{k-1}\right]\quad \forall 1\le k\le n.$$