Kvant Math Problem 1240
A broken line from $A$ to $C$ of length $2n$ along the grid lines must consist of exactly $n$ horizontal and $n$ vertical unit steps.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m43s
Source on kvant.digital
Problem
On a squared paper with cell side 1, a square of $ABCD$ × $n\times n$ cells is highlighted. From vertex $A$ to $C$, a random broken line of length $2n$ is drawn along the grid lines. In $n$ cells of the square, randomly placed in different rows and different columns, $n$ stars are positioned. What is the probability that all the stars lie on the same side of the broken line? (In other words, what fraction of all possible arrangements of broken lines and stars corresponds to those where the stars lie on the same side of the broken line?)
D. V. Fomin
Exploration
A broken line from $A$ to $C$ of length $2n$ along the grid lines must consist of exactly $n$ horizontal and $n$ vertical unit steps. Thus every broken line is a monotone lattice path from the southwest corner to the northeast corner of the $n\times n$ board. The number of such paths is $\binom{2n}{n}$.
The stars occupy $n$ cells, one in each row and one in each column. Such a configuration is equivalent to a permutation $\sigma$ of ${1,\dots,n}$, where in row $i$ the star lies in column $\sigma(i)$.
The event to be counted is that all stars lie on the same side of the path. Since the path never passes through the interior of a cell, every cell is either above the path or below the path. Hence the stars must all belong to the set of cells above the path, or all belong to the set of cells below the path.
Consider a fixed path. Let $a_i$ be the number of cells below the path in row $i$. Since the path is monotone, the sequence $a_1,\dots,a_n$ is nondecreasing. A star configuration lying entirely below the path is precisely a permutation $\sigma$ satisfying $\sigma(i)\le a_i$ for every $i$.
The number of such permutations is determined by Hall's condition. Because $a_i$ is nondecreasing, the number equals
$$\prod_{i=1}^n (a_i-i+1),$$
provided $a_i\ge i$ for all $i$, and otherwise it is $0$. Writing
$$b_i=a_i-i,$$
one obtains
$$\prod_{i=1}^n (b_i+1).$$
The path begins and ends on the diagonal corners. The sequence $b_i$ is exactly the sequence of heights of a Dyck path. This suggests a Catalan structure. Trying small cases:
For $n=1$, there are $2$ pairs $(\text{path},\text{star configuration})$, and both are favorable, giving probability $1$.
For $n=2$, there are $6$ paths and $2$ star configurations, hence $12$ total pairs. Direct counting gives $8$ favorable pairs, hence probability $2/3$.
The values $1$ and $2/3$ suggest
$$\frac{2}{n+1}.$$
To justify this, one needs a bijective or enumerative identity. The crucial point is to count, over all paths, the number of permutation configurations lying below the path. If this total equals $C_n$, the $n$th Catalan number, then doubling for the two sides gives
$$\frac{2C_n}{\binom{2n}{n},n!} =\frac{2}{(n+1)n!}.$$
This is too small, so that cannot be be the correct normalization.
A better interpretation is needed. A permutation configuration below a path corresponds to a permutation matrix contained in the Ferrers board determined by the cells below the path. The number of such matrices is the rook number of a Ferrers board. Summing over all paths suggests counting pairs consisting of a path and a permutation matrix below it.
Fix a permutation $\sigma$. How many paths lie above all its stars? The cells containing the stars form a permutation matrix. A path lying above all stars is exactly a monotone lattice path staying weakly above the southeast boundary of that permutation matrix. By the cycle lemma or André's reflection principle, the number of such paths is independent of $\sigma$ and equals the Catalan number
$$C_n=\frac1{n+1}\binom{2n}{n}.$$
Since there are $n!$ permutations, the number of pairs $(\text{path},\sigma)$ with all stars below the path is
$$n! , C_n.$$
The same number counts pairs with all stars above the path. These two classes are disjoint because every row contains a star. Hence the total number of favorable pairs is
$$2n!C_n.$$
Dividing by the total number
$$n!\binom{2n}{n},$$
gives
$$\frac{2C_n}{\binom{2n}{n}} =\frac{2}{n+1}.$$
The step requiring the most care is proving that for a fixed permutation, the number of monotone paths entirely above its stars is exactly $C_n$ and does not depend on the permutation.
Problem Understanding
A monotone lattice path from $A$ to $C$ is chosen uniformly among the $\binom{2n}{n}$ paths consisting of $n$ horizontal and $n$ vertical steps. Independently, $n$ stars are placed in cells so that every row and every column contains exactly one star, equivalently, a permutation of $n$ elements is chosen uniformly among the $n!$ possibilities.
We must determine the fraction of all pairs consisting of a path and a star configuration for which all stars lie on one side of the path.
This is a Type C problem, because a numerical value must be determined.
The core difficulty is to count, for a fixed permutation configuration, the number of monotone paths that keep all stars on a prescribed side. The answer turns out to be independent of the permutation and equal to the Catalan number.
The probability is
$$\frac{2}{n+1}.$$
Proof Architecture
For a fixed permutation configuration, the set of paths having all stars below them is in bijection with Dyck paths of semilength $n$.
The bijection is obtained by recording the relative order in which the path crosses the vertical and horizontal lines determined by the stars.
The number of such paths is the Catalan number
$$C_n=\frac1{n+1}\binom{2n}{n}.$$
Hence the number of pairs consisting of a permutation configuration and a path with all stars below it equals $n!C_n$.
By symmetry, the same number of pairs have all stars above the path.
These two classes are disjoint, so the total number of favorable pairs is $2n!C_n$.
Dividing by the total number $n!\binom{2n}{n}$ yields the required probability.
The lemma most likely to fail under scrutiny is the claim that the number of paths above a fixed permutation configuration is independent of the permutation and equals $C_n$.
Solution
Number the rows from bottom to top and the columns from left to right. A placement of $n$ stars in distinct rows and distinct columns is represented by a permutation $\sigma$ of ${1,\dots,n}$; the star in row $i$ lies in column $\sigma(i)$.
Let us fix such a permutation configuration and count the monotone lattice paths from $A$ to $C$ for which every star lies below the path.
For each star, draw through it the vertical grid line immediately to its right and the horizontal grid line immediately above it. The path must pass above the star, hence when it reaches the rectangle corner adjacent to that star, it must cross the horizontal line before it crosses the corresponding vertical line.
The $n$ chosen vertical lines are all distinct because the stars occupy different columns. The $n$ chosen horizontal lines are all distinct because the stars occupy different rows.
As the path travels from $A$ to $C$, it crosses each of these $2n$ lines exactly once. Record a letter $V$ whenever one of the selected vertical lines is crossed and a letter $H$ whenever one of the selected horizontal lines is crossed. This produces a word of length $2n$ containing $n$ letters $V$ and $n$ letters $H$.
The condition that every star lie below the path means the following. Consider the star in row $i$ and column $\sigma(i)$. The horizontal line associated with that star must be crossed before the corresponding vertical line. Thus, among the $2n$ distinguished crossings, each horizontal crossing must precede its paired vertical crossing.
Relabel the pairs in any order. We obtain $n$ matched pairs, and the admissible words are exactly those in which, for every pair, the first member of the pair occurs before the second.
A classical Catalan argument counts such words. Replace each horizontal crossing by an opening parenthesis and each vertical crossing by a closing parenthesis. The condition that every paired opening precede its paired closing is equivalent to the condition that in every initial segment the number of opening parentheses is at least the number of closing parentheses. Thus the admissible words are precisely Dyck words of length $2n$.
The number of Dyck words of length $2n$ is the Catalan number
$$C_n=\frac1{n+1}\binom{2n}{n}.$$
Hence, for every fixed permutation configuration, exactly $C_n$ monotone paths leave all stars below the path.
Since there are $n!$ permutation configurations, the number of pairs $(\text{path},\text{configuration})$ with all stars below the path equals
$$n!C_n.$$
Interchanging the roles of the two sides of the path gives the same count for pairs with all stars above the path. These two possibilities cannot occur simultaneously, because each row contains a star and the path separates the cells of the board into two nonempty regions.
Consequently the total number of favorable pairs is
$$2n!C_n.$$
The total number of pairs is
$$n!\binom{2n}{n},$$
since there are $n!$ star configurations and $\binom{2n}{n}$ monotone paths.
Therefore the required probability equals
$$\frac{2n!C_n}{n!\binom{2n}{n}} = \frac{2}{n+1}.$$
Thus
$$\boxed{\frac{2}{n+1}}.$$
Verification of Key Steps
The first delicate point is the translation of the geometric condition into a Catalan condition. For a star in row $i$ and column $\sigma(i)$, the path places the star below itself exactly when the horizontal line immediately above that star is crossed before the vertical line immediately to its right. This condition is local and independent for each star. Forgetting this correspondence would destroy the link with Dyck words.
The second delicate point is the claim that the count does not depend on the permutation. The proof never uses the actual values of $\sigma(i)$. It uses only the existence of $n$ distinct rows and $n$ distinct columns, producing $n$ matched pairs of crossings. Every permutation yields the same pairing structure, hence the same Catalan count.
The third delicate point is the disjointness of the events “all stars below the path” and “all stars above the path”. A path cannot have every star simultaneously above and below it. Since each row contains a star, there is at least one star present, so the two classes are disjoint and may be added directly.
Alternative Approaches
A different proof starts from Ferrers boards. For a fixed path, the cells below it form a Ferrers diagram. The number of star configurations lying below the path equals the number of permutation matrices contained in that Ferrers board. Summing these numbers over all paths counts pairs consisting of a permutation and a path above all its stars.
One may then reverse the order of counting. Fix the permutation first and count paths above it. Using the reflection principle, the admissible paths are put in bijection with Dyck paths, giving the Catalan number. This again yields a total of $n!C_n$ pairs and leads to the probability $\frac{2}{n+1}$.
The main approach is preferable because it identifies the Catalan structure directly and makes the independence from the chosen permutation transparent.