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