$1,2,...,n(n+1)/2$ placed at random in bottom-heavy nxn triang. array. Prob. that largest num in every row is smaller than largest in any row below? From the 1990 Canada National Olympiad: 

$\dfrac{n(n+1)}{2}$ distinct numbers are arranged at random into $n$ rows. 
The first row has
  $1$ number, the second has $2$ numbers, the third has $3$ numbers and so on. Find
  the probability that the largest number in each row is smaller than the largest
  number in each row with more numbers.

The conclusions I have reached so far:


*

*it is almost impossible to start from the top of the array, without knowing something about the distribution of numbers below (it is possible to meet the conditions for the first row even if it contains a number as large as $n$, whereas it is certain if it contains $1$)

*working from the bottom up, one can see that the last row must contain the number $\dfrac{n(n+1)}{2}$ if the condition is to be met

 A: Let $p_n$ be the probability that this array meets the desired conditions.  Then we note that for $p_{n+1}$, we need $\frac{(n + 1)(n+2)}{2}$ to be in the last row, and that the first $n$ rows satisfy the desired conditions.  Thus, we have $$p_{n+1} = \mathbb{P}\left(\frac{(n + 1)(n+2)}{2}\text{ is in the last row}\right)p_n.$$
Since the last row has $n+1$ elements, and there are a total of $\frac{(n+1)(n+2)}{2}$ elements, we have $$ \mathbb{P}\left(\frac{(n + 1)(n+2)}{2}\text{ is in the last row}\right) = \frac{2}{n+2}.$$
We also note that $p_1 = 1$.  Thus, we have \begin{align} p_{n+1} &= \frac{2}{n + 2}p_n \\
&= \frac{2^2}{(n + 2)(n + 1)}p_{n - 1} \\
&= \frac{2^n}{(n+2)(n+1)\cdots 3}\cdot p_1 \\
&= \frac{2^{n+1}}{(n+2)!}.
\end{align}
Thus, we have $p_n = \frac{2^n}{(n+1)!}$.  The combinatorialist in me feels like there should be a quick, direct proof of this fact, but I can't come up with one; in the meantime, I think this recursive method works.
A: Let $T_r:=\frac{r(r+1)}{2}$ for every $r=0,1,2,\ldots$.  We are counting the number of ways to arrange the numbers on this triangular array so that the largest number on each row is smaller than that of the next.  
On the $n$-th row of the triangular array, the number $T_n$ must be there, and $n-1$ other numbers are chosen from $T_n-1$ numbers.  Hence, there are $n!\cdot \binom{T_n-1}{n-1}$ ways to choose and arrange elements of the $n$-th row.  For $k=1,2,\ldots,n-1$, we have $T_{n-k}$ elements left, and the largest of them must be on the $(n-k)$-th row, and $n-k-1$ other entries of this row must be picked from $T_{n-k}-1$ remaining numbers.  Hence, there are $(n-k)!\cdot\binom{T_{n-k}-1}{n-k-1}$ ways to choose and arrange elements for the $(n-k)$-th row.  That is, the number of ways to assign elements into the triangular array according to the rule is 
$$\begin{align}
\prod_{k=0}^{n-1}\,\left((n-k)!\cdot \binom{T_{n-k}-1}{n-k-1}\right)
&=\prod_{k=0}^{n-1}\,\left(\frac{n-k}{T_{n-k}}\cdot\frac{T_{n-k}!}{T_{n-k-1}!}\right)=T_n!\,\prod_{k=0}^{n-1}\,\left(\frac{n-k}{T_{n-k}}\right)
\\
&=T_n!\,\prod_{k=0}^{n-1}\,\left(\frac{2}{n-k+1}\right)=T_n!\,\left(\frac{2^n}{(n+1)!}\right)\,.
\end{align}$$
Thus, the probability of getting this type of arrangements is $\frac{2^n}{(n+1)!}$.
