Комбинаторика 2

Ноя 16 2014

Лекция «Комбинаторика-2.»

Практически вся эта лекция будет посвящена разнообразным свойствам особых чисел, называемых попросту «цэшками», а по-научному числами сочетаний. Эти числа, обозначаемые стандартно Сnk, уже появлялись в первой лекции «Комбинаторика». Напомним их определение основную формулу:
Сnk — это число способов выбрать k различных (т.е. без повторений) предметов из n различных (0<=k<=n), без учета порядка выбора. Они могут быть вычислены по следующим формулам:
Сnk=Ank/k!
Cnk=(n*(n-1)*(n-2)*…*(n-k+1))/k!
Cnk=n!/(k!*(n-k)!)

Доказательства всех этих формул и определение чисел Ank вы можете прочитать в лекции «Комбинаторика 1».

Из формул видно, что: Cn0=1, Cn1=n, Cn2=n*(n-1)/2=(n2-n)/2, Cn3=n*(n-1)*(n-2)/6 … Cnn-1=n, Cnn=1.

Свойство 1. Cnk=Cnn-k (при всех n>=0 и всех k от 0 до n; обычно говорят кратко — «при всех n и k»).
Доказательство: Их у этого свойства будет два: первое — из формулы, второе — комбинаторное рассуждение.
1.) Cnk=n!/(k!*(n-k)!), а Cnn-k=n!/((n-k)!*(n-(n-k))!)=n!/((n-k)!*k!) — то же самое, что и Cnk, ч.т.д.
2.) Когда мы выбираем k предметов из n, то n-k предметов мы оставляем. Если мы, наоборот, выбранные k предметов оставим, а оставленные n-k — выберем, то получим способ выбора n-k предметов из n. Заметим, что мы получили взаимно-однозначное соответствие способов выбора k и n-k предметов из n. Значит, тех и других способов поровну. Но одних а Cnk, а других а Cnn-k, поэтому они равны, ч.т.д.

Свойство 2. Cn+1k+1=Cnk+Cnk+1, «при всех n и k».
Доказательство: Их опять будет два, различных по тому же принципу.
1.) Cnk=n!/(k!*(n-k)!), Cnk+1=n!/((k+1)!*(n-k-1)!), а Cn+1k+1=(n+1)!/((k+1)!*(n-k)!). Теперь приведем первые два равенства к общему знаменателю и сложит: Cnk+Cnk+1 = n!*(k+1)/((k+1)!*(n-k)!)+n!*(n-k)/((k+1)!*(n-k)!) = n!*(k+1+n-k)/((k+1)!*(n-k)!) = (n+1)!/((k+1)!*(n-k)!) = Cn+1k+1, ч.т.д.
2.) Cn+1k+1 — это кол-во способов выбрать k+1 предметов из n+1. Посчитаем его, зафискировав один предмет (назовем его «крапленым»). Если мы не берем крапленый предмет, то нам надо выбрать k+1 предмет из n оставшихся, а если мы его берем, то надо выбрать из n оставшихся еще k предметов. Первое можно сделать Cnk+1 способами, второе — Cnk способами. Всего как раз Cnk+Cnk+1, ч.т.д.

(!) Мы только что познакомились со специфическим комбинаторным способом доказательства равенств. Он заключается в том, чтобы посчитать одно и то же количество двумя способами и получить при этом формулы, стоящие в разных частях доказываемого равенства. Раз мы считали одно и то же, то эти формулы равны (см., напр. док-во 2 св-ва 2). Иногда мы считаем два разных количества, а потом замечаем, что они одинаковы, приводя взаимно-однозначное соответствие между объектами, посчитанными в первый и во второй раз (см., напр. док-во 2 св-ва 1) — соответствие способов выбрать k и n-k предметов.

Примеры комбинаторных задач с «цэшками»:

Задача 1. Сколькими способами можно из семи банок с краской разных цветов выбрать четыре?
Решение: Число способов выбора — это C74. Давайте его посчитаем: C74=C73 по св-ву 1. C73 = 7*6*5/3! = 7*6*5/6 = 7*5 = 35.

Задача 2. У одного меломана есть 6 дисков известной поп-группы, у другого 8. Сколькими способами они могут обменяться тремя дисками?
Решение: Каждый меломан должен выбрать из своих дисков три, которые он будет менять. Первый может сделать это C63 способами, а второй C83 способами. Так как выбор независим, то все вариантов C63*C83. Посчитаем: C63 = 6*5*4/3! = 6*5*4/6 = 5*4 = 20. C83 = 8*7*6/3! = 8*7*6/6 = 8*7 = 56. Ответ: 20*56=1120.

Задача 3. В кружке занимаются 2 девочки и 7 мальчиков. Сколько есть способов послать на конкурс команду из 4-х человек, если в ней обязательно должна быть хоть одна девочка?
Решение: В команду входит либо одна девочка, либо обе. В первом случае эту девочку можно выбрать C21 способами, а также C73 способами выбрать в команду еще трех мальчиков. Во втором случае в команду надо выбрать еще 2-х мальчиков C72 разными способами. Всего C21*C73+C72 способов. Посчитаем: C21=2, C73=35 (уже считали в зад.1), C72=7*6/2!=42/2=21. Ответ: 2*35+21=91.

Задача 4. Сколькими способами можно разбить 10 человек на 2 команды по 5 человек в каждой? А 15 человек на 3 команды по 5 человек в каждой?
Решение: Число способов выбрать одну команду (5 человек) — C105. Тогда ясен и состав второй команды — другие 5 человек. Но: каждый вариант выбора мы посчитали дважды, один раз считая первой одну команду, другой раз — другую. Поэтому в ответе будет C105/2 (желающие могут посчитать сами, что это будет 126).
Для трех команд давайте считать, что мы на время зафискировали порядок их выбора: первую, вторую и третью команды. Тогда число способов выбрать первую команду — C155, вторую (при выбранной первой) — C105, а третью автоматически образуют оставшиеся 5 человек. Сколько мы насчитали лишнего? Ясно, что способы выбора одних и тех же трех команд в разном порядке мы посчитали как разные. А одни и те же 3 команды можно поставить в разном порядке 3!=6 способами (см. лекцию «Комбинаторика»). Поэтому мы насчитали в 6 разбольше, чем нужно. Ответ: C155*C105/6 (это будет, на самом деле, 126126).
(!) Обратите внимание: мы сделали здесь примерно то же, что и в док-ве формулы Сnk=Ank/k! в лекции «Комбинаторика»: представили, что мы выбираем объекты не просто так, а в определенном порядке. То, что в исходной задаче было одним способом выбора, теперь может быть посчитано как разные способы много раз. А именно: факториал кол-ва объектов, к которым применена эта процедура, т.к. именно столькими способами можно эти объекты переставить. На этот факториал и надо будет поделить полученный ответ.
Вопрос на понимание: А почему из 15 человек можно выбрать 2 команды по 5 ровно C155*C105/2 способами?

«Цэшки», треугольник Паскаля и Бином Ньютона:
В предыдущих примерах мы вычисляли числа Cnk непосредственно по формуле, делая много умножений и делений. Оказывается, есть метод вычислять сразу много разных «цэшек», используя только сложение. Особенно важно это при программной реализации, поскольку компьютер складывает числа гораздо быстрее, чем умножает и тем более делит. Он основан на доказанном выше «свойстве 2″: Cn+1k+1=Cnk+Cnk+1.

Давайте построим из чисел два бесконечных треугольника. В первом из них (см. рис. внизу слева) будем ставить единицы в самом верху и по краям каждом следующей строки, а каждое из остальных чисел будет равно сумме двух стоящих над ним слева и справа (этот треугольник называется треугольником Паскаля). Во втором (см. рис. внизу справа) будем последовательно выписывать значения Cnk, отводя по одной строке для каждого значения n и располагая в ней «цэшки» по возрастанию k. На самом деле эти треугольники одинаковы. Равенство первых нескольких строчек, можно заметить, а дальше надо уже доказывать.

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

