[МУЗЫКА] Мы изучили довольно много разных вещей в комбинаторике, и в этом видео мы потренируемся решать задачи, попробуем поприменять наши знания. Давайте рассмотрим, например, такую задачу. У нас есть колода из 52 карт, стандартная обычная колода. И мы хотим выбрать пять карт из этой колоды. Сколько есть способов это сделать? Когда мы выбираем карты из колоды, то выборка неупорядоченная. Давайте считать, что она неупорядоченная, обычно порядок не имеет значения, у нас просто есть рука из пяти карт. Так что на самом деле, мы просто выбираем подмножество из множества, в котором 52 элемента, 52 карты. Ну сколько есть пятиэлементых подмножеств в 52-элементном множестве? Это c (52 / 5). Это можно посчитать, и окажется, что это порядка двух с половиной миллионов способов выбрать пять карт из колоды из 52 карт. Хорошо, давайте немножко усложним задачу и посмотрим, сколько есть выборов пяти карт из такой же колоды, в которых есть две черви и три пики. Ну вот теперь у нас какая-то не произвольная рука из пяти карт, а с какими-то ограничениями. У нас должно быть две черви и три пики. Давайте попробуем это посчитать. И это оказывается не очень сложно. Нам нужно взять две черви (червей всего 13 в такой колоде), и нам нужно выбрать две карты из 13 возможных. Также нам нужно взять три пики. И их в колоде тоже 13, и нам нужно выбрать три карты из 13 возможных. Две карты из 13 можно выбрать c (13 / 2) способами, и три карты из 13 можно выбрать c (13 / 3) способами. И дальше по правилу произведения их нужно перемножить, и получается вот столько способов: примерно 22 тысячи способов выбрать пять карт так, чтобы среди них были ровно две черви и ровно три пики. Видно, что порядок чисел совсем другой. Таких выборов карт уже гораздо меньше. Хорошо, давайте рассмотрим другую задачу. Сколько есть неотрицательных целых чисел меньше 10 тысяч, содержащих цифру 7? Ну давайте попробуем стандартные способы, как мы можем это вычислять, как мы делали что-то подобное раньше. Ну мы можем начать последовательно перебирать цифры этого числа. Первую цифру можно выбрать десятью способами. Давайте смотреть на такое число, как на последовательность из четырех цифр, если там меньше цифр, просто допишем их вначале нулями, то есть трехзначные числа — это четырехзначные числа, которые начинаются с 0. Итак, при таком взгляде на вещи, первую цифру из четырех можно выбрать десятью способами. Вторую тоже можно выбрать десятью способами, третью также можно выбрать десятью способами. А вот с четвертой цифрой будут проблемы, потому что если среди первых цифр уже встретилась семерка, то четвертую цифру можно выбрать тоже десятью способами. А если семерка там не встретилась, то четвертую цифру можно выбрать ровно одним способом. И это проблема, то есть вот мы это проанализировали, но это не дает нам ответ, как вообще это посчитать. Мы хотели бы теперь что-то перемножить по правилу произведения, но с четвертой цифрой проблема. В зависимости от того, какие казались первые три цифры, четвертую цифру можно выбрать разным количеством способов. Хорошо, давайте попробуем по-другому. Мы решали близкую задачу на прошлой неделе, и нам нужно было посчитать числа, в которых есть ровно одна цифра семь. Ну давайте попробуем аналогично, может быть, не так важно, что там ровно одна цифра семь, или просто что хотя бы одна цифра семь там есть в этом числе. Попробуем это повторить. И хорошо, позицию для цифры семь можно выбрать четырьмя способами, вот как мы рассуждали в тот раз. Ну допустим, мы это уже сделали, и тогда на каждую из оставшихся позиций, ну в прошлый раз мы говорили что можно поставить цифру девятью способами, потому что семерка уже использована и второй раз ее использовать нельзя, ну а здесь у нас семерка может использоваться второй раз, поэтому можно поставить туда цифру десятью способами, на все оставшиеся три позиции можно поставить цифру десятью способами. Но в этом решении есть проблема, и она состоит в том, что некоторые числа мы посчитали два раза, а именно вот, например, число 7.573 мы посчитали два раза, потому что один раз мы посчитали его, когда поставили цифру семь на первую позицию, а остальные цифры выбрали произвольным образом, а второй раз когда поставили цифру семь на третью позицию, а остальные выбрали произвольным образом. Видно, что вот такое число в наших подсчетах встретится дважды. И это проблема, потому что другие числа встретятся один раз, и некоторые встретятся больше раз, и в общем, непонятно, как это починить. Хорошо, пока непонятно, как это быстро посчитать и в целом неочевидно. Но на самом деле оказывается, что здесь работает следующий прием. Довольно легко посчитать противоположное, довольно легко посчитать не те числа, которые нас спрашивают, а все числа минус те числа, которые нас спрашивают. Заметим, что всего чисел без цифры семь, их 9⁴. Ну действительно, если мы пытаемся посчитать числа без цифры семь, то первую цифру можно выбрать девятью способами (семерка запрещена), вторую тоже девятью способами (опять же, семерка запрещена) и так далее. Каждую цифру можно выбрать девятью способами, мы должны это перемножить по правилу произведения, получится 9⁴. А при этом всего чисел — 10⁴, потому что понятно, первую цифру можно выбрать десятью способами, вторую десятью способами и так далее. Поэтому, если мы хотим посчитать число чисел, в которых есть хотя бы одна цифра семь, надо взять все числа 10⁴ и вычесть все числа, которые не годятся, а именно те, в которых семерка не встречается, их 9⁴. Вот такой получается ответ, и получается, что таких чисел 3.439. Хорошо, давайте рассмотрим еще одну задачу. Сколько есть целых чисел от нуля до 9.999 таких, что их цифры убывают при чтении слева направо, то есть каждая следующая цифра просто меньше предыдущей. Сколько есть таких чисел? Ну и опять же, давайте попробуем стандартные способы, попробуем посчитать варианты для каждой позиции и воспользоваться правилом произведения. Ну и видно, что у нас возникнут проблемы, потому что первую цифру понятно, что можно выбрать, допустим, десятью способами, а вот вторую уже непонятно, потому что она должна быть меньше первой цифры. И все зависит от того, какая была первая цифра. Если это была девятка, то там есть девять способов, если это была, допустим, тройка, то там всего три способа. Так что на этом пути возникает проблема, и поэтому мы попробуем с другой стороны подойти к этой задаче. И давайте попробуем сделать так: вот у нас есть четыре позиции для наших цифр. Давайте просто выберем, какие цифры среди цифр от нуля до девяти войдут в наше число. Ну и как только оказывается, что как только мы выбрали эти четыре разные цифры, то число определяется однозначно. Ну действительно, вот если мы выбрали, например, числа три, четыре, два и семь, то наше число определяется однозначно, а именно, мы теперь должны их расставить в убывающем порядке. То есть если мы знаем, какие цифры входят в наше число, то само число определяется однозначно. Мы можем написать только 7, 4, 3 и 2, только такое число с этими цифрами годится. Получается, что порядок выбора цифр не важен, то есть мы выбираем просто четыре цифры из десяти возможных, и по сути мы выбираем сочетание размера четыре из десяти вариантов. То есть мы выбираем подмножество из четырех цифр среди десяти возможных цифр. Получается, что чисел с убывающими цифрами столько же, сколько подмножеств размера четыре в десятиэлементом множестве. Получаем, что ответ этот c (10 / 4) — это 210 вариантов. То есть чисел четырехзначных с убывающими цифрами всего 210 штук, их не так много. Рассмотрим еще один пример, уже знакомая нам картинка, но немножко другая задача. У нас есть фишка на доске, она стоит в левом нижнем углу, и мы хотим сдвинуть ее в позицию, помеченную в клетку с координатами 3 и 5. Она вот отмечена на доске. За каждый ход мы можем сдвигать фишку либо на одно поле направо, либо на одно поле вверх. Сколько есть способов это сделать? Ну в прошлый раз мы считали, сколько нужно шагов. И шагов нужно восемь, это мы уже обсуждали, и при этом три шага должны быть сдвигом направо, а остальные пять шагов — сдвигом вверх. И что важно, любая такая комбинация шагов приводит нас в правильную клетку. То есть как бы мы ни сделали шаги так, что среди них и было три шага направо, и пять шагов вверх, мы неизбежно придем в клетку с координатами 3 и 5. Хорошо, осталось посчитать, сколько есть способов сделать восемь шагов, так что среди них есть три шага направо и пять шагов вверх. Ну а по сути что нам нужно сделать? Нам нужно выбрать подмножество из восьми шагов размера три. Если мы возьмем восемь шагов наших последовательных и выберем среди них три, и скажем, что в эти три шага мы сделали ход направо, а в оставшиеся шаги мы сделали ход вверх, то это будет выборка — выборка, которая приведет нас в правильную клетку. Таким образом, нам нужно просто посчитать количество способов выбрать три шага среди восьми возможных. И мы получаем, что это просто количество подмножеств размера три в восьмиэлементом множестве c (8 / 3), 56 способов дойти в эту клетку. На самом деле давайте посмотрим на эту задачу еще с другой стороны. Оказывается, что то, что мы здесь делали, можно на самом деле в этом увидеть треугольник Паскаля. Давайте попробуем. Давайте нарисуем эту доску, И давайте в каждой клетке напишем, сколько есть способов дойти из левого нижнего угла в эту клетку. Давайте постепенно заполнять эту табличку. Что мы можем сказать сразу? Во-первых, мы можем сказать что в левой нижней клетке единица. Есть ровно один способ дойти из левой нижней клетки в нее саму — просто стоять на месте. Дальше, во всех клетках в нижней строке тоже стоит единица, потому что есть ровно один способ попасть в каждую из них — просто идти направо и никуда не сворачивать. То же самое с первым столбцом — мы можем только идти вверх и никуда не сворачивать. Дальше, вот в следующей клетке стоит цифра два. Это клетка с координатами 1, 1, она чуть правее и выше, чем левый нижний угол. Почему? Ну потому, что есть два способа туда попасть. Мы можем попасть туда из клетки левее и из клетки ниже. И туда и туда мы можем попасть одним способом, и мы по правилу суммы должны их сложить, получится два варианта попасть в эту клетку. Давай просмотрим клетку теперь чуть правее, и там мы должны написать три. Опять же, есть два способа, два возможных варианта, как попасть в эту клетку. Есть пути, которые ведут из левой клетки, и есть пути, которые ведут снизу. И путей первого типа — их два, а путей второго типа снизу, их один. По правилу суммы мы должны сложить, получить тройку. Давайте продолжим. Вот в этой клетке тоже надо написать три, потому что есть два способа дойти снизу и один способ дойти слева. По правилу суммы складываем. И можно продолжить это дело, так по диагоналям заполнять эту табличку. Вот здесь будет написано четыре, потому что это 3 + 1. Вот здесь будет написано шесть: есть три способа дойти слева и три способа дойти снизу. Здесь будет написано четыре. И и так далее. Мы можем продолжить заполнять эту табличку, пока не дойдем до клетки с координатами 5, 3, и там будет написано какое-то число. Но на самом деле давайте просто заметим, что здесь нарисован треугольник Паскаля, который просто перевернули и совместили его вершину с левым нижним углом. То есть просто мы вот видим, что эта картинка просто совпадает с треугольником Паскаля вот так перевернутым, и это не случайно. Потому что на этой картинке в каждой клетке мы вписываем число, которое получается суммой клетки левее и ниже, и это то же самое правило, которое мы использовали в треугольнике Паскаля: значение в каждой каждой клетке получается суммой значений двух клеток над ней. После переворачивания получается то же самое. Это и есть треугольник Паскаля. Хорошо, мы подробно обсудили с вами биномиальные коэффициенты, рассмотрели разные свойства, и оказалось, что у них есть много математических и комбинаторных интерпретаций, оказывается, что они встречаются в разных местах и они очень полезны. Мы попрактиковались в применении наших знаний, то есть мы попробовали порешать разные задачи, увидели, что есть разные подходы и идеи. И в следующем уроке мы обсудим с вами еще одну стандартную комбинаторную постановку, которую мы еще не обсуждали, а тем не менее она часто встречается. [МУЗЫКА]
