Очевидно, что число способов получения множества

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 5Следующая ⇒

Перестановки.

Содержание задачи о числе перестановок сводится к следующему: сколькими разными способами можно переставить n различных предметов?

! В данном случае важно взаимное расположение предметов !

Пример 4. Сколькими различными способами можно переставить 3 монеты в 1, 2 и 3 копейки?

Решение: ½{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}½=6 способов.

В общем случае число всех возможных перестановок из n предметов обозначается Р(n) и определяется формулой Р(n) = n!

Доказательство: Пусть есть множество из n предметов. На первое место можно поставить любой из n предметов. После того, как заполнено первое место, на второе можно поставить любой из (n-1) оставшихся предметов и т.д. По правилу умножения получим: n*(n-1)*(n-2)….2*1=n!, что и требовалось доказать.

Подстановки.

Рассмотрим множества А и В, каждое из n элементов. Подстановкой множества А в множество В называется взаимнооднозначное отображение множества А в множество В.

Если мощности А и В равны и |A|=|B|=n, то число всех возможных подстановок множества А в множество В оценивается формулой Р(n) = n!

Очевидно, что перестановки n различных предметов, расположенных на n различных местах есть подстановки множества из n различных предметов в множество из n различных мест!

Пример 5*. Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы они не били друг друга?

Решение:

Пример 6. Сколько способов есть разложить 10 писем по десяти разным конвертам? Ответ:10!

Размещения.

Суть задачи о размещениях: сколько есть способов для размещения по m различным местам m из n различных предметов?

Пример 6. Сколькими способами можно разместить по двум местам 1 и 2 две из трех монет в 1, 2 и 3 копейки? Взаимное расположение важно!

№ мест

1и2

1и2

1и2

1и2

1и2

1и2

монеты

1,2

1,3

2,3

2,1

3,1

3,2

Ответ: 6 способов.

Общая формула:

Иначе можно записать:

Доказательство: Число подмножеств из m элементов каждое, которые выбираются из n элементов, равно  . Так как в определении понятия размещения играет роль место, на котором находится элемент, то каждое подмножество из m элементов можно расставить m! способами, следовательно, число всех размещений:

Пример 7. Сколькими способами можно выбрать и разместить в ряд на книжной полке 3 из 5 различных книг?

Пример 8. Сколькими различными способами можно обозначить треугольник, отмечая его вершины различными буквами (большими) латинского алфавита (букв 26 штук)?

Разбиения.

Суть задачи о разбиениях: сколькими способами можно разложить множество А мощностью n на m попарно непересекающихся подмножеств Ві таким образом, что   и если |B₁|=K₁,  |B₂|=K₂ , …, то К1 + К2 +…=n

Общее число разбиений множества А:

Эту формулу и суть разбиения можно объяснить таким образом:

   Пусть есть множество А из n элементов:

Тогда разбиение множества А на m взаимно непересекающихся подмножеств показано на рисунке.

Тогда по правилу умножения общее число способов:

Пример 10. Сколькими способами можно распределить 6 шаров в 3 ящика (№1, №2 и №3) так, чтобы в ящике №1 был всегда один шар, в ящике №2 – два шара, в ящике №3- три шара.

Решение: Задача сводится к отысканию 1,2,3- разбиения множества шаров. Число таких разбиений:

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров