анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 14 из 26

Китайская теорема об остатках. Эта теорема касается решения систе- мы уравнений вида
x = a
1
mod m
1
x = a
2
mod m
2
…
x = a
n
mod m
n
где числа m
1
, m
2
, …, m
n
попарно взаимно простые.

11.2. Комбинаторика

181
Можно доказать, что решением этой системы уравнений является
x = a
1
X
1 inv
m1
(X
1
)+ a
2
X
2 inv
m2
(X
2
) + … +a
n
X
n
inv
mn
(X
n
),
где
1 2
n
k
k
m m
m
X
m
=

В этом решении для каждого k = 1, 2, …, n
a
k
X
k
inv
mk
(X
k
) mod m
k
= a
k
,
потому что
X
k
inv
mk
(X
k
) mod m
k
= 1.
Поскольку все остальные члены суммы делятся на m
k
, они не влияют на остаток и x mod m
k
= a
k
Например, решением системы
x = 3 mod 5
x = 4 mod 7
x = 2 mod 3
является число
3 · 21 · 1 + 4 · 15 · 1 + 2 · 35 · 2 = 263.
Найдя одно решение x, мы можем получить еще бесконечно много ре- шений вида
x + m
1
m
2
… m
n
11.2. Комбинаторика
Комбинаторика изучает методы подсчета комбинаций объектов. Обычно наша цель состоит в том, чтобы эффективно подсчитать число комбина- ций, не генерируя каждую в отдельности. В этом разделе мы обсудим из- бранные комбинаторные методы, применимые к широкому кругу задач.
11.2.1. Биномиальные коэффициенты
Биномиальный коэффициент (
n
k
) – это число способов, которыми можно выбрать k элементов из множества, содержащего n элементов. Например,
(
5 3
) = 10, поскольку у множества {1, 2, 3, 4, 5} есть 10 подмножеств по 3 эле- мента:
{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5},
{1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}.

182 
Глава 11. Математика
Биномиальные коэффициенты можно вычислить, пользуясь рекуррент- ной формулой
1 1
1
n
n
n
k
k
k
−
−
  
 

=
+
  
 

−
  
 

с начальными значениями
1.
0
n
n
n
   
=
=
   
   
Чтобы понять, почему эта формула верна, рассмотрим произвольный элемент множества x. Если мы включим x в подмножество, то останется выбрать k – 1 элементов из n − 1. Если же мы не станем включать x в под- множество, то нужно будет выбрать k элементов из n − 1.
Биномиальные коэффициенты можно также вычислить по формуле:
!
!(
)!
n
n
k
k n
k
 
=
 
 
−
,
основанной на следующем рассуждении. Существует n! перестановок
n элементов. Из каждой перестановки мы включаем в подмножество пер- вые k элементов. Поскольку порядок элементов внутри и вне подмно- жества не играет роли, результат делится на k! и на (n − k)!.
Для биномиальных коэффициентов имеет место тождество
,
n
n
k
n
k
  

=
  

−
  

поскольку мы разбиваем множество n элементов на два подмножества: первое содержит k элементов, а второе – n − k элементов.
Сумма биномиальных коэффициентов равна
2 .
0 1
2
n
n
n
n
n
n
     
 
+
+
+ +
=
     
 
     
 

Название «биномиальные коэффициенты» связано с формулой возве- дения бинома (a + b)в степень n:
0 1 1 1
1 0
(
)
0 1
1
n
n
n
n
n
n
n
n
n
a
b
a b
a
b
a b
a b
n
n
−
−
 
 


 
+
=
+
+ +
+
 
 


 
−
 
 


 

Биномиальные коэффициенты входят также в треугольник Паскаля
(рис. 11.4), в котором каждое значение равно сумме двух расположенных над ним.

11.2. Комбинаторика

183
1 1
1 1
2 1
1 3
3 1
1 4
6 4
1
Рис. 11.4. Первые пять строк треугольника Паскаля
Мультиномиальные коэффициенты. Мультиномиальный коэффициент
1 2
1 2
!
,
,
,
,
!
!
!
m
m
n
n
k k
k
k k
k


=






