Counting of permutations (possibly) related to Euler number I got a question which is somehow related to Euler's number in combinatorics, but I do not know how to make a formal connection.
Definition: Given numbers from 1 to $n$, let $G(n,k)$ denote the number of permutations such that the permutation can be decomposed into $k$ groups, $G_1, \cdots, G_k$, where in each $G_i$, $min(G_i)$ is the rightmost one, and $min(G_1)<min(G_2)< \cdots < min(G_k)$.
For instance,

*

*for $n=3$ and $k=1$, it could be $(3, 2,1)$ or $(2,3,1)$

*for $n=3$ and $k=2$, it could be $(3, 1,2)$ or $(2, 1, 3)$ or $(1, 3, 2)$

*for $n=3$ and $k=3$, it could be $(1, 2,3)$
As a result, $G(3,1)=2, G(3,2)=3$ and $G(3,3)=1$
I want to compute $\sum_{k=1}^n k\cdot G(n,k)$ for a given $n$.
My attempt: Interestingly enough, some small example suggests that this is actually $(\sum_{k=1}^n 1/k)\cdot n!$.
My question is whether there is an expression for $G(n,k)$ or $\sum_{k=1}^n k\cdot G(n,k)$?
 A: There is a linear recurrence that can be derived for $G(n,k)$.
Let us see how to insert the element $'n+1'$ into such a permutation. If $'n+1'$ is part of a seperate block, it is forced to be the rightmost element of the permutation and the rest of the $n$ elements have to form a permutation that is counted in $G(n,k-1)$.
Otherwise, $'n+1'$ can be inserted in any of the blocks $G_i$ where it can be any element but the rightmost one in the block. Say, $312$ is our permutation, then $4$ can be inserted either in one of the following spaces:
$$\large{\_312,3\_12,31\_2}$$
Therefore, we would get
$$G(n+1,k)=G(n,k-1)+nG(n,k).$$
Of course, for any recurrence, we need to specify the initial values which you have provided.
$$G(3,0)=0,G(3,1)=2, G(3,2)=3 \text{ and }G(3,3)=1.$$
This should allow us to calculate the values of $G(n,k)$ for $n\geqslant 4,k \geqslant 0$.
Therefore, $G(n,k)$ turns out to be the unsigned Stirling numbers of the first kind.
We can calculate the generating function using this recurrence and that turns out to be $$\sum\limits_{k=0}^{n}G(n,k)x^k=x(x+1)\cdots(x+n-1).$$
From this, $$\sum\limits_{k=0}^{n}kG(n,k)=\dfrac{d\big(\sum\limits_{k=0}^{n}G(n,k)x^k \big)}{dx} \Bigg\vert_{x=1}=n!(1+\frac{1}{2}+\cdots+\frac{1}{n})$$
A: Indeed, $G(n,k)$ is equal to the Stirling number of the first kind $n \brack k$, or $S_1(n,k)$. An equivalent definition for $G(n,k)$ is "the number of permutations of $\{1,\dots,n\}$ which have $k$ running minima", where a running minimum of a permutation is defined to be an entry which is smaller than all of the numbers which come after it. On the other hand, the Stirling numbers of the first kind are the number of permutations of $n$ with $k$ cycles.
To prove $G(n,k)={n\brack k}$, it suffices to find a bijection on permutations which takes a permutation with $k$ cycles to one with $k$ running minima. For this purposes, the canonical cycle representation of a permutation suffices (brief mention on wikipedia). Given a permutation with $k$ cycles, write all of those cycles with their smallest element last, and then concatenate them together in increasing order of their last elements. For example, the permutation defined by $1\to 5\to7\to 1$, $2\to 3\to 2$, $4\to 4$, $5\to 8\to 5$, would be written
$$
(5,7,1)\,(3,2)\,(4)\,(8,5)
$$
The key step is then to realize the parentheses are unnecessary; if you delete the parentheses, you can still tell where they were, since a break occurs after every running minimum. The result is
$$
5,7,1,3,2,4,8,5
$$
This is a permutation with four running minima, namely $1,2,4,5$. This is the bijection; the initial permutation had four cycles, the final had four running minima.
A: It is not a complete answer, but suddenly it occurs to me this is essentially Stirling number of the first kind.
https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
