Так, ну, давайте, теорема более простая из двух. Эта теорема о том, чему равняется С из n по k. Мы хотим посчитать просто вот это вот число сочетаний без повторений. Значит, я утверждаю, что C из n по k можно выразить по следующей формуле. Это на самом деле просто A из n по k, поделенное на k факториал. То есть, k сочетаний без повторений в k факториал раз меньше, чем k размещений без повторений. Вот такое вот очень естественное соотношение между двумя комбинаторными величинами. Ну, и если записать явно формулу, которую мы в прошлый раз доказали для A из n по k, то у нас получится классическое выражение, которое, наверняка, многие могли видеть, где-то встречать уже раньше. n! * k!* (n − k)! Такое вот красивое симметричное выражение, которое служит явной формулой для подсчета чисел сочетания, сочетания, без, повторяю, без повторения. Так, ну, давайте, действительно это дело аккуратно докажем. И почему же сочетаний, которые без повторений ровно в k факториал раз меньше, чем размещений, которые естественно тоже без повторений? Ну на самом деле все очень просто. Давайте, я сначала словами скажу. И может быть для кого-то так будет сразу понятнее, после чего я разведу какое-то занудство на доске. Буду там как-то аккуратно это все расписывать. Но, на самом деле, все будет очень просто. Суть-то совсем элементарная. Смотрите, вот мы вытащили какую-то последовательность объектов, в которой мы учитываем порядок встречаемости этих объектов. Конечно, эту последовательность мы можем вытащить столькими способами, сколько у нас всего есть размещений без повторений. И это количество есть A из n по k. Вытащили какую-то последовательность: л, я, г. у, ш, к, а. Вот, например, такую вот последовательность букв русского алфавита. Всего 7 букв. То есть здесь в этом примере k равняется 7. Ну вытащили, замечательно. А могли вытащить другую последовательность тоже одним из вот стольких вот способов A из n по k. Ну, в данном случае, там A из 33 по 7. Потому что у нас 33 буквы русского алфавита, и мы из них, вот здесь видно, извлекаем 7 штук. Ну могли вытащить вот такую вот последовательность. Я об этом в прошлый раз говорил. И с точки зрения размещений без повторений − это, конечно, другая последовательность, потому что буквы в ней встречаются в ином порядке. Действительно, получается просто другое слово. В начале было слово «лягушка», теперь получилось слово «гуляшка». Ну там еще какая-нибудь «ялгушка» или еще что-нибудь. То есть вариантов много. Но если нас не интересует порядок букв, порядок объектов в той последовательности, которую вы извлекаем, а интересует лишь кучка, лишь пригоршня, состоящая из вот этих вот 7, в данном случае, букв, то и вот это, и вот это – суть одно и то же. И «ялгушка» и там не знаю, какое-нибудь «шау», что-то такое литовское. Это тоже, это тоже вполне то же самое сочетание без повторений. То есть это разные размещения, но это одно и тоже сочетание, понятное дело. То есть, вот здесь вот есть много различных размещений, но каждое из них представляет собой одну и ту же кучку букв. То есть, каждое из них является одним и тем же сочетанием. Но естественно сочетаний получается во столько раз меньше, сколько вот этих вот слов можно записать под данной фигурной скобкой. Но, а сколько можно таких слов записать, например, вот в этом конкретном случае? Если у нас всего 7 букв и мы их можем между собой переставлять как угодно, в итоге всякий раз, получая одну и ту же кучку из букв? Ну понятно, мы в прошлый раз это с вами обсуждали, это то, что называется число перестановок. То есть мы просто можем как угодно переставить 7 букв. Значит здесь у нас получится всего 7 факториал способов. Есть 7 факториал способов переставить буквы слова «лягушка», так что каждый раз буквы-то одни и те же, но слово получается новое. Ну понятно, значит в 7 факториал раз больше у нас получается этих отдельных слов размещений без повторений, нежели есть сочетаний без повторений, каждое из которых это просто кучка букв любого из этих слов. Вот ну, а теперь, давайте, я еще раз то же самое, смысл-то, вроде, совершенно понятен, еще раз то же самое постараюсь максимально формализовано уже, аккуратно сказать, в общем случае, когда у нас не 7, а произвольное число k, но суть абсолютно та же самая. Ну действительно, вот у нас есть множество, состоящее из n объектов. Давайте их как-нибудь стандартно обозначим, как у нас это водилось до сих пор, обозначим наши объекты a1, ..., a с индексом n. И вот из этого множества мы извлекает всевозможные k сочетания без повторений. Значит, извлекаем отсюда все возможные k сочетания без повторений. Берем какое-нибудь из этих k сочетаний, давайте, как-нибудь его так внешне обозначим в виде такой сарделечки. Я все-таки не могу быть совершенно формальным в каждый момент времени. Давайте, вот такая вот сарделечка будет у нас обозначать одно конкретное k сочетание. Ну, если вы хотите формальности, я конечно, могу около этой сарделечки написать, что-нибудь вот в таком стиле ai1 ai2, ..., ai с индексом k. Подразумевая, что k сочетание без повторений состоит вот именно из этих объектов с какими-то различными индексами i1, ..., ik, и это объекты, все изначально принадлежащие исходному множеству a1, ..., an. Но здесь, повторяю, важно, что i1, i2, ik — это все разные индексы, а это какие-то элементы исходного множества. Просто вот с какими-то различными индексами. Ну все-таки мне сарделечка, как-то вот, честно говоря, больше по душе, сарделечка, она как-то радует душу. Гораздо в большей степени, чем какое-то формальное множество со страшными двойными индексами. Вот. Это у нас сочетания. То есть опять же кучка, горстка букв, пригоршня, в которой порядок пока не имеет никакого значения. Вот зафиксировали одно такое k сочетание, потом зафиксировали какое-то другое k сочетание. Давайте, еще одна сарделечка — это еще одно k сочетание, которое отличается от данного. Но что значит оно отличается? Что значит k сочетание не такое же как предыдущее? Это значит, что у него другой набор вот этих индексов. То есть, не то чтобы мы как-то переставили элементы в нем. Нет, нет... эта пригоршня, она от этого не меняется. Нет. Мы берем просто какой-то другой, вообще говоря, набор букв, в котором есть буквы, отличные от присутствующих в первом k сочетании, в первой сарделечке. Ну я не знаю, как для красоты можно написать так aj1, ..., ajk, подразумевая, что вот это вот множество индексов j1, jk, отличается от множества индексов i1, ik, как-то вот они не совпадают между собой. Сами эти множества различны. Вот ну, и так далее, много, много таких сарделечек, много, много таких сарделечек. А сколько их? Товарищи, сколько всего таких сарделечек? Сколько всего различных k сочетаний без повторений? Ну допустим мы даже не знаем формулу, но мы же точно знаем обозначение их С из n по k, просто по определению. Вот это если хотите, первое, вот это – второе, вот это – третье, а вот это – С из n по k. Вот это самое последнее, мы их как-то перенумеровали, ну, мы их знаем, мы их по определению знаем, что их С из n по k штук. Хорошо. А теперь давайте, зафиксируем какую-нибудь их этих сарделечек. Вот в ней есть буковки, объекты a с какими-то там индексами, и начнем эти объекты между собой переставлять, вот буквально как здесь это было сделано в фигурных скобках. То есть будем записывать эти последовательности в разном порядке. Ну можно написать сначала a с индексом i1, потом a с индексом i2, и наконец, a с индексом ik. Можно в начало поставить вот этот последний объект, за ним, например, расположить второй. Ну и так далее. Но мы с вами знаем, мы это в прошлый раз изучали, и только что вспоминали относительно слова «лягушка», таких перестановок на множестве из вот этих вот k различных объектов, это различные объекты, и таких перестановок на множестве из этих k различных объектов k факториал штук. Ну давайте, так как-нибудь, это и нарисуем, в виде таких стрелочек. Здесь будет сарделька побольше. Во сколько раз эта сарделька побольше? Ну, ровно в k факториал раз. Значит, здесь было одно, а здесь получается k факториал. K факториал чего? Еще раз. Здесь у нас есть сочетания без повторений, некоторое совершенно конкретное, вот как в примере, это было сочетание, состоящее из 7 букв: л, я, г, у, ш. к, а. А вот здесь этому сочетанию, этой единственной горстке букв сопоставлены все возможные последовательности букв, все возможные слова, которые можно из этих букв составить путем их перестановки. Понятно, что этих слов – k факториал, и эти слова представляют собой в аккурат k размещения без повторений. Точно так же здесь есть k факториал различных порядков, различных размещений, которые соответствуют данному единственному, конкретному k сочетанию. Здесь есть точно также k факториал различных размещений, отвечающих данному k сочетанию. Ну и наконец, здесь их тоже k факториал. Картинка абсолютно идентичная. Понятное дело, сарделька увеличилась. Здесь у нас получается k факториал размещений. Хорошо. А сколько всего размещений? Смотрите, вот здесь k факториал, здесь k факториал, здесь k факториал, здесь k факториал. А суммарно сколько? Ну суммарно мы получим просто все возможные размещения. То есть суммарно мы получим в точности A из n по k – количество всех возможных размещений без повторений из n объектов. То есть, когда мы сложим вот эти все k факториалы, мы получим в аккурат A из n по k. Но сколько всего этих k факториалов? А столько, сколько было маленьких сарделечек, то есть С из n по k. То есть получается, что если С из n по k – количество маленьких сарделечек, умножить на k факториал, то есть сложить вот эти все k факториалы по всем С из n по k маленьким сарделечкам, то у нас получится в аккурат A из n по k – количество всех возможных размещений. Мы просто каждое размещение определили так: взяли некоторое k сочетание и по нему построили все возможные размещения, которые из него получаются. Естественно, мы исчерпали таким образом множество всех возможных размещений. Всех возможных слов из k различных букв. Ну и в итоге мы получаем ровно ту самую формулу, которая и была заявлена в формулировке теоремы. Ну, а это соответственно будет n! / k! * (n − k)! И теорема, тем самым, полностью доказана. Ну, товарищи, я не знаю, я конечно очень занудно в этом месте рассказал, но, с другой стороны, ну, проглотите этот кусок, если он совершенно очевиден. В конце концов, та затравка, с которой начато было доказательство для случая «лягушки» любимой, она же, в общем, понятна. Ну, а если вдруг непонятна, то посмотрите на это внимательно. Да, вот взяли каждое сочетание, посмотрели все размещения, которые ему соответствуют. Сочетаний суммарно С из n по k, размещений стало быть в k факториал раз больше. А сколько всего размещений? A из n по k. Ну значит, С из n по k — это A из n по k поделить на k факториал. и вся недолга. Теорема полностью доказана.
