grandes-ecoles 2019 Q36

grandes-ecoles · France · centrale-maths1__psi Permutations & Arrangements Permutation Properties and Enumeration (Abstract)
In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), an algorithm constructs a permutation of $S_{n}$ from an outcome of $n$ draws as follows:
  • We start with the sequence $(0,1,0)$ after the first draw.
  • For any $k \in \llbracket 2, n \rrbracket$, if on the $k$-th draw we draw a white ball (respectively black ball) numbered $p$, we insert the value $k$ in the sequence in the middle of the $(p+1)$-th ascent (respectively descent).
  • At the end, we remove the two 0's from the list.

Using the algorithm above, construct the permutation of $S_{5}$ associated with the outcome $(B_{0}, B_{0}, N_{1}, N_{0}, B_{2})$.
In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), an algorithm constructs a permutation of $S_{n}$ from an outcome of $n$ draws as follows:
\begin{itemize}
  \item We start with the sequence $(0,1,0)$ after the first draw.
  \item For any $k \in \llbracket 2, n \rrbracket$, if on the $k$-th draw we draw a white ball (respectively black ball) numbered $p$, we insert the value $k$ in the sequence in the middle of the $(p+1)$-th ascent (respectively descent).
  \item At the end, we remove the two 0's from the list.
\end{itemize}

Using the algorithm above, construct the permutation of $S_{5}$ associated with the outcome $(B_{0}, B_{0}, N_{1}, N_{0}, B_{2})$.