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

Карпов А.В.

Веснин В.Р.

Еникеев М.И., Кочетков О.Л.

Ромашов О.В.

Социология труда: Учеб. пособие. – М.: Гардарики, 1999. – 320с.

Общая, социальная и юридическая психология. Краткий энциклопедический словарь. М.: Юридическая литература, 1997. – 448 с.

Практический менеджмент персонала. Пособие по кадровой работе – М.: Юристъ, 1998. – 496 с.

Психология менеджмента. Учеб. пособие. – М.: Гардарики, 1996. – 584 с.

Комбинаторика изучает комбинаторные конфигурации – системы из конечного числа элементов, удовлетворяющие некоторым условиям.

Главные задачи комбинаторики

1. Задача перечислительной комбинаторики. Найти число комбинаторных конфигураций с заданными свойствами.

2. Существует ли комбинаторная конфигурация с (очень сложными) заданными свойствами?

3. Алгоритмическая задача. Найти метод генерации комбинаторных конфигураций с заданными свойствами.

4. Оптимизационная задача. Найти комбинаторную конфигурацию с экстремальным значением некоторого параметра.

Простейшие комбинаторные конфигурации

Если множество A имеет в точности n элементов, то для краткости говорят, что A есть n- множество.

1. Сочетания без повторений по m из n элементов – это произвольные m- подмножества заданного n- множества.

Пример 1. Перечислим все сочетания без повторений по 2 из 4 элементов множества {1,2,3,4}:

{1,2}, {1,3}, {1,4},

{2,3}, {2,4},

{3,4}.

2. Сочетания с повторениями по m из n элементов – это подмножества { f ₁,…, f_m } заданного n- множества, содержащие некоторые элементы в более чем одном экземпляре. В теории множеств сочетание с повторениями представляется следующим образом. Пусть f – некоторое отображение множества {1,2,…, m } в заданное n- множество A. Тогда сочетание с повторениями по m из n элементов множества A можно представить как график отображения f:

