АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Элементы комбинаторики

10.1 Пусть есть некоторое конечное множество элементов U = {a₁, a₂,..., a_n}. Рассмотрим набор элементов , где ÎU, j = 1, 2,..., r. Этот набор называется выборкой объема r из n элементов. Любое подмножество U является выборкой, но не всякая выборка является подмножеством U, так как в выборку один и тот же элемент может входить несколько раз (в отличие от подмножества).

Комбинаторные задачи связаны с подсчетом числа выборок объема r из n элементов, где выборки подчиняются определенным условиям, т.е. выбор производится по какому-нибудь принципу. Подсчет числа выборок основывается на двух правилах теории множеств.

10.2 Принцип суммы: если card A = m, card B = n и AÇB = Æ, то card A È B = m+n. На комбинаторном языке это означает: если объект A можно выбрать m способами, объект B другими n способами и их одновременный выбор невозможен, то выбор “A или B” может быть осуществлен m+n способами.

10.3 Принцип произведения: если card A = m, card B = n, то card (A´B) = m´n. На комбинаторном языке это означает: если объект A может быть выбран m способами, при любом выборе A объект B может быть выбран n способами, то выбор “A и B” может быть осуществлен m×n способами.

10.4 Пример. A = {10 различных шоколадок}, B = {5 различных пачек печенья}. Выбор “A или B” означает, что выбирается что-то одно и способов выбора в это случае будет 15. Выбор “A и B” означает, что выбирается 1 шоколадка и 1 пачка печенья и различных вариантов для такого выбора будет 50.

10.5 Пример. Бросают 2 игральные кости. Сколькими способами они могут выпасть так, что на каждой кости выпадет четное число очков либо на каждой кости выпадет нечетное число очков?

Пусть m - число возможностей для выпадения четного числа на одной кости, n - число возможностей для выпадения нечетного числа. Здесь m = n = 3. По правилу произведения количество выпадения четных чисел, равно как и нечетных, равно 9. По правилу суммы количество возможностей для выпадения двух четных или двух нечетных чисел будет 18.

Рассмотрим основные способы формирования выборок.

10.6 Определение. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Если порядок следования элементов несущественен, то выборка называется неупорядоченной.

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

10.7 Перестановки. Упорядоченные выборки объемом n из n элементов, где все элементы различны, называются перестановками из n элементов. Число перестановок из n элементов обозначается P_n.

10.8 Теорема. P = n!

Доказательство проводится по индукции. Очевидно, если n = 1, то перестановка только одна и P₁ = 1!. Пусть для n = k теорема верна и P_k = k!, покажем, что она тогда верна и для n = k + 1. Рассмотрим (k+1)-ый элемент, будем считать его объектом A, который можно выбрать k+1 способами. Тогда объект B - упорядоченная выборка из оставшихся k элементов по k. B соответствии с индуктивным предположением объект B можно выбрать k! способами. По принципу произведения выбор “A и B” можно осуществить k!´(k + 1) = (k + 1)! способами. А совместный выбор “A и B” есть упорядоченная выборка из k + 1 элементов по k + 1.

10.9 Пример. Сколько существует способов, чтобы расположить на полке 10 различных книг? Ответ: 10!

Можно рассуждать иначе. Выбираем первый элемент, это можно сделать n способами. Затем выбираем второй элемент, это можно сделать (n - 1) способами. По правилу произведения упорядоченный выбор двух элементов можно осуществить n´(n - 1) способами. Затем выбираем третий элемент, для его выбора останется n - 2 возможности, последний элемент можно выбрать единственным способом. Мы вновь приходим к формуле: n(n - 1)(n - r)... 1.

10.10 Размещения. Упорядоченные выборки объемом m из n элементов (m < n), где все элементы различны, называются размещениями. Число размещений из n элементов по m обозначается .

10.11 Теорема. =

Доказательство. Обозначим x = . Тогда оставшиеся (n - m) элементов можно упорядочить (n - m)! способами. По принципу произведения, если объект A можно выбрать x способами, объект B (n - m)! способами, то совместный выбор “A и B” можно осуществить x ×(n - m)! способами, но выбор “A и B” есть перестановка и P_n = n! Отсюда x = =

Рассуждая иначе: первый элемент выбираем n способами, второй - (n - 1) способами и т.д., m - ый элемент выбираем (n - m + 1) способом. По принципу произведения вновь имеем: n(n - 1)...(n - m +1), что совпадает с .

10.12 Пример. Группа из 15 человек выиграла 3 различные книги. Сколькими способами можно распределить эти книги среди группы?

Имеем = 15 ×14 ×13 = 2730.