показывает, сколькими способами множество n элементов можно разбить на подмножества размера k
1
, k
2
, …, k
m
, где k
1
+ k
2
+ … + k
m
= n. Мультиноми- альные коэффициенты можно считать обобщением биномиальных коэф- фициентов; при m = 2 эта формула превращается в формулу для биноми- альных коэффициентов.
Ящики и шары. «Ящики и шары» – полезная модель, описывающая размещение k шаровв n ящиках. Рассмотрим три случая.
Случай 1. В каждом ящике не более одного шара. Например, при n = 5 и
k = 2 существует 10 комбинаций (рис. 11.5). В этом случае число комбина- ций в точности равно биномиальному коэффициенту (
n
k
).
Рис. 11.5. Случай 1: в каждом ящике не более одного шара
Случай 2. В ящике может быть несколько шаров. Так, при n = 5 и k = 2 существует 15 комбинаций (рис. 11.6). В этом случае процесс размещения шаров в ящиках можно представить в виде строки, состоящей из симво- лов «o» и «→». Предположим, что мы начинаем с левого ящика. Символ
«o» озна чает, что мы кладем шар в текущий ящик, а символ «→» – что пе- реходим к следующему ящику. Каждое решение является строкой длины
k + n – 1, состоящей из k символов «o» и n − 1 символов «→». Так, решению в правом верхнем углу на рис. 11.6 соответствует строка «→ → o → o →».
Отсюда вытекает, что число комбинаций равно (
k+n
k
–1
).

184 
Глава 11. Математика
Рис. 11.6. Случай 2: ящик может содержать несколько шаров
Случай 3. В каждом ящике не более одного шара, и, кроме того, никакие два соседних ящика не могут содержать шары одновременно. При n = 5 и
k = 2 существует 6 комбинаций (рис. 11.7). В этом случае можно предпо- ложить, что k шаров уже размещены по ящикам и между каждыми двумя соседними ящиками находится один пустой. Наша задача – выбрать пози- ции остальных пустых ящиков. Всего таких ящиков n − 2k + 1, а позиций для них k + 1. Следовательно, по формуле, выведенной в случае 2, число решений равно (
n
n
–
–
2
k
k+
+1 1
).
Рис. 11.7. Случай 3: каждый ящик содержит не более одного шара, и никакие два соседних ящика не содержат шары одновременно
11.2.2. Числа Каталана
Число Каталана C
n
определяет, сколько существует способов правильно расставить скобки в выражении, содержащем n левых и n правых скобок.
Например, C
3
= 5, т. е. существует пять способов расставить три левые и три правые скобки:
•
()()()
•
(())()
•
()(())
•
((()))
•
(()())
Правильная расстановка скобок определяется следующими правилами:
• пустая расстановка правильна;
• если расстановка A правильна, то расстановка (A) также правильна;
• если расстановки A и B правильны, то расстановка AB также пра- вильна.

11.2. Комбинаторика

185
По-другому охарактеризовать правильные расстановки скобок можно, сказав, что если взять любой префикс такой расстановки, то левых скобок в нем будет не меньше, чем правых, а в расстановке в целом левых и пра- вых скобок поровну.
Числа Каталана можно вычислить по формуле:
1 1
0
n
n
i
n i
i
C
C C
−
− −
=
=
∑
,
которая получается, если рассмотреть способы разбиения расстановки скобок на две части, обе из которых являются правильными расстановка- ми и первая содержит минимально возможное число скобок, но при этом не пуста. Для каждого i первая часть содержит i + 1 пар скобок, и число правильных расстановок равно произведению следующих величин:
• C
i
– количество способов построить расстановку из скобок, входя- щих в первую часть без учета самых внешних скобок;
• C
n
−i−1
– количество способов построить расстановку из скобок, входя- щих во вторую часть.
Базой рекурсии является случай C
0
= 1, поскольку вообще без скобок можно построить только пустую расстановку.
Числа Каталана можно также вычислить по формуле:
2 1
,
1
n
n
C
n
n
 