{ f ₁,…, f_m }={(1, f (1)),…,(m, f (m)}.

Пример 2. Перечислим все сочетания с повторениями по 2 из 4 элементов множества {1,2,3,4}:

{1,1}, {1,2}, {1,3}, {1,4},

{2,2}, {2,3}, {2,4},

{3,3}, {3,4},

{4,4}.

Пример 3. Перечислим все сочетания с повторениями по 4 из 2 элементов множества {1,2}:

{1,1,1,1}, {1,1,1,2}, {1,1,2,2}, {1,2,2,2}, {2,2,2,2}.

3. Размещения без повторений по m из n элементов – это произвольные кортежи длины m различных элементов заданного n- множества.

Пример 4. Перечислим все размещения без повторений по 2 из 4 элементов множества {1,2,3,4}:

(1,2), (1,3), (1,4),

(2,1), (2,3), (2,4),

(3,1), (3,2), (3,4),

(4,1), (4,2), (4,3).

4. Размещения с повторениями по m из n элементов – это произвольные кортежи длины m элементов заданного n- множества.

Пример 5. Перечислим все размещения с повторениями по 2 из 4 элементов множества {1,2,3,4}:

(1,1), (1,2), (1,3), (1,4),

(2,1), (2,2), (2,3), (2,4),

(3,1), (3,2), (3,3), (3,4),

(4,1), (4,2), (4,3), (4,4).

Пример 6. Перечислим все размещения с повторениями по 4 из 2 элементов множества {1,2}:

(1,1,1,1), (1,1,1,2),

(1,1,2,1), (1,1,2,2),

(1,2,1,1), (1,2,1,2),

(1,2,2,1), (1,2,2,2),

(2,1,1,1), (2,1,1,2),

(2,1,2,1), (2,1,2,2),

(2,2,1,1), (2,2,1,2),

(2,2,2,1), (2,2,2,2).

Основные правила комбинаторики

Если множество A имеет в точности n элементов, то также говорят, что число элементов множества A равно n и пишут | A |= n.

Вначале сформулируем основные правила комбинаторики на языке теории множеств.

Правило суммы. Пусть | A |= m, | B |= n и A Ç B =Æ. Тогда | A È B |= m + n.

Правило произведения. Пусть | A |= m и | B |= n. Тогда | A ´ B |= m + n.

Правило суммы может быть обобщено: если множества A ₁, …, A_n попарно не пересекаются, | A ₁|= m ₁, …, | A_n |= m_n, то | A ₁È…È A_n |= m ₁+…+ m_n.

Правило произведения тоже может быть обобщено: если | A ₁|= m ₁, …, | A_n |= m_n, то | A ₁´…´ A_n |= m ₁×…× m_n.

Теперь сформулируем обобщенные основные правила комбинаторики на собственном языке комбинаторики.

Правило суммы. Если элементы попарно не пересекающихся множеств A ₁, …, A_n могут быть выбраны соответственно m ₁, …, m_n способами, то элемент объединения A ₁È…È A_n может быть выбран m ₁+…+ m_n способами.

Правило произведения. Если элементы каждого из множеств A ₁, …, A_n независимо от выбора элементов остальных множеств могут быть выбраны соответственно m ₁, …, m_n способами, то кортеж элементов из декартова произведения A ₁´…´ A_n может быть выбран m ₁×…× m_n способами.

Формула включений и исключений

Правило суммы можно ещё сформулировать следующим образом:

если A Ç B =Æ, то | A È B |=| A |+| B |.

Теорема 1. | A È B |=| A |+| B |-| A Ç B |.

Доказательство. Так как множества A B и B, а также A B и A Ç B не пересекаются, (A B)È B = A È B, (A B)È(A Ç B)= A, то по правилу суммы

| A È B |=| A B |+| B |,

| A |=| A B |+| A Ç B |.

Из первого равенства по частям вычтем второе, получим

| A È B |-| A |=| B |-| A Ç B |. ð

Задача 1. В группе 25 студентов. Из них 16 учат английский, 12 – немецкий, 5 – английский и немецкий. Сколько человек в группе освобождены от изучения английского и немецкого языков?

Решение. Пусть A и B – множества студентов, изучающих соответственно английский и немецкий. Тогда A Ç B – множество студентов, изучающих оба языка, A È B – множество человек в группе, изучающих хотя бы один из двух языков. В силу теоремы 1, | A È B |=| A |+| B |-| A Ç B |=16+12-5=23. Число студентов, освобожденных от изучения языков: 25-23=2.

Объединение и пересечение n множеств определяется аналогично объединению и пересечению двух множеств:

объединение A ₁È…È A_n содержит те, и только те, элементы, которые принадлежат хотя бы одному из множеств A ₁,…, A_n;

пересечение A ₁Ç…Ç A_n содержит те, и только те, элементы, которые принадлежат каждому из множеств A ₁,…, A_n.

Теорема 2. | A È B È C |=| A |+| B |+| C |-| A Ç B |-| A Ç C |-| B Ç C |+| A Ç B Ç C |.

Доказательство. Так как A È B È C =(A È B)È C, то, в силу теоремы 1,

| A È B È C |=| A È B |+| C |-|(A È B)Ç C |.

Используем свойство дистрибутивности пересечения относительно объединения: (A È B)Ç C =(A Ç C)È(B Ç C). И ещё раз применим теорему 1:

|(A Ç C)È(B Ç C)|=| A Ç C |+| B Ç C |-|(A Ç C)Ç(B Ç C)|.

По свойствам пересечения, (A Ç C)Ç(B Ç C)= A Ç B Ç C. ÿ

Задача 2. Найти число натуральных чисел, не превосходящих 1000 и не делящихся на 3, 5 и 7.

Решение. Пусть A, B и C – множества чисел, не превосходящих 1000 и кратных 3, 5 и 7 соответственно. Тогда A Ç B, A Ç C, B Ç C и A Ç B Ç C – множества чисел, не превосходящих 1000 и кратных 15, 21, 35 и 105 соответственно. Напомним обозначение: [a] – целая часть числа a. Вычислим:

| A |=[1000/3]=333, | B |=[1000/5]=200, | C |=[1000/5]=142,

| A Ç B |=[1000/15]=66, | A Ç C |=[1000/21]=47, | B Ç C |=[1000/35]=28,

| A Ç B Ç C |=[1000/105]=9.

Далее, A È B È C – множество чисел, не превосходящих 1000 и кратных хотя бы одному из чисел 3, 5 и 7. По теореме 2,

| A È B È C |=333+200+142-66-47-28+9=543.

Значит, число натуральных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 3, 5 и 7, равно 1000-543=457.

В теоремах 1 и 2 доказаны формулы включений и исключений соответственно для двух и трех множеств.

Сформулируем формулу включений и исключений для n множеств:

| A ₁È…È A_n |=| A ₁|+…+| A_n |-| A ₁Ç A ₂|-| A ₁Ç A ₃|-…-| A_{n -1}Ç A_n |+

+| A ₁Ç A ₂Ç A ₃|+| A ₁Ç A ₂Ç A ₄|+…+| A_{n -2}Ç A_{n -1}Ç A_n |+…

…+(-1) ^{n -1}| A ₁Ç A ₂Ç…Ç A_{n -1}Ç A_n |.

Как выводится формула включений и исключений? Вначале в число элементов объединения A ₁È…È A_n включаются элементы, перечисленные хотя бы один раз, затем исключаются элементы, перечисленные хотя бы два раза, далее включаются элементы, перечисленные хотя бы три раза и т. д.

Число размещений по m из n

Простейшие комбинаторные конфигурации называются также выборками. Выборка по m из n элементов – это результат выбора m элементов некоторого n- множества. При решении комбинаторных задач вначале нужно ответить на следующие вопросы:

1) «Упорядочены элементы в выборках или нет?»

