Множества. Комбинаторика. Отношения (стр. 4 )

3)  Сколько существует пятизначных чисел, которые одинаково читаются справа налево, и слева направо?

Решение: Такие числа имеют вид: XYZYX. Начинаем выбирать цифры: первая цифра – 9 способов, вторая – 10, третья – 10. А четвертая и пятая у нас уже выбраны. Получаем: 9х10х10=900 чисел.

Набор элементов ai1,..., air из множества М={a1,..., a1} называется выборкой объема r из n – элементов. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

Упражнение

Докажите правила суммы и умножения, как теоремы.

1.2.1. Размещения

Размещением из n по r называется упорядоченная выборка объема r из n различных элементов.(n-r перестановка).

Например, все размещения из четырех объектов А, В, С, Д по 2:

АВ, АС, АД, ВА, ВС, ВД, СА, СВ, СД, ДА, ДВ, ДС.

Число всех различных размещений из n по r обозначается Аrn.

ТЕОРЕМА.

Аrn = n(n – 1)(n – 2)(n – 3)... ( n – r +1), (1)

Доказательство. А1n = n. Перейдем к нахождению А2n.

Мы имеем (n – 1) размещений, в которых на первом месте стоит первый элемент; (n – 1) размещений, в которых на первом месте стоит второй элемент, (n – 1) размещений, в которых на первом месте стоит третий элемент, ... , (n – 1) размещений, в которых на первом месте стоит n-ый элемент, т. е. А2n = n(n –1). Возникает гипотеза, что

Аkn = n(n – 1)(n – 2)(n – 3)... (n – k +1).

Перейдем к нахождению Аk+1n при такой гипотезе. Каждое размещение из n по k может дать n – k размещений из n по k+1, после присоединения одного из объектов, не вошедших в него, отсюда

Аk+1n = (n –k)Аkn = n(n – 1)(n – 2)(n – 3)… (n – k).

Доказательство 2. Воспользуемся правилом произведения: Начинаем выбирать первый элемент. У нас существует n способов это сделать. Второй – (n-1) способ, так как один мы уже выбрали, и так далее. Перед тем, как выбрать k элемент, мы уже выбрали (k-1) элемент, то есть для выбора k элемента нам осталось только (n-(k-1)) элемент. А так как мы выбираем и первый, и второй и т. д. элемент, то все эти числа мы должны перемножить. Получаем: . ■

Перестановкой n-ной степени называется взаимное расположение n элементов относительно друг друга, т. е. размещение из n по n.

Например: Пусть дано множество B={a, b, c}. Тогда все его различные перестановки:

{a, b, c}, {a, c, b,}, {b, a, c}, {b, c, a}, {c, a, b,}, {c, b, a}.

Число всех различных перестановок n-ной степени обозначается через Рn. Тогда Рn = Аnn = n(n –1)(n –2)×...×2×1, т. е.:

Рn = n! (2).

В новых обозначениях формулу (1) можно переписать в виде Arn =n!/(n-r)!. Договоримся также, что 0!=1.

Замечание: Факториал – это произведение последовательных натуральных чисел до указанного, включая его самого.

Например: 3!=1х2х3=6

5!=1х2х3х4х5=120

8!=1х2х3х4х5х6х7х8=40320.

Упражнения

1) Выведите формулу Аrn = n Аr-1n-1.

2) Пусть |X| = n, |У| = m. Докажите, что число всех взаимнооднозначных отображений Х в У равно Аnm .

3) Сколько всего семизначных телефонных номеров, в каждом из которых ни одна цифра не повторяется? (А710 ).

1.2.2. Сочетания

Сочетанием из n по r называется неупорядоченная выборка объема r из n элементов, т. е. любое подмножество, состоящее из r элементов, взятых из множествa n элементов.

Число всех различных сочетаний из n по r обозначается С rn.

Например: пусть дано множество B={a, b, c}. Выпишем все различные сочетания из 3 по 2: {a, b}, {a, c}, {b, c}.

Заметим, что С 0n = 1, С 1n = n, С nn = 1.

Замечание: очень важно увидеть разницу между сочетаниями и размещениями. В сочетании нам не важен порядок расположения элементов, нам важно только их наличие. А в размещениях, наряду с наличием, важно и как они расположены относительно друг друга. Т. е., когда мы составляем какой-нибудь номер, нам, очевидно, важно в каком порядке идут цифры (вам же важно, что вы живете в квартире 123 или 132), а, например, если мы хотим выбрать делегацию из 3 человек, нам абсолютно не важно, в каком порядке они выбраны, нам важно, что именно эти трое поедут в командировку, т. е. их наличие.

ТЕОРЕМА (правило симметрии).

С rn = С n-rn (1).

Доказательство. Выбор r элементов равносилен отбору (n-r) элементов, не включаемых в выборку. g

ТЕОРЕМА (формула Паскаля).

С rn = С rn-1 + С r-1n-1 (2).

Доказательство. Фиксируем один из объектов. Все сочетания разбиваются на два класса: класс сочетаний, не содержащих фиксированный элемент (в нем Сrn-1 сочетаний), и класс сочетаний, содержащих фиксированный элемент (в нем Сrn-1 сочетаний). Отсюда и следует формула Паскаля. ■