10.13 Сочетания. Неупорядоченные выборки объемом m из n элементов (m < n) называются сочетаниями. Их число обозначается .

10.14 Теорема.

Доказательство. Очевидно, Действительно, объект A - неупорядоченная выборка из n элементов по m, их число . После того, как эти m элементов отобраны, их можно упорядочить m! способами (в роли объекта B выступает “ порядок “ в выборке). Совместный выбор “A и B“ - упорядоченная выборка.

10.15 Пример. Группа из 15 человек выиграла 3 одинаковые книги. Сколькими способами можно распределить эти книги?

Сочетания, размещения и перестановки являлись подмножествами исходного множества. Рассмотрим выборки, которые не являются подмножествами.

10.16 Размещения с повторениями. Упорядоченные выборки объемом m из n элементов, где элементы могут повторяться, называются размещениями с повторениями. Их число обозначается (n).

10.17 Теорема. (n) = n^m.

Доказательство. Первый элемент может быть выбран n способами, второй элемент также может быть выбран n способами и так далее, m -тый элемент также может быть выбран n способами. По принципу произведения получаем n^m.

10.18 Пример. Кодовый замок состоит из четырех разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций?

Здесь n = 10, m = 4 и ответом будет 10⁴.

10.19 Пример. Рассмотрим вектор длины m, каждая координата которого может принимать всего 2 значения: 0 или 1. Сколько будет таких векторов?

Это есть выборка объемом m из двух элементов. Ответ: 2^m

10.20 Перестановки с повторениями. Пусть имеется n элементов, среди которых k₁ элементов первого типа, k₂ элементов второго типа и т.д., k_s элементов s-того типа, причем k₁ + k₂ +... + k_s = n. Упорядоченные выборки из таких n элементов по n называются перестановками с повторениями, их число обозначается С_n(k₁, k₂,..., k_s). Числа С_n(k₁, k₂,..., k_s) называются полиномиальными коэффициентами.

10.21 Теорема. С_n(k₁,..., k_s) =

Доказательство проведем по индукции по s, то есть по числу типов элементов. При s = 1 утверждение становится тривиальным: k₁ = n, все элементы одного типа и С_n(n) = 1. В качестве базы индукции возьмем s = 2, n = k₁ + k₂. В этом случаем перестановки с повторениями превращаются в сочетания из n элементов по k₁ (или k ₂): выбираем k₁ место, куда помещаем элементы первого типа.

С_n(k₁ k₂) =

Пусть формула верна для s = m, т.е. n = k₁ +... + k_m и

С_n(k₁,..., k_m)=

Докажем, что она верна для s = m + 1 (n = k₁ +... + k_m + k_m+1). В этом случае перестановку с повторениями можно рассматривать как совместный выбор двух объектов: объект A - выбор k _{m + 1} места для элементов (m + 1)-го типа; объект B - перестановка с повторениями из (n - k_m+1) элементов. Объект A можно выбрать способом, B - (k₁,..., k_m) способами. По принципу произведения

и мы получили требуемую формулу.

Замечание. Числа называются биноминальными коэффициентами. Из этой формулы следует, что

10.22 Пример. Сколько различных слов можно получить, переставляя буквы в слове “математика”?

Решение. Буква “а” входит 3 раза (k ₁= 3), буква “м” - 2 раза (k₂ = 2), “т”-2 раза (k₃ = 2), буквы “е”,”к”,”и” входят по одному разу, отсюда k₃ = k₄ = k₅ = 1.

С₁₀ (3, 2, 2, 1, 1, 1) = =151200.

10.23 Сочетания с повторениями. Пусть имеется n типов элементов, каждый тип содержит не менее m одинаковых элементов. Неупорядоченная выборка объемом m из имеющихся элементов (их число ³ m´n) называется сочетанием с повторениями. Число сочетаний с повторениями обозначается (n).

10.24 Теорема. (n) = .

Доказательство. Пусть в выборку вошло m₁ элементов первого типа, m₂ элементов вторго типа,... m_n - n - ного типа. Причем каждое 0 £ m_i £ m и m₁ + m₂ +... + m_n = m. Сопоставим этой выборке вектор следующего вида:

Очевидно, между множеством неупорядоченных выборок с повторениями и множеством векторов {b_m} существует биекция (докажите это!). Следовательно, (n) равно числу векторов b_m. “ Длина вектора” b_m равна числу нулей и единиц, или m + n - 1.

Число векторов равно числу способов, которыми m единиц можно поставить на m + n - 1мест, а это будет .

10.25 Пример. В кондитерской имеется 7 видов пирожных. Покупатель берет 4 пирожных. Сколькими способами он может это сделать? (Предполагается, что пирожных каждого вида ³ 4).