2) «Повторяются элементы в выборках или нет?»

Напомним, что упорядоченные выборки называются размещениями.

Число всех размещений без повторений (с повторениями) по m из n элементов обозначается ().

Буква A от французского «arrangement» («приведение в порядок»).

Теорема 3. и .

Доказательство. Мы и используем правило произведения в комбинаторной форме. В размещении (x ₁,…, x_m) без повторений первый элемент x ₁ можно выбрать n способами, второй элемент x ₂ можно выбрать n -1 способами, …, m -й элемент x_m можно выбрать n -(m -1)= n - m +1 способами. В размещении (x ₁,…, x_m) с повторениями первый элемент x ₁ можно выбрать n способами, второй элемент x ₂ можно выбрать n способами, …, m -й элемент x_m можно выбрать n способами. ð

n - факториал – это произведение первых n положительных целых чисел: n!=1×2×3×…× n. Считается, что 0-факториал равен 1: 0!=1.

Теорема 4. .

Доказательство. Правую часть первого равенства теоремы 3 умножим и разделим на произведение (n - m)×(n - m -1)×…×2×1=(n - m)! ð

Перестановка из n элементов – это размещение без повторений из n элементов по n. Число всех перестановок из элементов обозначается P_n.

Буква P от французского «permutation» («перестановка»).

Из теоремы 3 или теоремы 4 следует, что P_n = n!

Задача 3. Сколько пятизначных чисел можно составить из всех цифр, кроме 8 и 9?

Решение. 1-й способ. Из числа всех пятибуквенных слов из 8 цифр вычтем число тех слов, которые начинаются с нуля: .

2-й способ. На первое место имеется 7 способов выбора, на последующие места по 8 способов выбора. По правилу произведения 7×8×8×8×8=28672.

Задача 4. Сколько пятизначных чисел с разными цифрами можно составить из всех цифр, кроме 8 и 9?

Решение. 1-й способ. .

2-й способ. На первое место имеется 7 способов выбора, на второе – тоже 7 способов (прибавляется 0), на третье – 6 способов, на четвертое – 5 способов, на пятое – 4 способа. По правилу произведения 7×8×8×8×8=28672.

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

Напомним, что неупорядоченные выборки называются сочетаниями.

Число всех сочетаний без повторений (с повторениями) по m из n элементов обозначается ().

Буква C от французского «combinaison» («сочетание»).

Теорема 5. Имеют место следующие 3 формулы:

(i) , (ii) , (iii) .

Доказательство. (i) Каждое размещение без повторений (x ₁,…, x_m) по m из n можно построить в 2 шага: вначале строится сочетание без повторений { x ₁,…, x_m } по m из n, а затем – перестановка (x ₁,…, x_m) из m элементов множества { x ₁,…, x_m }. По правилу произведения .

(ii) следует из (i) и теоремы 4, а (iii) – из (i) и теоремы 3.

Формула (ii) используется при доказательствах свойств , а формула (iii) – при вычислениях конкретных значений . ð

Сочетание (x ₁,…, x_m) с повторениями по m из n элементов можно представить в виде множества {(x ₁, s ₁),…,(x_n, s_n)| s ₁,…, s_n Î N ₀, s ₁+…+ s_n = m }, где N ₀ – множество всех неположительных целых чисел, s ₁,…, s_n – числа экземпляров элементов x ₁,…, x_m соответственно в сочетании (x ₁,…, x_m) с повторениями. Вместо пары (x, s) обычно пишут , если s >0, и ничего не пишут, если s =0.

Теорема 6. .

Доказательство. Каждому сочетанию по m из n элементов с повторениями взаимно однозначно соответствует последовательность , состоящая из m единиц и n -1 нулей. Рассмотрим множество A номеров элементов последовательности a: | A |= m + n -1. Множество номеров элементов a, равных единице, является m -подмножеством множества A, т.е. сочетанием без повторений по m из m + n -1 элементов множества A. Отсюда следует, что каждому сочетанию с повторениями по m из n элементов взаимно однозначно соответствует сочетание без повторений по m из m + n -1 элементов. ð

Биномиальные коэффициенты

Бином Ньютона (1+ x) ⁿ, после раскрытия скобок и приведения подобных, преобразуется в многочлен a ₀ xⁿ + a ₁ x^{n -1}+…+ a_{n -1} x ¹+ a_nx ⁰ канонического вида, где a ₀=1, a_n =1, x ⁰=1. Оказывается, что , где i =0,1,…, n. Поэтому числа сочетаний называются биномиальными коэффициентами.

Теорема 7. .

Доказательство. . Раскроем скобки и приведем подобные: в полученном многочлене коэффициент при степени xⁱ равен сумме i единиц и n -i нулей. Число всевозможных выборов i единиц из общего числа выборов n равно . ð

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

Теорема 8. ; ; .

Доказательство. . .

.

Треугольник Паскаля – это таблица биномиальных коэффициентов , расположенных по строкам n и по столбцам m.

Свойства биномиальных коэффициентов, выводимых из формулы бинома Ньютона (теорема 7), приведены в следующей теореме.

Теорема 9 (следствия теоремы 7). Имеют место следующие тождества:

1) ;

2) ;

3) ;

4) .

Доказательство. 1) В тождестве теоремы 7 подставим x =1.

2) В том же тождестве подставим x =-1.

3) Продифференцируем обе части того же тождества по x:

.

Затем подставим x =1.

4) Проинтегрируем обе части того же тождества по x от 0 до 1:

.

Получим: . ð

Разбиения множества на блоки

Говорят, что семейство множеств { M ₁,…, M_k } является разбиением множества M на k блоков M ₁,…, M_k, если M ₁,…, M_k – непустые, попарно не пересекающиеся, подмножества множества M и объединение множеств M ₁,…, M_k есть множества M. Число (или S (n, k)) всех разбиений n -множества M на k блоков называется числом Стирлинга второго рода.

Пример 7. Перечислим все разбиения множества {1,2,3,4} на 2 блока:

{{1}, {2, 3,4}},

{{2}, {1, 3,4}},

{{3}, {1, 2,4}},

{{4}, {1, 2,3}},

{{1,2}, {3,4}},

{{1,3}, {2,4}},

{{1,4}, {2,3}}

Мы видим, что .

Пусть | A |= m, | B |= n. Тогда нетрудно установить, что число элементов:

• множества всех отображений множества A в B равно числу всех размещений с повторениями по m из n, то есть | B^A |= n^m;
• множества всех инъекций множества A в B равно числу всех размещений без повторений по m из n, то есть ;
• множества всех биекций множества A на B равно числу всех размещений без повторений по m из n, то есть n!;
• множества всех сюръекций множества A на B равно произведению числа всех перестановок n -множества B на число всех разбиений n -множества B на m блоков, то есть n! .

