Все комбинаторные величины у нас в кармане. Основные. Мы знаем размещение, мы знаем сочетание, мы умеем повторять, мы умеем не повторять, все формулы мы доказали, примеры задач какие-то привели, в домашней работе они тоже там появятся, будет масса интересных задачек на подсчет таких комбинаторных величин. Хочется понять где, в каких содержательных ситуациях эти комбинаторные величины еще участвуют, для чего они действительно нужны, и как ими можно жонглировать. Уподобно тому, как Франко жонглировал своими шариками да и своими формулами тоже. Вот, ими на самом деле можно жонглировать. Вот, ну самое первое, что обычно вспоминается в этом месте, это, конечно, то что называется бином Ньютона. Совершенно классическая вещь, которая вопреки литературным, так сказать, коннотациям, является вполне себе не сложной, и, как видите, может быть рассказана прямо в рамках второй лекции по вводной части комбинаторики. Значит, бином Ньютона, это вот что такое: вот у вас, как в школе учат, есть выражение (x + y), и его хочется возводить в какую-нибудь степень, а потом раскрывать скобки. Например, я думаю, что всякий школьник знает, что если (x + y) возвести в квадрат, то получится вот так. Я уж не буду честно раскрывать скобки, вы меня простите. Каждый из вас может это сделать сам, если вдруг забыл замечательную школьную формулу. x² + 2xy + y². Ну если она в жизни никогда не пригождалась вам, то вы вполне могли ее забыть. Если вы школьник, то вы получите 2, не зная такую формулу. Эта формула общеизвестная. Вот. Можно точно так же, взять и (x + y) возвести не во вторую степень, а в куб. Ну у вас получится x в кубе. Опять же, я не буду это проверять, это вот, если это школьник не знает, то он получит 2, только если он учится в математической школе. В обычной школе с него это может быть даже не спросят, а? Может быть я преувеличиваю, не знаю, может быть и спросят. Вот. 3x²y + 3xy² + y³. Вот такая вот формула есть. Ну проверьте на досуге, если вы не верите мне. Надо просто перемножить (x + y) * (x + y) * (x + y), раскрыть скобки и вот получится такая штука. Ну давайте я напишу еще одну. (x + y), например, в четвертой степени. Это будет x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴. Ну вот можно так раскрывать бесконечно долго, но если вы посмотрите на вид вот этих вот выражений, которые появляются после раскрытия скобок, вот этого, вот этого, вот этого, то вы увидите, что они какие-то исключительно симметричные. И если вы не знаете науки, вот, не знаете, что такое числосочетания, например, то вы будете смотреть на это как на некую загадку природы. Усмотрите в этом там какое-то мистическое явление, которое свидетельствует о том, что завтра, например, пойдет дождь. Я не знаю. В общем, это такой астрологический факт наверное будет для вас. На самом деле вся эта симметрия является простым следствием наших знаний, которые мы с вами уже получили, и, соответственно, теорема, которую мы в скорости с вами докажем, абсолютно аналогично тому, как мы только что действовали даже проще. Теорема состоит в следующем. Если мы (x + y) возведем в произвольную степень, которую обозначим n, как водится. Ну в какую-то n-ю степень, то выглядеть это будет вот так: у нас будет сначала C из n по 0 C из n по 0. Числосочетание из n объектов по 0. Мы с вами, кстати, в прошлый раз обсуждали это интересное явление, но я сейчас еще раз напомню. Значит, * x в степени n ну можно и так, y в 0, y в 0 это просто 1. Но вот я так в симметричной форме хочу написать. Дальше будет C из n по 1 * x в (n − 1) * y в 1 + C из n по 2 ну если там хватает слагаемых, * x в степени (n − 2) * y² +... +, а дальше все симметрично. Давайте, C из n, скажем по (n − 1) * x в 1 * y в (n − 1) и +, наконец, C из n по n * x в 0 * y в n. Вот такая вот замечательная формула. Ну давайте прежде чем ее доказывать, все таки сравним с тем, что написано вот на этой части доски, да? Я думаю, что на это у нас как раз хватит места в этом кусочке пространства. Так. Ну давайте подставим, скажем, n = 2. Вот просто в это утверждение подставим n = 2. Что такое C из 2 по 0? Ну даже по сути — это количество способов вытащить пустое множество, множество, в котором вообще отсутствуют какие-либо объекты, из множества, состоящего из 2-х объектов. Понятно, что должна быть 1, но с другой стороны, так оно и есть. 2 факториал / 0 факториал * (2 − 0) факториал. Вот мы сегодня доказали эту замечательную формулу. 2 факториал / 2 факториал — это 1. 0 факториал по определению — это тоже 1. Так что все сходится, это 1. И y в 0 это тоже 1, поэтому у нас получается просто x², вот здесь вот. Дальше мы смотрим C из 2 по 1. Давайте вот здесь C из 2 по 1. Это 2 факториал / 1 факториал * 1 факториал. Вот здесь вот тоже 1 факториал. Давайте их одинаково нарисуем, эти две единички. Ну опять смысл понятен, надо из двух объектов вытащить какой-нибудь один. Понятно, что из двух объектов один объект вытаскивается ровно двумя способами. И здесь мы получаем именно это: 2 факториал это 2. 1 факториал — это 1. То есть да, действительно, есть два способа вытащить один объект из множества мощности 2. То есть мы получаем + вот здесь вот. C из 2 по 1 — это 2. x в первой y в первой, то есть xy. Дальше, C из 2 по 2 — это последнее слагаемое, C из 2 по 2. Это надо из двух объектов вытащить два объекта. Ну понятно, что это делается единственным способом. По формуле тоже получается 1 и мы просто прибавляем y², y во второй степени. Сошлось, в точности. Ну можем проверить, чтоб уж не совсем занудствовать, например, для (x + y)⁴. А то если я уж каждую формулу буду проверять, то вы соскучитесь. Значит, для (x + y)⁴, вот n = 4. Действительно, C из 4 по 0 — это снова 1. Пустое множество из любого извлекается только одним способом. x в 4 вот он. x в 4 все в порядке. y в 0 пропал, 1 стал. C из 4 по 1 — это количество способов вытащить один объект из 4, понятное дело, таких способов 4 штуки. По формуле запишите — будет тоже 4, как это не удивительно. Дальше идет x в (n − 1), то есть x³. А y в первой, вот он y в первой, это просто y. Так, следующее слагаемое — это C из 4 по 2. Это первая нетривиальная C, про которую с ходу неочевидно, чему она равняется, ну 4 факториал — это 24, 2 факториал — это 2. Итого получаем 6. Хе! Вот оно 6. Какое совпадение удивительное. Ну 6, да, * x² * y² Ну дальше тоже можете посчитать, будет то же самое. То есть вот эта вот формула, она, собственно, вот эта формула и называется биномом Ньютона, ничего в этом на самом деле сложного нет. Давайте я еще для красоты слога, чтобы вы привыкали к каким-то более серьезным математическим обозначениям, напишу ту же самую формулу с помощью значка суммирования. То есть я буду писать не +... +, а вот так: как водится сумма обозначается значком Σ, да? Пока от 0 до n, C из n по k, на, ну тут так написано, y в степени k, x в степени (n − k). Видите, когда 0 подставляем, здесь как раз x в n будет, y в 0. C из n по 0, тогда 1 вот это получится, ну и так далее. Просто стандартное короткое обозначение для вот этого длиннющего. Ну длиннющее долго писать, а короткое вон такое вот красивое и замечательное. Сейчас докажем.