C00

C10

C11

C20

C21

C22

C30

C31

C32

C33

C40

C41

C42

C43

C44

Утверждение. Если строчки треугольника Паскаля и позиции в них нумеровать, начиная с нуля, то на k-м месте в n-й строке будет стоять значение Cnk (основное свойство треугольника Паскаля).
Доказательство: Индукция по n (см. лекцию «Индукция», если вы еще не знакомы с этим методом).
База: n=0 — действительно, C00=1 — как раз то, что стоит на верхушке треугольника Паскаля.
Переход: от n к n+1. Пусть в n-й строчке все числа уже равны значениям «цэшек» из n по соответствующим k. Рассмотрим n+1-ю строчку. На ее краях (нулевое и n+1-е места) стоят две единицы — и значения Cn+10 и Cn+1n+1 как раз равны 1. Далее, при всех k от 1 до n число, стоящее на k-м месте в n+1-й строке, равно сумме чисел, стоящих в n-й строке на k-1-м и k-м местах соответственно (т.е. как раз двух стоящих над ним — по принципу построения треугольника Паскаля). По предположению индукции, они равны Cnk-1 и Cnk, а их сумма тогда будет Cnk-1+Cnk, что как раз равно Cn+1k (по свойству 2 «цэшек»), ч.т.д.

Для справки мы приводим здесь первые 11 строчек (с нулевой по 10-ю) треугольника Паскаля — их можно посчитать и вручную. На компьютере, с помощью простой программы, можно вычислить значительно больше «цэшек», и более быстрого алгоритма, чем треугольник Паскаля, пока не существует.

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

1

5

10

10

5

1

1

6

15

20

15

6

1

1

7

21

35

35

21

7

1

1

8

28

56

70

56

28

8

1

1

9

36

84

126

126

84

36

9

1

1

10

45

120

210

252

210

120

45

10

1

Такие, казалось бы, чисто комбинаторные вещи, как числа Cnk и треугольник Паскаля, неожиданно встречаются и в алгебре. Выпишем известные формулы сокращенного умножения:

(a+b)0=
(a+b)1=
(a+b)2=
(a+b)3=

1
a+b
a2+2ab+b2
a3+3a2b+3ab2+b3

Коэффициенты в этих формулах (и это лучше видно, когда выписаны еще нулевая и первая степень) — это числа из треугольника Паскаля, то есть «цэшки». На самом деле, такая закономерность будет продолжаться и дальше, и называется она бином Ньютона. Точнее:(a+b)n=an+Cn1an-1b+Cn2an-2b2+…+Cnn-1a1bn-1+bn.
Можно доказать эту формулу по индукции, как и основное свойство треугольника Паскаля. Но это будет упражнением для желающих попрактиковаться в индукции. Приведем более простое объяснение:
(a+b)n=(a+b)(a+b)…(a+b) (n скобок). Раскрывая скобки, получаем в отдельных слагаемых произведения n букв, каждая из которых — a или b, т.е. an-kbk при каком-то k от 0 до n. Докажем, что для каждого такого k число таких слагаемых — ровно Cnk, откуда, приведя подобные, и получаем формулу бинома. Но это правда: an-kbk получается путем взятия a из k скобок и b из n-k оставшихся; разные такие слагаемые получаются путем разного выбора этих самых k скобок, а k скобок из n можно выбрать как раз Cnk способами, ч.т.д.
(!) Именно из-за бинома Ньютона числа Cnk часто называют биномиальными коэффициентами.

Более сложные свойства «цэшек»:
Прежде, чем изучать этот параграф, следует внимательно прочесть и понять предыдущий, так как приводимые здесь доказательства тесно используют связьCnk с треугольником Паскаля и биномом Ньютона.