Значения С rn могут быть последовательно записаны с помощью этой формулы в треугольник Паскаля.

0 1

1 1 1

2 1 2 1

3 1 3 3 1

4 1 4 6 4 1

5 1 5 10 10 5 1

6 1 6 15 20 15 6 1

7 1 7 21 35 35 21 7 1

n C0n C1n C2n … Cnn.

Выбрать r из n разных объектов можно Сrn способами. Имеется r! возможностей упорядочить объекты каждого сочетания. Согласно правилу умножения имеется r! Сrn возможностей выбрать и разместить по r разным местам r из n разных объектов, т. е. A rn = r! С rn. Отсюда

С rn = n! / (r!(n –r)!) (3),

или

С rn = n(n–1) … (n–r+1) / r! (4)

Упражнения

1)  Докажите формулы

С rn = С r -1n -1 + С r -1n -2 +...+ С r -1r + С r -1r -1 (5),

С rn = С rn -1 + С r -1n -2 + С r -2r -3 + С 0n – r -1 (6).

2)  С помощью формулы Паскаля докажите формулу (4) подсчета С rn.

3)  Сколькими способами можно распределить 12 различных предметов между тремя лицами так, чтобы каждый получил по четыре предмета? (Ответ: С412С48 = 34650).

4)  Сколькими способами можно разместить в ряд p+q шаров, из которых p белых и q черных (p > q) при условии, что черные шары не могут лежать рядом. Ответ: Cqp+q

5)  На прямой взяты 10 точек, а на параллельной ей прямой – еще 7 точек. Сколько существует треугольников, вершинами которых являются эти точки? (Ответ: +).

6)  Сколькими способами можно разложить в три пакета 8 различных книг? (Ответ: 38).

7)  Сколькими способами можно послать 8 различных фотографий, использовав 5 различных конвертов? (Ответ: 85)

8)  Сколькими способами 12 полтинников можно разложить по 5 различным карманам, если ни один из карманов не должен быть пустым? (Решение: сначала разложим 5 полтинников по одному в каждый карман, осталось 7 полтинников. Теперь используем способ “разделительных нулей”. Все полтинники обозначим единицами, и будем разделять их нулями. Например: комбинация “10101011110” означает, что в первом кармане один полтинник, во втором и третьем – 1, в четвертом – 4, а пятый карман пустой. Очевидно, что всевозможные комбинации из 7 единиц и четырех нулей определяют все возможные расположения полтинников. Значит, наша задача свелась к нахождению числа таких различных комбинаций. Переставляем все цифры, число таких перестановок – 11!, но ведь есть одинаковые элементы, значит, искомых случаев будет в 7!4! раза меньше. Получаем ответ: 11!/7!4!).

9)  Сколькими способами можно вынуть 4 карты из колоды, содержащей 36 карт, так, чтобы были все четыре масти? (Ответ: . Пояснение: сначала выбираем 3 масти, которые вынимаем, а потом из каждой масти по одной карте).

10)  Сколькими способами можно переставить буквы слова “кофеварка” так, чтобы гласные и согласные буквы чередовались? (Решение: очевидно, что слово должно начинаться с согласной, и мы расставляем их через одну, всего способов – 5!, затем на свободные места ставим гласные, получаем – 4!/2!. Так как мы проделываем и одно и другое, то по правилу произведения мы должны эти числа перемножить. Ответ: 5!х4!/2!).

11)  Сколько делителей у числа 210? (Решение: Разложим число 210 на простые множи=2х5х3х7. Любой делитель – это различные произведения простых сомножителей. Значит, наша задача – найти их число. Число 2 может либо входить в это произведение, либо не входить, следовательно, для него существует 2 возможности, аналогично, и для всех остальных чисел существует по 2 возможности. Далее, по правилу произведения получаем: 24)

12)  Сколько четырехзначных чисел можно составить из цифр числа 132132?

13)  Сколькими способами можно переставить цифры числа 12312343 так, чтобы три одинаковые цифры не шли друг за другом?

1.2.3. Бином Ньютона

Заметим, что

(1+t1) (1+t2)... (1+tn) = 1+ (t1 + t2 + ... + tn) + (t1t2 + t1 t3 + ... + tn-1tn) +…

При t = t1 = t2 =...=tn имеем

(1 + t)n = 1 +nt + C2nt2 + C3nt3 + C4nt4 +...+ Cnntn (1).

При t =b /a – получим бином Ньютона

(a + b)n = an + C1nan -1b + C2nan -2b2 + ... + Cnnbn (2).

Здесь в качестве коэффициентов стоят Crn, поэтому эти числа C0n , C1n, C2n,...,Crn называют биномиальными коэффициентами.

Свойства бинома Ньютона:

1) степени a убывают в слагаемых правой части от n до 0,

2) степени b возрастают от 0 до n,

3) в каждом слагаемом сумма степеней a и b равна n,

4) коэффициенты Crn при симметричны относительно середины суммы.

При a = b = 1 из формулы Ньютона получим:

C0n + C1n + C2n + ...+ Cnn =2n (3).

Если положить a = 1, b = –1, то получим:

C0n – C1n + C2n – ...+(–1)n Cnn = 0 (4).

Упражнения

Докажите:

1) k Ckn = n 2n–1;

2) Сkn / (k+1) = (2n+1 –1)/ (n+1);