A tutorial of reflection principle in combinatorics
Разница между en2 и en3, 61 символ(ов) изменены
###Introduction↵
A classical problem reads:↵

> Count the paths from $(0,0)$ to $(m,n)(n>m>0)$ that doesn't go through $y=x$ (the path can touch the line). One can only move up or right by $1$ in one move.↵

The problem can also be described as:↵

> Count binary strings that consist of $m$ zeros and $n$ ones $(n\ge m)$, such that in every prefix of the string, the number of zeros doesn't exceed the number of ones.↵

Consider how to count paths from $(0,0)$ to $(m,n)$ without the intersection restriction. To get to $(m,n)$, we must move up $n$ times and move right $m$ times. In other words, we need to permute $n$ right and $m$ up, whose quantity is↵

$$\displaystyle{\frac{(m+n)!}{m!n!}=\binom{m+n}{m}}$$↵

To 
count the paths that doesn't intersectfind the answer, we can try to count the paths that go through $y=x$, and this is when the reflection principle is utilized. The principle says:↵

> Given point $A,B$ at the same side of line $l$, the number of paths from $A$ to $B$ that intersect with $l$ is equal to that of paths from $A^\prime$ to $B$, where $A^\prime$ is the reflection point through $l$.↵

To show why it is correct, we should first note that a path from $A^\prime$ to $B$ must intersect with $y=x$. Say at point $P$ the path first intersect with $y=x$, we can reflect the path from $A^\prime$ to $P$ through $l$ and get a path from $A$ to $B$, and vice versa. This indicates that the intersecting paths from $A$ to $B$ and the paths from $A^\prime$ and $B$ are one-to-one corresponded, and the quantity of the two are the same.↵

![ ](/predownloaded/ea/0d/ea0dc3e241d31a95ae59db2a88f196f43da5c1ed.png)↵

Back to our problem. Going through $y=x$ is the same as intersecting with $y=x-1$ in this case, so $(0,0)$ can reflected to $(1,-1)$, and the number of intersecting path is $\binom{m+n}{m-1}$. Therefore, the answer to the problem is↵

$$\boxed{\displaystyle{\binom{m+n}{m}-\binom{m+n}{m-1}=\frac{n-m+1}{n+1}\binom{m+n}{m}}}$$↵

In particular, when $n=m$, the formula becomes↵

$$\boxed{\displaystyle{\frac{1}{n+1}\binom{2n}{n}}}$$↵

which is the **Catalan number**.↵

<spoiler summary="Note">↵
Note that there are two ways to generate valid paths in the first description when $n=m$, one keeps $x\ge y$ and the other keeps $x\le y$, so the answer is $\frac{2}{n+1}\binom{2n}{n}$.↵
</spoiler>↵

###Examples↵
[problem:26D]↵

<spoiler summary="Tutorial">↵
If one buys a ticket with only a 20 euro banknote, Charlie should use a 10 euro banknote for change. Say Charlie has served $x$ customers with only 20 euro and $y$ with only 10 euro, the inequality $y\ge x-k$ must hold to keep the process run.↵

Therefore, the not-intersected line in this question is $y=x-k-1$ and $(0,0)$ reflects to $(k+1,-k-1)$, which gives the number of good permutations as:↵

$$\displaystyle{\binom{m+n}{m}-\binom{m+n}{m-k-1}}$$↵

And the answer to this problem is:↵

$$\boxed{\displaystyle{1-\frac{\binom{m+n}{m-k-1}}{\binom{m+n}{m}}}}$$↵
</spoiler>↵

[problem:105390D]↵

<spoiler summary="Tutorial">↵
Suppose the printer does the operation 2 for $i$ times and does the operation 1 for the other $m-i$ times. Since the string only has $n$ characters, we must use $m-i-n$ operation 2 to clear extra characters. And now we have $k=i-(m-i-n)$ extra operations 2 which must be used on empty string to waste them.↵

Now we suppose the printer does $x$ operation 2 and $y$ operation 1 at some time, and we can find the same inequality $y\ge x-k$ also holds. In addition, the equality $y=x-k$ must hold at a certain time. In other words, the path must 
intersect wittouch $y=x-k$ but cannot go through it.↵

To find the answer, we first find the number of non-intersect paths, which is $\binom{n}{i}-\binom{n}{i-k-1}$, and then find the number of non-go-through paths, which is $\binom{n}{i}-\binom{n}{i-k}$. Note that our paths 
are intersects but not goes through with the line, so the number of our paths is that of non-go-through ones minus non-intersect ones, or↵

$$\boxed{\displaystyle{\binom{n}{i-k}-\binom{n}{i-k-1}}}$$↵

The problem can be easily solved by enumerating $i$ and accumulating results.↵
</spoiler>↵

[problem:2025E]↵

<spoiler summary="Tutorial">↵
Note that player 1 must have no less suit 1 cards (or trumps) than player 2, and of each other suits, player 1 must have no more cards (or non-trumps) than player 2. Particularly, player 1 uses his small trumps to ruff extra non-trumps of player 2. ↵

Say $m=2p$ and in a distribution, player 1 has $p-q_i$ cards of suit $i(i\neq1)$, so player 2 has $p+q_i$ cards. We can list $1$ or $2$ according to the cards' ranks of two players. For example, if player 1 obtains $\{3,6\}$ and player 2 obtains $\{1,2,4,5\}$, the list is $221221$. To ensure each of player 1's cards finds an opponent's distinct card whose rank is below it, the list must satisfy that in each prefix of our list, the number of $2$ must be no less than $1$.↵

Therefore, we can just substitude $m=p-q_i$ and $n=p+q_i$ into the formula above and get the number of valid distributions of this suit:↵

$$\boxed{\displaystyle{a[q_i]=\frac{2q_i+1}{p+q_i+1}\binom{2p}{p-q_i}}}$$↵

For suit 1, the formula is the same, i. e., when player 1 has $p+q_1$ trump card and player 2 has $p-q_1$, there are also $a\[q_1\]$ valid distributions.↵

Enumerate $q_1$. Since $\sum_{i=2}^n q_i=q_1$, the number of other suits' distribution is $a^{*(n-1)}\[q_1\]$, so the final answer is:↵

$$\
boxed{\displaystyle{\sum_{q=0}^pa[q]a^{*(n-1)}[q]}}$$↵
</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский zrnstnsr 2024-10-15 02:53:13 61
en2 Английский zrnstnsr 2024-10-15 02:38:05 176 (published)
en1 Английский zrnstnsr 2024-10-15 02:29:17 5579 Initial revision (saved to drafts)