Утверждение 1. Сумма Cn0+Cn1+Cn2+…+Cnn-1+Cnn (т.е. чисел в n-й строке треугольника Паскаля) равна 2n.
Доказательство №1: (комбинаторное). Поскольку Cnk — число способов выбрать k предметов из n, то сумма всех таких чисел при фиксированном n и разных k (т.е. сумма из условия) — число способов выбрать несколько предметов (возможно, 0, 1 или все) из n. Почему же несколько предметов из n можно выбрать именно 2n способами? Мы можем выбрать первый предмет или не выбрать — 2 случая. В каждом из этих случаев мы можем выбрать или не выбрать второй предмет — имеет по 2 подслучая, т.е. 22=4 варианта. В каждом из них образуется по 2 подслучая, смотря, выбран ли третий предмет — всего 23=8 вариантов и т.д. В конце, после n ветвления на подслучаи, получаем 2n вариантов, ч.т.д.
Доказательство №2: (индукция с использованием свойства Cn+1k+1=Cnk+Cnk+1).
База: n=0 и Cn0+Cn1+Cn2+…+Cnn-1+Cnn=C00=1=20, ч.т.д.
Переход: (от n к n+1). Cn+10+Cn+11+Cn+12+…+Cn+1n+Cn+1n+1 = Cn+10+Cn0+Cn1+Cn1+Cn2+…+Cnn-1+Cnn+Cn+1n+1 по указанному свойству. Заметим, что Cn+10=1=Cn0 и Cn+1n+1=1=Cnn, откуда это выражение равно 2Cn0+2Cn1+2Cn2+…+2Cnn-1+2Cnn = 2*(Cn0+Cn1+Cn2+…+Cnn-1+Cnn). Это, по предположению индукции, равно 2*2n=2n+1, ч.т.д.
Доказательство №3: (бином Ньютона). Заметим, что 2n=(1+1)n и раскроем по формуле бинома Ньютона (при a=b=1). Получим 1+Cn1+Cn2+…+Cnn-1+1 — с учетом того, что Cn0=Cnn=1, это как раз сумма из условия, ч.т.д.
(!) Обратите внимания: три разных рассуждения, использующие совершенно разный взгляд на природу «цэшек», приводят к одному и тому же результату. На самом деле, тот или иной взгляд может оказаться более удобным в зависимости от конкретной задачи и, конечно, конкретного решающего.

Утверждение 2. Сумма Cn0-Cn1+Cn2-…+(-1)n-1Cnn-1+(-1)nCnn равна 0.
Доказательство №1: (комбинаторное). Заметим, что сумма всех слагаемых со знаком «+» — это число способов выбрать четное число предметов из n, а со знаком «-» — соответственно,нечетное. Докажем, что тех и других способов поровну, например, поставив их во взаимно-однозначное соответствие. Объединим способы выбора предметов в пары так: в одном способе первый предмет выбран, а в другом не выбран, но остальные предметы в обоих способах выбираются одинаково. Ясно, что в двух способах из пары кол-ва выбранных предметов различаются на 1, поэтому в каком-то из способов выбрано четное число предметов, а в другомнечетное. Поскольку мы разбили на пары все способы, то тех и других поровну, ч.т.д.
Упражнение: Придумать еще два доказательства, по индукции и через бином Ньютона.
(!) Заметим, что четное (и нечетное тоже) число предметов из n можно выбрать 2n-1способами: число способов выбрать четное и нечетное число предметов одинаковы, а в сумме они дают 2n, значит, оба по 2n-1.

