Доказательство. "Закодируем" каждую комбинацию следующим образом

"Закодируем" каждую комбинацию следующим образом. Если комбинация включает k₁ элементов первого типа, то записываем подряд k₁ единиц, ставим нуль. После него ставим подряд k₂ единиц, если комбина­ция включает k₂ элементов другого типа и т. д. Например, если А = {a, b, c, d}, то комбинациям по два элемента с повторениями соответствуют пары {а, а}, {а b}, {а, с}, {а, d}, {b, b}, {b, с}, {c,d}, {c, c}, {c, d}, {d, d}, а их "кодами" будут соответственно

11000, 10100, 10010, 10001,..., 00011.

Нетрудно убедиться, что между "кодами" и комбинациями существует взаимно однозначное соответствие. Таким образом, каждой комбинации из n элементов по т соответствует последовательность из т единиц и n - 1 нулей (в рассмотренном примере n = 4, т = 2). Следовательно, число всех комбинаций из n элементов по т с повторениями равно числу последовательно­стей, состоящих из т единиц и n - 1 нулей, т. е. .

Теорема доказана.

Пример:

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

x₁+x₂+…+x_n=m?

Решение:

Решения данного уравнения можно интерпретировать так. Если имеем целые неотрицательные числа x₁, x₂, …,x_n, такие что x₁+x₂+…+x_n=m, то можно составить комбинацию из n элементов по m, взяв x₁ элементов первого типа, x₂ элементов второго типа,..., x_n элемен­тов n- оготипа. Наоборот, имея комбинацию из n по m элементов, получим решение урав­нения (x₁, x₂, …,x_n – число элементов первого, второго, и, соответ­ственно, n- оготипа), где все x_i неотрицательные (i = 1, 2,..., n). Таким об­разом, между множеством всех неотрицательных решений данного уравнения и множеством всех комбинаций из n элементов по m устанавлива­ется взаимно однозначное соответствие. Следовательно, число целых не­отрицательных решений уравнения равно

Например, если x₁+x₂+ x₃+x₄=10, то это уравнение имеетцелых неотрицательных решений.

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

Задача 1:

Сколькими способами на первенстве мира по футболу могут распределиться медали, если в финальной части играют 24 команды?

Решение. Золотую медаль может получить любая из 24 команд, т. е. имеем 24 возможности. Серебряную медаль может выиграть одна из 23 команд, а бронзовую - одна из 22 команд. По основному правилу комбинаторики общее число способов распределения медалей 24. 23. 22 = 12 144.

Задача 2:

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

· Цифры могут повторяться.

Решение. Первой цифрой может быть одна из цифр 1,2,3,4,5, по­скольку 0 не может быть первой цифрой, ибо в таком случае число не будет трехзначным. Если первая цифра выбрана, то вторая может быть выбрана шестью способами, как и третья цифра. Следователь­но, общее число трехзначных цифр 5*6*6 = 180.

· Ни одна из цифр не повторяется дважды.

Решение. Первой цифрой может быть одна из пяти цифр - 1,2, 3, 4, 5. Если первая цифра выбрана, то второй может быть также одна из пяти цифр (тут уже учитывается 0), а третья может быть выбрана четырьмя способами из четырех цифр, что остались. Следовательно, общее количество таких трехзначных чисел 5*5*4 = 100.

· Цифры нечетные и могут повторяться.

Решение. Первой цифрой может быть одна из трех цифр: 1, 3, 5. Второй тоже может быть одна из этих трех цифр. Аналогично и тре­тья цифра может быть выбрана тремя способами. Таким образом, общее количество таких чисел равняется 3*3*3 = 27.

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

Задача 3:

Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они «не били» друг друга?

Решение. Условие «не могли бить» означает, что на каждой го­ризонтали и вертикали может стоять лишь одна ладья. Ввиду это­го, каждому расположению ладей на доске соответствует перестановка . Верхняя строка перестановок – это номера горизонталей, нижняя - вертикалей, пересечение которых определяет положение ладей на доске. Следовательно, число рас­становок равно числу перестановок Р₈ = 8! из 8 элементов.

Число подмножеств данного множества:

Задача 4:

Сборная команда университета по волейболу насчитывает 15 человек. Сколько разных вариантов должен рассмотреть тренер перед игрой, чтобы заявить список игроков на игру?

Решение. Число игроков волейбольной команды равно шести. Значит, число всех возможных вариантов - это число различных подмножеств, состоящих из шести элементов в множестве из пятнадцати элементов. Следовательно,

.

Размещение элементов множества:

Основная формула:

Задача 5:

Студенту необходимо сдать три экзамена на протяжении семи дней. Сколькими способами это можно сделать?

Решение. Искомое число способов равно количеству трехэлемент­ных упорядоченных подмножеств множества из семи элементов, т. е. существует = 7 * 6 * 5 = 210 способов.

Если известно, что последний экзамен будет сдаваться на седьмой день, то число способов равно З * = 3 * 6 * 5 = 90.

Задача 6:

Сколькими разными способами можно разместить пять студентов в ауди­тории, которая имеет 20 мест?

Решение. Искомое число способов равно числу размещений из 20 элементов по 5 элементов, т. е. = 20 * 19 * 18 * 17 * 16 = 1 860 480.

Задача 7:

Сколько различных слов можно составить:

· В алфавите из восьми букв.

Решение. Всех таких слов будет столько, сколько существует отображений восьмиэлементного множества в множестве из двух элементов, т.е. по теореме 2⁸=256 слов.

· В алфавите из шестнадцати букв.

Решение. В этом алфавите имеем 2¹⁶=65536 слов.

Задача 8:

В хоккейном турнире участвуют 17 команд. Разыгры­ваются золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали?

Решение. 17 команд претендуют на 3 места. Тогда тройку при­зеров можно выбрать способами = 17*16*15 = 4080.