Generating functions in combinatorics topic: Pascal triangle for bivariate function

Question

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.

Answer 1

$\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.$$