Consider the product
$A_n = \left\{1\right\} \times \left\{1,2\right\} \times \cdots \times \left\{1,2,\ldots,n\right\}$.
For $\sigma = (a_1, a_2, . . . , a_n) \in A_n$, define the set of descents
$\operatorname{Des}(\sigma) := \left\{ i \in [n − 1] :
a_i \geq a_{i+1} \right\}$ of $\sigma$.Prove that the number of sequences $\sigma \in A_n$ having descent set $\operatorname{Des}(\sigma) = S$ is equal to the number of permutations $w \in S_n$ having descent set $\operatorname{Des}(w) = S$ for every $ S \subseteq [n − 1]$.
Idea: I have to create an one to one function. I have an idea but don't know how to describe it and prove it. So I'll give an example.
{1,1,3,2,4} $\in A_n$
$a_1=a_2$ so it's a decent
(-, -, -, -, 1)
The next descent is
$a_3>a_4$
(-,-,2,3,1)
Then we don't find anymore descents so we end up with
(4,5,2,3,1)
Best Answer
Given $a \in A_n$, define a permutation $\pi_a$ of $\{1,\dots,n\}=[n]$ as follows:
First, let $\pi_a(n)=a_n$. If $1 \le k<n$ and $\pi_a(k+1),\dots,\pi_a(n)$ have been defined, let $\pi_a(k)$ be the $a_k$th smallest element of $[n]\setminus\{\pi_a(k+1),\dots,\pi_a(n)\}$.
For example, if $n=5$ and $a=(1,1,3,4,2)$, then $\pi_a=(3,1,4,5,2)$. If $a=(1,2,1,4,5)$ then $\pi_a=(2,3,1,4,5)$. If $a=(1,1,1,1,1)$ then $\pi_a=(5,4,3,2,1)$.
The mapping $a \to \pi_a$ is a bijection from $A_n$ to the permutations of $[n]$.
It is easy$^{(*)}$ to check that $k$ is a descent of $\pi_a$ iff $k$ is a descent of $a$. This implies the required identity.
$(*)$ Indeed, let $$[n]\setminus\{\pi_a(k+2),\dots,\pi_a(n)\}= \{r_1,\dots,r_{k+1}\}, \; \text{where} \; r_1<\cdots<r_{k+1} \,.$$
If $k$ is a descent for $a$, that is, $a_k \ge a_{k+1}$, then $\pi(k)=r_{1+a_k} > r_{a_{k+1}}=\pi(k+1)$.
On the other hand, if $a_k < a_{k+1}$, then $\pi(k)=r_{a_k} <r_{a_{k+1}}=\pi(k+1)$.