A tutorial of reflection principle in combinatorics

Правка en2, от zrnstnsr, 2024-10-15 02:38:05

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 intersect, 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.

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.

Note

Examples

26D - Tickets

Tutorial

105390D - String From Another World

Tutorial

2025E - Card Game

Tutorial
Теги combinatorics

История

 
 
 
 
Правки
 
 
  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)