Комбинаторика
Комбинаторика и теория вероятности.
1. ПЕРЕБОР ВАРИАНТОВ «ОСОБАЯ ПРИМЕТА» КОМБИНАТОРНЫХ ЗАДАЧ.
3. РЕШЕНИЕ ЗАДАЧИ О КВАРТЕТЕ.
4. ПЕРЕСТАНОВКИ С ПОВТОРЕНИЯМИ.
6. ЕСТЬ ЛИ У НУЛЯ ФАКТОРИАЛ?
7. РАЗМЕЩЕНИЕ С ПОВТОРЕНИЯМИ.
8. РЕШЕНИЕ ЗАДАЧИ О ПАСПОРТАХ.
10. задача о лотто-миллион.
11. сочетания с повторениями .
12. БИНОМ НЬЮТОНА.
13. биномиальные коэффициенты и сочетания.
14. треугольник паскаля .
15. Список литературы.
ПЕРЕБОР ВАРИАНТОВ «ОСОБАЯ ПРИМЕТА»
В знаменитой басне Крылова «Квартет» «проказница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент: они исследовали влияние взаимного расположения музыкантов на качестве исполнения. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты. Зададимся вопросом: сколько существует способов, чтобы рассадить, например в один ряд, четырех музыкантов?
Другой случай. Воспетый Маяковским «молоткастый, серпастый» советский паспорт имел серию и номер, состоящие в общей сложности из трех частей:
1)Некоторое число, записанное римскими цифрами;
2)Две русские буквы;
3)Шесть арабских цифр.
Например, IX-РГ № 000. Разумеется, все паспорта должны иметь разные номера. Сколько может быть различных паспортов?
Третья ситуация. Нас приглашают сыграть в Лотто-Миллион. Суть игры в том, что нужно из 49 номеров угадать 6, которые выпадут во время тиража. Для участия в игре следует приобрести специальную карточку и вычеркнуть в ней 6 любых квадратов, пронумерованных числами от 1 до 49. Чтобы выиграть наверняка, можно было бы запастись таким количеством карточек, какое необходимо для вычеркивания 6 номеров всеми возможными способами. Сколько этих способов?
Общее у всех этих задач то, что их решение занимается отдельная область математики, называемая комбинаторикой. «Особая примета» комбинаторных задач – вопрос, который всегда можно сформулировать так, чтобы он начинался словами: «Сколькими способами…».
Пусть имеется n объектов, неважно каких, лишь бы все они различались между собой: книги, детские кубики или музыканты крыловского «Квартета». Мысленно расставим их в ряд и такое упорядоченное расположение объектов назовем перестановкой. Попытаемся ответить на вопрос: сколько всего возможно перестановок из n предметов? Число перестановок обозначается Pn, подчеркивая тем самым, что оно зависит от количества предметов n.
Попытаемся найти Pn сначала для небольших n. Если n=1, т. е. имеется один единственный предмет, то существует и один-единственный способ его перестановки. Поэтому P1 = 1.Возьмем n = 2. Сразу понятно, что P2 = 2, поскольку два предмета (назовем их А и Б) можно расставить двумя различными способами: АБ и БА. Попробуем рассуждать несколько иначе: первый предмет (А) установим неподвижно, а второй (Б) будем «прилаживать» к нему. Безусловно, объект Б можно поставить либо спереди, либо сзади от А, следовательно, число перестановок P2 вдвое больше, чем P1, т. е. P2 = P1 ∙ 2 = 1 ∙ 2. Добавим теперь третий предмет В. К каждой из перестановок двух объектов А и Б можно пристроить третий предмет тремя различными способами: поставить его спереди, между ними либо сзади. Перестановка АБ, таким образом, порождает три перестановки: ВАБ, АВБ и АБВ, перестановка БА – также три: ВБА, БВА и БАВ, и все получившиеся шесть перестановок – разные. Отсюда P3 = P2 ∙ 3 = 1 ∙ 2 ∙3.
Вообще, из каждой перестановки n – 1 предметов можно получить n дополнительных перестановок, добавляя n-й предмет либо спереди, либо сзади, либо между имеющимися предметами (между n – 1 предметами существует n – 2 промежутка; 1 + 1 + n – 2 – вот и выходит ровно n). Стало быть, при переходе от n – 1 к n предметам количество перестановок увеличивается в n раз. Поэтому общая формула будет такой:
Pn = 1 ∙ 2 ∙ 3 ∙ … ∙ n = n!.
Восклицательным знаком (в математике он называется факториалом) принято обозначать произведение всех натуральных чисел от 1 до n включительно.
Мы не просто вывели формулу, но одновременно указали способ, как получить все возможные перестановки. Надо отметить, что он далеко не единственный. Например, все перестановки можно получить из начальной, поочередно меняя местами соседние объекты:
АБВ → АВБ → ВАБ → ВБА → БВА → БАВ.
РЕШЕНИЕ ЗАДАЧИ О КВАРТЕТЕ.
Четыре горе-музыканта из басни Крылова долго пересаживались с места на место. В ходе этого «творческого поиска» Осёл внёс предложение: «Мы, верно, уж поладим, коль рядом сядем» Попробовали – не помогло. Но в ряд-то можно сесть по-разному! Давайте определим число возможных перестановок. Здесь n = 4, поэтому способов «усесться чинно в ряд» имеется P4 = 4! = 1 ∙ 2 ∙ 3 ∙ 4 = 24.
Добавим, что для решения некоторых задач приходится применять идею перестановок не в «чистом» виде, а с поправками. Допустим, главный фактор, влияющий на качество игры, — это соседи каждого музыканта, и не важно, кто из них справа, а кто слева. При таком условии перестановка «Мартышка, Осёл, Козёл, Мишка» эквивалентна зеркально-симметричной: «Мишка, Козёл, Осёл, Мартышка». Понятно, что в этом случае все P4 вариантов разбиваются на пары равнозначных перестановок, то общее число различающихся вариантов будет P4/2 = 24/2 = 12
Теперь представим, что музыканты сели не в ряд, а по кругу. В этом случае можно рассуждать так: в каждом из вариантов пронумеруем всех участников по часовой стрелке, начиная, скажем, с Осла. В различных перестановках каждый, конечно, должен иметь разные номера. Только у одного из них – Осла – будет постоянный номер 1. Значит, осталось пронумеровать различными способами только троих. Поэтому здесь число возможных перестановок – P3 = 3! = 6.
ПЕРЕСТАНОВКИ С ПОВТОРЕНИЯМИ.
Есть особый (и очень важный!) вид перестановок – перестановки с повторениями. В них среди прочих участвуют предметы, неразличимые между собой, — «близнецы». Замена одного «близнеца» другим не приводит к новой расстановке. Предположим, что, отчаявшись, наши музыканты решили создать вместо квартета симфонический оркестр. Для этого Мартышка привела с собой ещё 15 Мартышек, Осёл – ещё 20 Ослов, Козёл – 10 Козлов, лишь Мишка поленился и остался в одиночестве. Выясним, сколькими способами можно рассадить их в ряд.
Возьмем любую произвольную расстановку всех 16 + 21 + 11 + 1 = 49 музыкантов. Если бы «близнецов» в их числе не оказалось, то перестановок было бы 49!. Но вот среди них появилось 16 одинаковых Мартышек. Не трогая остальных зверей, а меняя лишь Мартышек всеми возможными способами (а их будет 16!), получим вроде бы новой перестановки, но теперь уже не различимые. То есть каждые16! Старых перестановок преобразуются в одну новую, и общее число перестановок уменьшается в 16! Раз. Очевидно, та же история с Ослами, и с Козлами (лишь Медведь по-прежнему один). В итоге количество перестановок окажется равным
Медведя мы не учитывали, но, дабы не нарушать единообразия, добавим и его, т. е. поделим указанное выражение на 1! = 1, что ничего не меняет. А записывать это принято так:
P 16,21,11,1 = 49!16! ∙ 21! ∙ 11! ∙ 1! ≈ 1,4 ∙1022
Обратите внимание на горизонтальную черту на буквой Р : с её помощью отличают повторений от обычных перестановок.
Нетрудно получить и общую формулу для случая, когда имеется n групп «близнецов», со стоящих соответственно из k 1, k 2, …, k n неразличимых предметов:
Pk1, k2, …,kn=k1+k2+ …+kn! k1!k2!… kn !
Множество факториалов в этой формуле кого-то может смутить. Но в комбинаторике факториал – частый гость, даже хозяин. К сожалению, на калькуляторе функция «факториал» обычно отсутствует, поэтому при практических расчетах приходится последовательно умножать натуральные числа. Занятие довольно трудоёмкое – попробуйте, например, вычислить 49!. Однако, когда не требуется абсолютной точности, для больших n можно с успехом использовать формулу, которую вывел в XVIII в. Шотландский математик Джеймс Стирлинг:
Она примечательна не только высокой точностью (уже при n = 10 погрешность менее 1%), но и неожиданным присутствием двух замечательных чисел: числа Эйлера е = 2,71828… и не менее знаменитого π=3,14159 …. А произвести вычисления по формуле Стирлинга на хорошем калькуляторе не составляет труда.
Иногда бывает нужно из n имеющихся различных объектов отобрать произвольное m штук (m≤ n ) и расположить их некотором порядке. Каждое такое упорядоченное расположение называется размещением. Сколько существует размещений при заданных n и m? Оказывается, ответ можно дать, основываясь на знании перестановок.
Обозначим искомое число Anm . Сначала возьмём любую перестановку всех n объектов и рассмотрим первое m из них. Они образуют размещение m объектов из n имеющихся, тогда как последние n – m объектов совершенно не влияют на это размещение, как их не переставляй. Но эти n – m «хвостовых» объектов могут быть переставлены Р n – m способами. Значит, каждому размещению можно «пришить» Р n – m различных «хвостов», что порождает столько же перестановок всех n объектов. Общее число перестановок всех объектов Рn в таком случае равно произведению искомого Anm числа и Pn — m :
Anm= PnPn-m = n ! n — m !
Предположим, что происходит некий конкурс с 8 участниками. Одновременно проводится викторина: нужно угадать, кто займет в конкурсе 1,2,3-е места. Сколько всего существует вариантов ответов? Очевидно, что искомое количество равно числу размещений из 8 по 3:
A83 = 8!5! = 8 ∙ 7 ∙ 6 = 336
Надо сказать, что некоторые следствия из этой формулы довольно неожиданны…
ЕСТЬ ЛИ У НУЛЯ ФАКТОРИАЛ?
Как вы думаете, сколькими способами можно выбрать 0 объектов из n имеющихся, или другими словами, сколькими способами можно не выбрать ни одного объекта? Вопрос, конечно, странный, но формально получается
An0 = n ! n — 0!= n ! n !=1
Пожалуй, это логично: есть единственный способ не выбрать ни одного объекта из n имеющихся – ничего не делать.
Второй вопрос: сколькими способами можно сделать упорядоченный выбор из n объектов… всех n? Поступаем так: выбираем любой объект, рядом с ним размещаем второй, потом третий и т. д. получается обыкновенная перестановка всех n объектов, и число таких перестановок Рn = n!. С другой стороны, согласно найденной формуле, это же число равняется
Ann = n ! n — n != n !0!
Появилось новое выражение 0! (факториал мы определили только для натуральных чисел). Предположим, что 0! – это какое-то неизвестное число, и найдем его из равенства Ann = Pn . Тогда n!/0! = n!, откуда 0! = 1, т. е. факториал нуля равен единице (хотя казалось, что это непременно должен быть нуль). Факториал нуля возникает в самых разных комбинаторных задачах, но везде и всегда его принимают равным единице.
РАЗМЕЩЕНИЕ С ПОВТОРЕНИЯМИ.
Помимо обычных размещений бывают и размещения с повторениями (точно так же, как перестановки). Пусть имеется n различных объектов. Выберем из них m штук, действую по следующему принципу. Возьмём любой, но не будем устанавливать его в какой-то ряд, а просто запишем под номером 1 его название, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был только что взят), запишем его название, пометив номером 2, и снова вернем объект обратно. И так далее, пока не получим m названий. Размещения с повторениями обозначаются Anm . Определить это число несложно. На первом месте в списке может находиться любой из n объектов, на втором – тоже любой, и на третьем, и на четвертом… в общем, на каждом. Поэтому число размещений с повторениями выражается формулой.
Заметим, что здесь допустим случай, когда m > n, т. е., выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после «использования» возвращается обратно и может быть «использован» повторно.
РЕШЕНИЕ ЗАДАЧИ О ПАСПОРТАХ
Давайте определим, сколько может быть паспортов советского образца с различными сериями и номерами, если зафиксировать римские цифры серии. Остаются две русские буквы и шесть арабских цифр. Рассмотрим буквы и цифры отдельно.
БУКВЫ. В русском алфавите 33 буквы. Нам нужно выбрать любые две, при этом они могут оказаться и одинаковыми. Следовательно, имеет место размещение с повторениями, где n = 33 и m = 2: A332 = 332 = 1089.
ЦИФРЫ. Здесь выбирается (и опять с повторениями) m = 6 цифр из n = 10 возможных. Для этого есть A106 = 106 способов.
ИТОГ: поскольку каждую пару букв можно соединить с любой шестёркой цифр, то возможно существует A332∙A106 = 332 ∙ 106 = 1 089 000 000 паспортов, имеющих одни и те же римские цифры серии, — больше миллиарда! Ну а если потребовать, чтобы в каждом номере и буквы, и цифры были различными, — сколько тогда получится паспортов? Здесь вместо размещений с повторениями нужно использовать обычные размещения. Поэтому ответ таков:
A332∙A106 = 33!33 — 2! ∙ 10!10 — 6! = 33! ∙ 10!31! ∙ 4! = 200
Число уменьшилось более, чем в 6 раз.
В некоторых задачах по комбинаторике не имеет значения порядок расположения объектов в той или иной совокупности. Важно лишь то, какие именно элементы её составляют. К примеру, представим себе школьный класс, который пришёл в спортзал. Школьники могу выстроиться в шеренгу, а могут бегать, где попало, прыгать, кувыркаться, стоять на голове, лазать по канату – всё равно они останутся тем же самым множество учеников класса. Теперь часть из них переведём в соседнее помещение, где им также дозволяется, бегать, прыгать и т. д. Такая выборка элементов, при которой их порядок совершенно неважен, называется сочетанием. Число всевозможных сочетаний из п элементов по т обозначается Cnm . Попробуем найти это число.
Будем основываться на том, что нам известно: на размещениях и перестановках. Сначала из n элементов выделим какие-либо m элементов с учётом очерёдности выбора. Это — размещение, и число таких размещений Anm . Очевидно, что различные размещения, в которые входят те же объекты, но в ином порядке, будут соответствовать одному сочетанию (ведь в сочетании порядок роли не играет). Другими словами, любая перестановка выбранных m элементов порождает то же самое сочетание. Но таких перестановок Рm. Поэтому число сечений из п элементов по т в Рm раз меньше числа размещении, т. е.
Cnm = AnmPm = n! n-m! m! = n! m!(n-m)!
Обратите внимание на своеобразную симметрию этой формулы: если заменить т на п — т, получится то же самое, только факториалы в знаменателе поменяются местами. Отсюда следует замечательное свойство сочетаний:
Объясняется это просто: каждому сочетанию из т отобранных элементов всегда соответствует сочетание из п — т оставшихся. Так что можно с самого начала говорить не о выделении т объектов из п, а о разбиении множества исходных п элементов (например, тех же школьников) на две части — по ти n — m в каждой (т человек — в один зал, а n — m — в другой).
Попытаемся теперь ответить на следующий вопрос: сколькими способами п школьников могут разделиться по t залам так, чтобы в первом зале оказалось m 1 школьников, во втором m 1 , и т. д., где m 1 + m 2 + . + mt , = п? Обозначим искомое число через Cnm1,m2, …mt . Как его получить? Сначала из общего количества n школьников выделим m 1 , потом из n — m , оставшихся m 2 , и т. д., следовательно,
Cnm 1, m 2, … mt = Cnm 1 ∙ Cn — m 1 m 2 ∙ … ∙ Cn — m 1- m 2-…- mt -1 mt = n ! m 1 ! m 2!… mt !
Удивительно: хотя мы не рассматривали никаких перестановок и все школьники заведомо разные, тем не менее выведена формула, точно повторяющая формулу для числа перестановок с повторениями. А всё дело в том, что данную задачу можно трактовать двояко. С одной стороны, мы распределяем отличающихся друг от друга школьников по залам. Тогда получаются сочетания. Но опишем ситуацию по-другому: мы как бы распределяем среди школьников билеты в разные залы. Причём билеты в один зал неотличимы друг от друга. Это уже перестановки (билетов среди построенных в ряд школьников) с повторениями.
задача о лотто-миллион.
Сколько карточек Лотто-Миллион нужно купить и заполнить, чтобы на них оказались все комбинации по 6 номеров из 49 возможных? Понятно, что количество карточек равно числу сочетаний из 49 элементов по 6, т. е.
а это составляет почти 14 млн. Можно сделать вывод: для реализации подобной идеи уже надо быть миллионером! Но и в этом случае разбогатеть будет трудно, поскольку выигрыш не фиксирован и в каждом тираже на призовой фонд отводится лишь часть собранной от продажи билетов суммы.
Попробуем ответить ещё на несколько вопросов. Допустим, мы купили C 496 карточек и все их по-разному заполнили. После тиража 6 счастливых номеров окажется только на одной из них. Но в Лотто-Миллион выигрывают и карточки с совпадением 5 и даже 4 номеров. Сколько их?
Если на карточке угадано 5 номеров, это значит, что из 6 выпавших номеров здесь могут быть вычеркнуты любые 5, а из остальных 43 — лишь 1. Поэтому число способов угадать 5 номеров равно C 65 ∙ C 431 . Точно так же карточек с совпадением 4 номеров будет C 64 ∙ C 432 . Наконец, на C436 карточках не окажется ни одного выпавшего номера. Кстати, это больше или меньше половины от количества всех купленных карточек? Попробуйте сначала угадать, а потом проверьте себя.
сочетания с повторениями .
И перестановки, и размещения могут быть с повторениями. Имеет смысл говорить и о сочетаниях с повторениями. Из множества, содержащего п предметов, возьмём один произвольный, занесём его в список, после чего вернём обратно. Затем точно так же выберем ещё один объект и т. д., пока в списке не окажется т наименований (среди них могут быть и одинаковые). Принципиальное отличие от размещений с повторениями заключается в том, что в данном случае элементы списка не нумеруются. Например, списки «А, Б, А, Г» и «Б, Г, А, А», считаются одинаковыми. Попробуем найти число Cnm сочетаний с повторениями из п элементов по т. Для этого придётся проявить определённую изобретательность. Следите внимательно.
Произвольно пронумеруем элементы исходного множества числами от 1 до п. Пусть в какое-то из полученных сочетаний вошло k 1 элементов под номером 1, k 2 элементов под номером 2,…, kn элементов под номером n . Что можно сказать обо всех этих числах ki . Ясно, что сумма k 1 + k 2 + . + kn = m (ведь в списке всего т объектов!).
Теперь изобразим это сочетание в виде цепочки из нулей и единиц. Единица здесь будет обозначать каждый отдельный элемент сочетания, а нуль — символизировать границу между группами элементов, соответствующих соседним ki . Если некоторое ki = 0, т. е. элементов с номером i в списке нет, то в соответствующем месте цепочки окажутся два «пограничных» нуля подряд.
Итак, записываем: сначала k1 единиц, затем один нуль, после этого k 2 единиц и снова нуль. kn -1 единиц и опять нуль, наконец, kn единиц – и всё.
Поскольку сумма всех ki равна m , в построенной цепочке содержится m единиц. Нулей же п -1. Так что вся цепочка состоит из n + m – 1 цифр.
Подведём итог. Каждому возможному списку поставлена в соответствие некоторая цепочка из нулей и единиц длиной п + т — 1. При этом если два списка одинаковы, то и цепочки получатся одинаковыми. Верно и обратное: каждой цепочке соответствует определённый список. Например, цепочка говорит нам, что в списке — четыре элемента номер 1, ни одного элемента номер 2, по одному элементу номер 3 и 4 и ни одного элемента номер 5. Таким образом, задача свелась к поиску ответа на вопрос: сколько можно составить различных цепочек длиной п + т-1 из т единиц и n — 1 нулей? А это не что иное, как число перестановок с повторениями m нулей и n — 1 единиц, т. е. Pm, n-1 . Поэтому
Сnm = Pm , n -1 = n + m -1! m ! n -1!
Итак, формулы для перестановок, размещений ii сочетаний (с повторениями и без) обнаруживают тесную связь между основными понятиями комбинаторики. Эти формулы составляют своего рода азбуку комбинаторики, поскольку на них основано решение большинства школьных комбинаторных задач.
В алгебре довольно часто приходится возводить в степень двучлен a + b . Недаром каждый школьник заучивает наизусть формулы квадрата и куба суммы двух чисел. Помните, «квадрат первого числа плюс удвоенное произведение. » и т. д.? Аналогичная формула, но уже для произвольного п> О называется биномом Нъютона, хотя и была известна задолго до него. (Слово «бином» в переводе с латыни означает «двучлен».) Формула эта имеет прямое отношение к комбинаторике. 
Для удобства в выражении ( a + b ) n вынесем bn за скобки и обозначим a / b через х. Получается bn ( x + 1) n . На время забудем про множитель bn и будем искать формулу для (х + 1) n . Нетрудно догадаться, что после раскрытия скобок перед нами предстанет многочлен п-й степени. Нужно только определить коэффициенты при различных степенях х.
Поступим следующим образом. Выпишем произведение из n скобок (х + 1):
Теперь раскроем скобки, но при этом не будем приводить подобные члены. Например:
( x +1)3 = ( x + 1)(х +1)(х + 1) = x 3 + x 2 + x 2 + x + x 2 + x + x + 1 и т. д.
Естественно, результат представляет собой сумму каких-то степеней х (в том числе и нулевой, т. е. 1).
Наконец, соберём все x по одинаковым степеням и получим многочлен n -й степени уже в привычном виде. Ясно, что коэффициент при х m будет равен количеству слагаемых х m в первоначальном, не приведённом виде. Сколько их? Ещё не зная, как ответить на этот вопрос, мы уже чувствуем, что перед нами комбинаторная задача.
биномиальные коэффициенты и сочетания.
После перемножения п скобок (х +1) любая появившаяся степень х возникла как произведение n сомножителей — по одному от каждой скобки. Но все сомножители равны либо x , либо 1. Для появления m -й степени х необходимо, чтобы при перемножении ровно из m скобок были взяты сомножители х, а из остальных п — т скобок — 1. Сколькими способами можно выбрать т объектов (в данном случае скобок) из п возможных? Или, другими словами, каково число сочетаний из п элементов по m? Ответ мы знаем: Cnm . Итак, раскрыв все скобки, получим Cnm слагаемых, равных х m , и, значит, после приведения подобных членов коэффициент при х m равен Cnm . 
( x + 1) n = Cnnxn + Cnn-1xn-1 + Cnn-2xn-2 + … + Cn1x + Cn0
Так как числа Cnm являются коэффициентами в формуле бинома Ньютона, они называются биномиальными коэффициентами. Попробуйте выписать формулы бинома ( x + 1) n для некоторых конкретных значений x , например для х= 0, ±1, ±2, ±1/2.
Нетрудно вывести подобную формулу и для (а + b ) n . Надо только вспомнить, что
a/b = x и ( а + b)n =bn(x+1)n .
В результате получим:
(а + b ) n = Cnnan + Cnn-1an-1b + Cnn-2an-2b2 + … + Cn1abn-1 + Cn0bn
Проверим данную формулу для п = 3:
( а + b)3 = C33a3 + C32a2b + C31ab2 + C30b3
C33 = C30 = 3!3!∙0! = 1 и C32 = C31 = 3!2!∙1! = 3
(a + b)3 = a 3 + 3 a 2 b + 3 ab 2 + b 3
— знакомая формула куба двучлена!
Формула бинома Ньютона позволяет обнаружить важную зависимость между биномиальными коэффициентами. Рассмотрим формулу для ( x + 1) n +1 . Чему равен коэффициент при xm+1? Ясно, что это Cn +1 m +1 . С другой стороны, ( x + 1) n +1 можно получить, умножив формулу для ( x + 1) n на ( x + 1). Тогда (m + 1)-я степень числа x может быть получена либо при умножении слагаемого Cnmxm на x , либо при умножении Cnm+1xm+1 на 1. Поэтому коэффициент Cn+1m+1 в формуле для ( x + 1) n +1 должен быть равен сумме Cnm и Cnm+1 , т. е.
Cn+1m+1 = Cnm + Cnm+1
Эта формула позволяет довольно легко построить таблицу биномиальных коэффициент, не вычисляя их по отдельности с помощью
громоздкой формулы n ! m ! n — m ! . Начнём c того, что выпишем в одну строку бесконечное число нулей и только одну единицу среди них:
Ниже создадим вторую строку чисел, записывая между каждыми двумя числами первой строки их сумму. Затем под второй строк запишем по тем же правилам третью, четвертую и т. д.: 
Смотрите, как стремительно увеличиваются ненулевые числа, расползаясь вправо и влево! Чтобы нагляднее представить результат, сотрём все нули, а строки пронумеруем, начиная с нуля (рис. 1).
Впервые этот цифровой треугольник подробно описал французский
математик Блез Паскаль в своём «Трактате об арифметическом треугольнике» (опубликован в 1665 г.). С тех пор он так и называется — треугольник Паскаля. Несколько иные варианты этой таблицы были известны итальянцу Никколо Тарталье, персидскому поэту и учёному Омару Хайяму, китайским и индийским математикам.
В треугольнике Паскаля п-я строка содержит биномиальные коэффициенты Cn 0 , Cn1, Cn2, … Cnn. Это следует из формулы, которая применительно к построенной таблице означает, что каждое число равно сумме двух вышестоящих.
Треугольник Паскаля обладает множеством замечательных свойств. Например, сумма чисел п-й сроки треугольника равна 2 n . Чтобы доказать это, достаточно рассмотреть бином, у которого а = b =1.С одной стороны, он равен 2 n , а с другой — сумме всех биномиальных коэффициентов этой строки.
Другое свойство: количество нечётных чисел в п-й строке всегда равно степени двойки, более того, оно равно 2 k , где k — число единиц в двоичной записи числа п. Например, 5-я строка содержит числа 1, 5, 10, 10, 5, 1, среди которых 4 нечётных. В то же время число 5 в двоичной системе счисления записывается как 101. Число 101 содержит 2 единицы, и 2 n =4. Доказать это
свойство гораздо сложнее, чем первое.
Ещё одно свойство треугольника Паскаля в каждой строке сумма чисел, стоящих на нечётных местах, равна сумме чисел, стоящих на чётных местах. Чтобы убедиться в этом, рассмотрите бином, у которого а= 1, b = -1. Кроме того, если номер строки — простое число, то все числа в строке, за исключением двух крайних единиц, делятся на номер строки.
1. »Энциклопедия для детей. Том 11. Математика». Авантг. Москва.
2. Магидович энциклопедий Аванта+ Астрель АСТ. 2009г. Москва.
3. Станислав Коваль. «От развлечения к знаниям». Wydawnictwa Naukowo — Techniczne . 1972г. Варшава.
Источник