Число способов будет

10.26 Пример. Пусть V = {a, b, c}. Объем выборки m = 2. Перечислить размещения, сочетания, размещения с повторениями, сочетания с повторениями.

1. Размещения: {(ab), (bc), (ac), (ba), (cb), (ca)}.

2. Сочетания: {(ab), (ac), (bc)}.

3. Размещения с повторениями: {(ab), (bc), (ac), (ba), (cb), (ca), (aa), (bb), (cc)}. (3)= 3² = 9.

4. Сочетания с повторениями: {(ab), (bc), (ca), (aa), (bb), (cc)}.

Задачи

1. A и B и еще 8 человек стоят в очереди. Сколькими способами можно расположить людей в очереди, чтобы A и B были отделены друг от друга тремя лицами?

Ответ: 6 × 8! × 2!.

2. Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если:

а) цифры не повторяются;

б) цифры могут повторяться;

в) используются только нечетные цифры и могут повторяться;

г) должны получиться только нечетные числа и цифры могут повторяться.

Ответ: а) 5 × 5 × 4 × 3=300; б) 5 × 6³ = 1080; в) 3⁴; г) 5 × 6 × 6 × 3 = 540.

3. В классе изучается 10 предметов. Сколькими способами можно составить расписание на понедельник, если в понедельник должно быть 6 уроков и все разные?

Ответ:

4. На одной прямой взято m точек, на параллельной ей прямой n точек. Сколько треугольников с вершинами в этих точках можно получить?

Ответ:

5. Сколько есть пятизначных чисел, которые читаются одинаково справа налево и слева направо, например, 67876.

Ответ: 9 × 10 × 10 = 900.

6. Сколько разных делителей (включая 1 и само число) имеет число 3⁵ × 5⁴?

Ответ: 30.

7. В прямоугольной матрице A = {a_ij} m строк и n столбцов. Каждое a_ijÎ{+1, -1}, причем произведение a_ij по любой строке или любому столбцу равно 1. Сколько таких матриц?

Ответ: 2^(m-1)(n-1).

8. В комнате n лампочек. Сколько разных способов освещения комнаты, при которых горит:

а) ровно k лампочек (k < n);

б) хотя бы одна лампочка.

Ответ: а) C_n^k; б) C_n¹ + C_n² +... + C_nⁿ = 2ⁿ - 1

9. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей?

Ответ: С₉⁴ = 126.

10. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей?

Ответ: С₁₀⁴ = 210.

11. Имеются p белых и q черных шаров. Сколькими способами их можно выложить в ряд, чтобы никакие 2 черных шара не лежали рядом (q £ p + 1)?

Ответ: .

12. Имеется p разных книг в красных переплетах и q разных книг в синих переплетах (q £ p + 1). Сколькими способами их можно расставить в ряд, чтобы никакие две книги в синих переплетах не стояли рядом?

Ответ: × p!×q!.

13. Сколькими способами можно упорядочить {1, 2,... n} чисел так, чтобы числа 1, 2, 3 стояли рядом в порядке возрастания?

Ответ: (n - 2)!.

14. На собрании должны выступить 4 докладчика: A, B, C и D, причем B не может выступить раньше A. Сколькими способами можно установить их очередность.

Ответ: 12 = 3! + 2× 2 +2.

15.Сколькими способами m + n + s предметов можно распределить на 3 группы, чтобы в одной группе было m предметов, в другой - n, в третьей - s предметов.

Ответ:

16. Сколько целых неотрицательных решений имеет уравнение

x₁ + x₂ +... + x_m = n

Ответ: .

17. Найти число векторов a = (a₁ a₂... a_n), координаты которых удовлетворяют условиям:

1) a_i Î {0, 1};

2) a_i Î {0, 1,... k - 1};

3) a_i Î {0, 1,... k_i - 1};

4) a_i Î {0, 1} и a₁ + a₂ +... + a_n = r.

Ответ: 1) 2ⁿ; 2) kⁿ; 3) k₁ k₂... k_n; 4) .

18. Каково число матриц {a_ij}, где a_ij Î{0,1} и в которой m строк и n столбцов?

1) строки могут повторяться;

2) строки попарно различны.

Ответ: 1) 2^m×n; 2) .

19. Дано m предметов одного сорта и n другого. Найти число выборок, составленных из r элементов одного сорта и s другого.

Ответ: .

20. Сколькими способами число n можно представить в виде суммы k натуральных слагаемых (представления, различающиеся лишь порядком слагаемых считаются разными).

Ответ: .

Дата добавления: 2015-09-27 | Просмотры: 793 | Нарушение авторских прав