 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Свойства биноминальных коэффициентов. Треугольник Паскаля
|
|
Числа 
обладают целым рядом замечательных свойств, перечислять которые можно очень долго. Мы выделим здесь только некоторые:
1. 
2. 
3. 
4. Если 
и 
, то 
.
Все эти свойства можно доказать аналитически, используя только что выведенную формулу для 
, но интереснее провести их комбинаторное доказательство:
a. Выбрать 0 (так же, как и все 
) элементов из возможных можно только одним способом.
b. Выбрать 
элементов из – это все равно, что указать те 
элементов, которые мы не выбираем.
c. Любое сочетание из по является -элементным подмножеством -элементного множества. Число - это количество таких подмножеств. Сумма таких чисел по всем от 0 до дает (по правилу сложения) количество всех возможных подмножеств -элементного множества.
Теперь посчитаем это же количество по-другому. Любое подмножество -элементного множества можно закодировать двоичной (т.е. состоящей из 0 и 1) последовательностью длины : на 
-м месте стоит 1, если -й элемент входит в это подмножество, 0 – если не входит. А всего таких последовательностей (а значит и всех возможных подмножеств) по правилу умножения 
.
Зафиксируем какой-то один из элементов нашего множества и обозначим его 
. Все -элементные подмножества можно разбить на два непересекающихся класса: содержащие и не содержащие . Количество подмножеств, содержащих , можно посчитать так: один элемент уже выбран, остается выбрать еще 
элемент из 
– это можно сделать 
способами. Количество подмножеств, не содержащих , можно посчитать так: элемент выбирать нельзя, значит, нужно выбрать элементов из – это можно сделать 
способами. По правилу сложения общее количество -элементных подмножеств будет равно 
.
Последнее из доказанных свойств позволяет вычислять числа не по выведенной ранее формуле с факториалами, а рекуррентно, последовательно выражая числа с бóльшим значением через предыдущие:
Шаг 1. Найдем 
Шаг 2. Найдем  . Выразим  через уже известные: 
Шаг 3. Найдем  . Выразим  через уже известные:  , 
… и так далее.
Процесс вычисления чисел удобно организовать в виде таблицы (еще одно применение таблиц!): будем заносить в -ю строку этой таблицы все числа  . Поскольку в -ой строке будет таких чисел, то таблица получится «треугольной»:
Причем закономерность заполнения клеток в этой таблице очень простая: в первую клетку очередной строки ставим 1, а в каждую следующую – сумму чисел стоящих в предыдущей строке левее и над ним (например: 2 = 1 + 1); заканчиваем строку также 1. Полученная треугольная таблица получила название треугольник Паскаля, по имени великого французского математика Блеза Паскаля, изучавшего свойства этого треугольника и использовавшего его при решении вероятностных задач. Дата публикования: 2015-03-26; Прочитано: 439 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!  |