Числа Стирлинга второго рода вычисляются по следующим формулам:

;

, где n >0;

, где n >0, 1£ k £ n.

Непосредственно число Стирлинга второго рода вычисляется по следующей формуле: .

Число всех разбиений n -множества M называется числом Белла B_n.

Ясно, что .

Перестановки с повторениями

Задача 5. Найти число разбиений n -множества M на блоки M ₁,…, M_k, такие, что | M ₁|= n ₁,…,| M_k |= n_k, 1£ n ₁,…, n_k £ n, n ₁+…+ n_k = n.

Решение. Элемент множества M ₁ можно выбрать способами, элемент множества M ₂ – способами, элемент множества M ₃ – способами и т.д. Применим правило произведения:

После сокращений получим: .

Перестановкой с повторениями называется размещение с повторениями по n из n элементов k -множества M (k £ n) со следующим дополнительным условием: различные k элементов множества M повторяются соответственно n ₁,…, n_k раз, 1£ n ₁,…, n_k £ n, n ₁+…+ n_k = n.

Теорема 10. Число перестановок с повторениями различных k элементов n ₁,…, n_k раз, 1£ n ₁,…, n_k £ n, n ₁+…+ n_k = n, равно .

Доказательство. Пусть M – множество номеров перестановки с повторениями, одной из указанных в условии теоремы, M ₁,…, M_k – множества номеров с одинаковыми элементами, повторяющимися n ₁,…, n_k раз соответственно. Тогда семейство множеств { M ₁,…, M_k } будет разбиением множества M на k блоков. Значит, каждой перестановке с повторениями соответствует вполне определенное разбиение множества M на k блоков. Ясно, что это соответствие является биекцией. Значит, искомое число перестановок с повторениями равно числу разбиений на k блоков . ð

Задача 6. Найти число всех перестановок букв слова «баобаб».

Решение. n ₁=3 (буква «б»), n ₂=2 («а»), n ₁=1 («о»), значит, .

Докажем теорему о полиномиальной формуле.

Теорема 11. .

Доказательство. После раскрытия степени, подсчитываем число одночленов вида . Их столько же, сколько будет разбиений множества множителей степени на подмножества, содержащие соответственно , число элементов которых равно соответственно . Следовательно, коэффициент при одночлене равен . ð

Задача 7. Найти коэффициент одночлена в многочлене, получаемом из степени трехчлена после раскрытия скобок и приведения подобных.

Решение. В силу теоремы 11,

.

Ответ: c =1,2.

Рекуррентные последовательности

Рекуррентным соотношением (или рекуррентным уравнением) называется соотношение вида

a_n = F (n, a_{n - k},…, a_{n -1}), (1)

где n, k Î N₀, n ³ k, F – некоторая функция от k +1 переменных. Значениями переменных a ₀, a ₁,… могут быть действительные или комплексные числа.

Последовательность a ₀, a ₁,…, a_n,… называется рекуррентной, если элементы a ₀, a ₁,…, a_{k -1} заданы по условию, а при n ³ k элемент a_n вычисляется по соотношению (1).

Пример 8. Соотношение a_n = a_{n -1}+ d определяет арифметическую прогрессию с разностью d и с начальным членом a ₀.

Пример 9. Соотношение b_n = b_{n -1} ×q определяет геометрическую прогрессию со знаменателем q ¹0 и с начальным членом b ₀.

Пример 10. Соотношение j _n =j _{n -2}+j _{n -1} определяет последовательность Фибоначчи. В своем сочинении 1202 г. Леонардо Фибоначчи рассмотрел задачу: «Предположим, что пара кроликов через месяц родит еще одну пару кроликов, и что кролики начинают рождать со второго месяца рождения. Если в начале года была 1 пара кроликов, то, сколько пар кроликов будет в конце года?» Число пар кроликов j _n равно сумме числа j _{n -2} новорожденных пар, т.е. числа пар кроликов, бывших 2 месяца назад, и числа j _{n -1} пар кроликов, бывших 1 месяца назад.

