Лемма 1

Теорема

Число сочетаний из n по k:

По определению 0!=1. Факториал относится к натуральным числам, поэтому считается, чо упорядочить 0 объектов можно единственным образом.

При решении задач комбинаторики используются следующие правила:

1. Правило суммы: если некоторый объект A может быть выбран из множества объектов m-способами, а другой объект B может быть выбран n-способами, то выбрать либо A, либо B можно m+n способами («или» это +)

2. Правило произведения: если некоторый объект A может быть выбран из множества объектов m-способами, и после каждого такого выбора объект B может быть выбран n-способами, то пара объектов AB в указанном порядке может быть выбрана m∙n способами («и» это ∙)

Принцип математической индукции –

Утверждение P(k) зависящее от натурального числа k справедливо при любом k из N, если утверждение P(k) справедливо при k=1

Для всякого l из N из справедливости P(l) следует справедливость P(l+1).

Каково бы ни было целое число n≥1, число различных размещений по одному объекту из заданных n равно:

У нас n объектов. Мы можем выбрать каждый объект только одним способом.

Число есть суммарное число различных способов, какими один объект может быть выбран из n объектов. Выбранным может быть либо первый, либо второй, либо третий …. либо n-ый:

Дата добавления: 2015-04-24