Элементы дискретной математики - 18 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

Составители: 

Рубрика: 

18
Комбинаторное доказательство.
Составим k-сочетание из n элементов а
1
, а
2
, …,a
n
и разобьем их на два класса. В
первый из них войдут сочетания, содержащие элемент a
n
, во второй – не содержащие этого
элемента. Если из любого сочетания первого класса откинуть элемент а
n
, то останется (к –1)-
сочетание, составленное из элементов а
1
, а
2
, …, a
n-1.
Число таких сочетаний равно
1
1
−
−
k
n
C .
Поэтому в первый класс входит
1
1
−
−
k
n
C
комбинаций. Сочетания второго класса являются k-
сочетаниями, составленными из элементов а
1
, а
2
, …,a
n-1.
Поэтому их число равно
k
n
C
1−
.
Поскольку любое k-сочетание принадлежит одному и только одному из этих классов, а
общее число этих сочетаний равно
k
n
C , то, используя правило сложения, приходим к
искомому равенству.
4 свойство:
nn
n
k
nnn
CCCC 2......
10
=+++++
Комбинаторное доказательство.
2
n
– число всех размещений с повторениями из элементов двух типов. Разобьем эти
размещения на классы, отнеся в k-ый класс те, в которые входят k элементов первого типа и
n–k элементов второго типа. Размещения k-го типа - это ни что иное, как всевозможные
перестановки из k элементов первого типа и n–k элементов второго типа. Число таких
перестановок
равно P(k, n–k)=C(n, k). По правилу суммы общее число размещений всех
классов равно
n
n
k
nnn
CCCC +++++ ......
10
. С другой стороны, это же число равно 2
n
.
5 свойство: 0)1(...)1(...
210
=−++−++−
n
n
nk
n
k
nnn
CCCCC
Комбинаторное доказательство.
Выпишем все сочетания из n элементов а
1
, …,а
n
и сделаем следующее
преобразование: к сочетанию, не содержащему элемент а
1
, допишем его, а из сочетаний,
куда оно входит, вычеркнем. Легко проверить, что при этом снова получаются все
сочетания, и притом по одному разу. Но при этом преобразовании все сочетания, имевшие
четное число элементов, превратятся в сочетания, имеющие нечетное число элементов, и
обратно. Значит сочетаний с четным и нечетным количеством элементов
одинаковое
количество (пустое сочетание тоже входит в рассмотрение). Это и выражает данная
формула.
Задача.
На окружности отмечено 11 точек. Сколько существует многоугольников с вершинами
в отмеченных точках?
Решение.

Страницы