Утверждение 3. Сумма (Cn0)2+(Cn1)2+…+ (Cnn)2 равна C2nn.
Замечание: Это редкостное свойство, напротив, ни по индукции, ни через бином не доказывается :-(
План доказательства: Вспомнив про «свойство 1″, сделаем в сумме замену: Cn0*Cnn+Cn1*Cnn-1+…+Cnn*Cn0. Возьмем такой объект: 2n шариков, n белых и n черных. Число способов выбрать из них какие-то n шариков — конечно, C2nn. А если мы сгруппируем эти способы поколичеству белых и черных шариков среди выбранных, то получим как раз написанную выше сумму (упражнение: убедиться в этом).

Теория «шаров и перегородок»:
Этот параграф следует прочесть особо внимательно. Изложенный в нем метод, на первый взгляд, непрост, но очень изящен и имеет многочисленные применения в олимпиадных задачах.

Задача 5. Есть k ящиков и n>=k однаковых шаров. Сколькими способами можно разложить шары по ящикам так, чтобы ни один ящик не оказался пустым?
Решение: Давайте определять раскладку так: выложим шары в ряд и поставим между ними k-1 перегородку. То, что слева от первой перегородки, положим в первый ящик, между первой и второй — во второй… то, что справа от последней — в последний, k-й ящик. Ящик будет пустым, только если две перегородки стоят рядом не разделенные шарами, либо перегородка стоит с краю, левее или правее всех шаров. Так давайте это запретим! Пусть на каждое из n-1 мест между n шарами можно поставить не более одной из k-1 перегородок. То есть, из n-1 мест надо будет выбрать k-1, куда мы ставим перегородки. Отсюда получаем ответ: Cn-1k-1.

Задача 6. А сколько способов разложить шары, если могут быть пустые ящики?
Решение: Если определять раскладку так же, ставя между шарами k-1 перегородку, то ограничений уже не будет: шары и перегородки можно ставить в произвольном порядке. Давайте считать, что у нас расставлено в ряд n+k-1 объектов: n из них шары, а остальные — перегородки. Тогда раскладка будет определяться тем, на каких местах какие объекты стоят. Из n+k-1 мест можно выбрать n мест для шаров Cn+k-1n способами, или: k-1 место для перегородок Cn+k-1k-1 способами. Эти числа равны и оба являются ответом.

Выбор с повторениями, без учета порядка (с помощью новой теории).
Найдем, наконец, то, что мы не нашли в первой лекции по комбинаторике (но проанонсировали ответ Cn+k-1k): число способов выбрать k предметов из n с повторениями без учета порядка.
Общая формулировка задачи: есть предметы n различных сортов. Сколько способов выбрать k предметов, если учитывается только число предметов того или иного сорта?
Давайте считать, что k предметов — это «шары», а n сортов — «ящики», по которым мы их раскладываем. Тогда получаем ситуацию, аналогичную задаче 6, только n и k надо поменять местами. В ответе будет Cn+k-1k или, что то же самое, Cn+k-1n-1.

Задача 7. Сколько способов переплести 12 одинаковых книг в красные, зеленые или синие переплеты?
Решение: Опять нас выручает теория «шаров и перегородок»: пусть 12 книг — это «шары», а 3 цвета переплетов — «ящики», по которым мы их раскладываем. Приходим к задаче 6 при n=12, k=3. В ответе будет C142=C1412.

Задача 8. Сколько способов разложить 7 белых и 2 черных шара по 9 различным ящикам?
Решение: Давайте посчитаем отдельно число раскладки белых и черных шаров. Для белых получаем C158=C157 (опять задача 6: n=7, k=9), а для черных C108=C102 (та же задача 6 при n=2, k=9). Так как одна раскладка от другой не зависит, то число вариантов надо перемножить. Ответ: C157*C102.

Задача 9. Общество из n человек выбирает председателя из своего состава. Сколько есть разных распределений голосов за различных кандидатов?
Решение: Пусть n голосов — это «шары», а n кандидатов — «ящики». Получаем ту же всенародно любимую :-) задачу 6 (на самом деле, задача 5 тоже нередко применяется), при k=n. А ответ тогда C2n-1n.

Нет ответов пока

Вы должны ввойти чтобы оставить комментарий.