Линейным рекуррентным соотношением называется соотношение вида

a_n + p ₁ a_{n -1}+…+ p_ka_{n - k} = f (n), (2)

где f (n) – функция от числа n, p ₁,…, p_k Î C. Соотношение (2) получается из соотношения (1) при F (n, a_{n - k},…, a_{n -1})= f (n)- p ₁ a_{n -1}-…- p_ka_{n - k}

Линейным однородным (или возвратным) соотношением называется соотношение вида (2) при f (n)=0:

a_n + p ₁ a_{n -1}+…+ p_ka_{n - k} =0, (3)

Общим решением рекуррентного соотношения (1) называется множество всех последовательностей, удовлетворяющих этому соотношению.

Частным решением соотношения (1) называется одна из последовательностей, удовлетворяющих этому соотношению.

Пример 8¢. Последовательность a_n = a ₀+ nd является общим решением соотношения a_n = a_{n -1}+ d. Это – формула общего члена арифметической прогрессии с разностью d и с начальным членом прогрессии a ₀.

Пример 9¢. Последовательность b_n = b ₀× qⁿ является общим решением соотношения b_n = b_{n -1} ×q. Это – формула общего члена геометрической прогрессии со знаменателем q ¹0 и с начальным членом прогрессии b ₀.

Пример 10¢. Так называемая формула Бине j _n = является частным решением соотношения j _n =j _{n -2}+j _{n -1} при j₀=j₁=1.

Многочлен x^k + p ₁ x^{k -1}+…+ p_{k -1} x + p_k называется характеристическим для возвратной последовательности для соотношения (2).

Теорема 12. Пусть характеристический многочлен рекуррентного соотношения (3) имеет k простых корней x ₁, …, x_k. Тогда общее решение соотношения (3) имеет следующий вид:

, (4)

где c ₁,…, c_k Î C.

Доказательство. Легко проверить следующие два утверждения.

(a) Последовательность cxⁿ, где c Î C, является решением рекуррентного соотношения (3).

(b) Если последовательности a_n и b_n являются решениями соотношения (3), то последовательность a_n + b_n также является решением соотношения (3).

Из (a) и (b) следует, что любая последовательность вида (4) является решением соотношения (3).

Обратно, любое решение соотношения (3) имеет вид (4).

При n =0,1,…, k -1, из равенства (4) мы получим систему линейных уравнений относительно c ₁,…, c_k:

(5)

Определитель системы (5) есть известный в алгебре определитель Вандермонда:

.

Так как простые корни x ₁,…, x_k попарно различные, то D¹0. Значит, система (5) имеет (единственное) решение. ð

Перестановки с определенным числом циклов

Перестановка p m -множества M называется циклом, если p(x ₁)= x ₂, p(x ₂)= x ₃, …, p(x_{m -1})= x_m, p(x_m)= x ₁, где x ₁, x ₂, x ₃, …, x_{m -1}, x_m – все, различные, элементы множества M. Этот цикл обозначается через (x ₁ x ₂ x ₃… x_{m -1} x_m). Каждая перестановка состоит из конечного числа циклов, и эту перестановку можно записать в виде произведения циклов.

Пример 11. Перечислим все перестановки множества {1,2,3,4}, разбиваемые на 2 цикла:

(1)(234); (1)(243);

(2)(134); (2)(143);

(3)(124); (3)(142);

(4)(123); (4)(132);

(12)(34); (13)(24); (14)(23).

Числом Стирлинга первого рода (без знака) (или s (n, k)) называется число разбиений n -множества B на k циклов.

Числа Стирлинга первого рода вычисляются по следующим формулам:

;

, где n >0;

, где n >0, 1£ k £ n.

Ясно, что .

Производящие функции

Производящей функцией последовательности a ₀, a ₁, a ₂,…, a_k,… называется формальный ряд a ₀+ a ₁ x + a ₂ x ²+…+ a_k +….

Дата добавления: 2017-01-13; Просмотров: 179; Нарушение авторских прав?; Мы поможем в написании вашей работы!