=
 
 
+
которую можно объяснить так. Всего существует (
2
n
n
) способов расставить n левых и n правых скобок (необязательно правильно). Посчитаем, сколько из этих расстановок неправильны.
Если расстановка скобок неправильна, то она должна содержать пре- фикс, в котором правых скобок больше, чем левых. Идея в том, чтобы вы- брать самый короткий из таких префиксов и поменять в нем каждую скоб- ку на противоположную. Например, расстановка
())()(
имеет префикс
()) и после обращения скобок принимает вид
)((()(
. В получающейся расста- новке будет n + 1 левых и n − 1 правых скобок. На самом деле существует единственный способ получить произвольную расстановку n + 1 левых и
n − 1 правых скобок описанным выше способом. Число таких расстановок равно (
n
+
2 1
n
), именно столько существует неправильных расстановок скобок.
Следовательно, число правильных расстановок равно
2 2
2 2
2 1
1 1
1
n
n
n
n
n
n
n
n
n
n
n
n
n
  
  
 
 
−
=
−
=
  
  
 
 
+
  
  
 
 
+
+

186 
Глава 11. Математика
Подсчет деревьев. С помощью чисел Каталана можно также подсчи- тать количество некоторых древовидных структур. Прежде всего C
n
равно числу двоичных деревьев с n вершинами в предположении, что левая и правая дочерняя вершины различаются. Например, существует 5 двоич- ных деревьев с 3 вершинами, поскольку C
3
= 5 (рис. 11.8). Далее, C
n
равно числу корневых деревьев общего вида с n + 1 вершинами. На рис. 11.9 по- казано 5 корневых деревьев с 4 вершинами.
Рис. 11.8. Существует 5 двоичных деревьев с 3 вершинами
Рис. 11.9. Существует 5 корневых деревьев с 4 вершинами
11.2.3. Включение-исключение
Формула включения-исключения позволяет подсчитать размер объеди- нения множеств, если известны размеры пересечений, и наоборот. Про- стой пример ее применения дает формула
|A ∪ B| = |A| + |B| − |A ∩ B|,
где A и B – множества, а |X| обозначает размер X. Эта формула иллюстрируется на рис. 11.10. В данном случае мы хотим вычислить размер объединения
A ∪ B, которому соответствует область, принадле- жащая хотя бы одному кругу. Площадь A ∪ B можно вычислить, сложив площади A и B и вычтя из резуль- тата площадь пересечения A ∩ B.
Та же идея применима и в случае, когда множеств больше двух. В случае трех множеств формула вклю- чений-исключений имеет вид:
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|,
она иллюстрируется на рис. 11.11.
A
B
A∩ B
Рис. 11.10. Принцип включения-исключе- ния для двух мно- жеств

11.2. Комбинаторика

187
В общем случае размер объединения X
1
∪ X
2
∪ …
∪ X
n
можно вычислить, перебрав все возможные пересечения некоторых множеств X
1
, X
2
, …, X
n
Если пересечение содержит нечетное число мно- жеств, то его размер учитывается со знаком плюс, а если четное – то со знаком минус.
Аналогичные формулы существуют для вычис- ления размера пересечения по известным разме- рам объединений, например:
|A ∩ B| = |A| + |B| − |A ∪ B|
и
|A ∩ B ∩ C| = |A| + |B| + |C| − |A ∪ B| − |A ∪ C| − |B ∪ C| + |A ∪ B ∪ C|.
Подсчет беспорядков. В качестве примера подсчитаем количество
беспорядков множества {1, 2, …, n}, т. е. перестановок, не оставляющих ни одного элемента на своем месте. При n = 3 существует три беспорядка:
(2, 3, 1) и (3, 1, 2).
Один из подходов к решению задачи основан на формуле включений- исклю чений. Обозначим X
k
множество перестановок, в которых элемент k
находится в позиции k. При n = 3 эти множества таковы:
X
1
= {(1, 2, 3), (1, 3, 2)},
X
2
= {(1, 2, 3), (3, 2, 1)},
X
3
= {(1, 2, 3), (2, 1, 3)}.
Число беспорядков равно
n
! − |X
1
∪ X
2
∪ … ∪ X
n
|,
поэтому достаточно вычислить |X
1
∪ X
2
∪ … ∪ X
n
|. Благодаря формуле вклю- чений-исключений эта задача сводится к вычислению размеров пере- сечений. Кроме того, пересечение c различных множеств X
k
содержит
(n − c)! элементов, потому что состоит из всех перестановок, в которых c
элементов находятся на своих местах. Следовательно, размеры пересече- ний легко вычисляются. Например, при n = 3
|X1 ∪ X2 ∪ X3| = |X1| + |X2| + |X3|
− |X1 ∩ X2| − |X1 ∩ X3| − |X2 ∩ X3|
+ |X1 ∩ X2 ∩ X3|
= 2 + 2 + 2 − 1 − 1 − 1 + 1
= 4,
так что число беспорядков равно 3! − 4 = 2.
Но эту задачу можно решить и без формулы включений-исключений.
Обозначим f(n)количество беспорядков множества {1, 2, …, n}. Можно вос- пользоваться следующей рекуррентной формулой:
Рис. 11.11. Принцип включения-исключения для трех множеств
A
B
C
A ∩ B
A ∩ C
B ∩ C
A ∩ B ∩ C

188 
Глава 11. Математика
⎧0
n
= 1
f(n) =
⎨
1
n
= 2.
⎩(n − 1)(f(n − 2) + f(n − 1))
n
> 2
Для доказательства этой формулы рассмотрим, где может оказаться эле- мент 1 в беспорядке. Существует n − 1 способов выбрать элемент x, кото- рый займет место элемента 1. В каждом случае есть два варианта.
Вариант 1: элемент x переставляется с элементом 1. Тогда остается по- строить беспорядок из n − 2 элементов.
Вариант 2: элемент x переставляется с элементом, отличным от 1. Тог- да нужно построить беспорядок из n − 1 элементов, потому что мы не можем переставить x на место элемента 1, а все остальные эле- менты должны быть переставлены.
11.2.4. Лемма Бёрнсайда
Лемму Бёрнсайда можно использовать для подсчета различных комби- наций таким образом, что симметричные комбинации учитываются толь- ко один раз. Лемма утверждает, что число таких комбинаций равно
1 1
( ),
n
k
c k
n
=
∑
где n – число способов изменить положение комбинации, а c(k) – число комбинаций, оставшихся неизменными после применения k-го способа.
В качестве примера вычислим количество ожерелий с n жемчужинами
m возможных цветов. Два ожерелья считаются симметричными, если они переходят друг в друга в результате поворота. На рис. 11.12 показаны че- тыре симметричных ожерелья, учитываемых при подсчете как одна ком- бинация.
Рис. 11.12. Четыре симметричных ожерелья
Существует n способов изменить положение ожерелья, поскольку его можно повернуть на k = 0, 1, …, n − 1 шагов по часовой стрелке. Например, при k = 0 ни одно из m
n
ожерелий не меняется, а при k = 1 не меняются только m ожерелий, в которых все жемчужины одного цвета. В общем слу- чае не меняются m
gcd(k,n)
ожерелий, поскольку участки соседних жемчужин длины gcd(k, n)становятся на место друг друга. Поэтому, согласно лемме
Бёрнсайда, количество различных ожерелий равно

11.2. Комбинаторика

189
1
gcd( , )
0 1
n
k n
k
m
n
−
=
∑
Так, число различных ожерелий с 4 жемчужинами 3 цветов равно
4 2
3 3 3 3
24.
4
+ +
+
=
11.2.5. Теорема Кэли
Теорема Кэли утверждает, что существует всего n
n
–2
различных помечен- ных деревьев с n вершинами. Вершины помечаются числами 1, 2, …, n, а два дерева считаются различными, если они отличаются структурой или пометкой. Например, при n = 4 существует 4 4–2
= 16 помеченных деревьев, все они показаны на рис. 11.13.
1 2
3 4
2 1
3 4
3 1
2 4
4 1
2 3
1 2
3 4
1 2
4 3
1 3
2 4
1 3
4 2
1 4
2 3
1 4
3 2
2 1
3 4
2 1
4 3
2 3
1 4
2 4
1 3
3 1
2 4
3 2
1 4