Сочетания с повторениями

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

Модельная задача 1. Сколькими способами можно разместить k одинаковых шаров по n разным ящикам?

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

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

Решение. Выложим шары в ряд. Поскольку все они одинаковые, можно считать, что сначала (например, слева) лежат шары из первого ящика, затем шары из второго ящика и так далее. Задача человека, раскладывающего шары по ящикам состоит в том, чтобы обозначить границу между шарами из первого ящика и шарами из второго, шарами из второго и шарами из третьего и так далее. То есть нам нужно расставить между шарами (n-1) перегородку (очевидно, что число перегородок на 1 меньше числа ящиков). Перегородки надо расставлять в промежутки между ящиками, причем в один промежуток можно ставить только одну перегородку (так как запрещается оставлять ящики пустыми). Таким образом, в качестве выборочного множества можно рассматривать промежутки между шарами (их k-1 штука), в качестве выборки берутся те промежутки, куда мы ставим перегородки. Выборка эта, очевидно, неупорядоченная и без повторений. То есть ответом в задаче будет число .

Решение модельной задачи 1. Эта задача легко сводится к задаче 2. Действительно, добавим к имеющимся у нас k шарам еще n шаров, которые тут же разложим по n ящикам – по одному шару в ящик. Так как это можно сделать единственным способом (шары одинаковые), то общее число интересующих нас способов при этом не изменится. То есть модельная задача 1 равносильна модельной задаче 2 с числом шаров, равным n+k. А потому ответом в задаче 1 будет число . Тем самым доказана формула:

Другое решение модельной задачи 1. Эту задачу можно решить непосредственно с помощью того же приема, который мы использовали при решении задачи 2. Выложим шары в ряд и будем расставлять между ними перегородки. Только на этот раз в один промежуток между шарами можно устанавливать несколько перегородок – две идущие подряд перегородки означают пустой ящик. Таким образом, мы должны вперемешку расположить в одну линию k шаров и n-1 перегородку, то есть k+n-1 символ. Или, другими словами, имеется k+n-1 позиция, и надо выбрать n-1 позицию, чтобы установить на эти позиции перегородки; на остальные k позиций при этом автоматически устанавливаются шары.

А сейчас мы рассмотрим еще одну задачу, родственную задачам о шарах и перегородках.

Модельная задача 3. Сколькими способами можно натуральное число n представить в виде суммы k натуральных слагаемых? При этом представления, отличающиеся порядком слагаемых, считаются различными.

Решение. Запишем n как сумму единиц: n=1+1+1+…+1. Чтобы представить n в требуемом виде, надо в этой сумме расставить соответствующим образом скобки. Или, другими словами, единицы надо разбить на группы, расставив между ними k-1 перегородку. Поскольку в каждую группу должна попасть хотя бы одна единица, то в промежуток между соседними единицами можно ставить не более одной перегородки. То есть мы должны из n-1 промежутка выбрать k-1 место для перегородок. Число способов равно .

Замечание. Можно рассуждать и проще. Задачу можно переформулировать так: сколькими способами можно n одинаковых единиц разложить по k разным ящикам-слагаемым. А это попросту модельная задача 2.

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

Задача 45. Двум мастерам приказали просверлить в рейке длиной 3 метра отверстия на равных расстояниях друг от друга и от концов рейки: одному мастеру на расстоянии 20 см, другому – 12см. Сколько всего отверстий проделано в рейке?

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

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

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

Задача 49. У Саши 8 книг по математике, а у Арины 12. Они договорились обменяться тремя книгами. Сколькими способами это можно сделать?

Задача 50. Сколькими способами можно разбить 10 человек на две баскетбольные команды по 5 человек в каждой?

Задача 51. Рота состоит из 3 офицеров, 6 сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из офицера, 2 сержантов и 20 рядовых?

Задача 52. Сколько существует 10-значных чисел, сумма цифр которых равна: а) 2, б) 3, в) 4?

Задача 53. Сколькими способами можно переставить буквы в слове "эпиграф", чтобы и гласные и согласные шли в алфавитном порядке?

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

Задача 55. На клетчатой бумаге изображен прямоугольник 12´8. Сколькими способами можно добраться из левой нижней клетки в правую верхнюю, если двигаться можно только вправо и вверх на одну клетку.

Задача 56. В условиях предыдущей задачи определить, сколькими способами можно добраться из левой нижней клетки в правую верхнюю, если запрещается проходить через клетку, находящуюся на пересечении четвертого столбца и четвертой строки данного прямоугольника. Исследовать задачу для случая, когда запрещенными являются две клетки прямоугольника.

Задача 57. В выпуклом n-угольнике проведены все диагонали. Известно, что никакие три из них не пересекаются в одной точке. Сколько всего точек пересечения имеют эти диагонали?

Задача 58. Из колоды, содержащей 52 карты, извлекли 10 карт. Во скольких случаях среди них окажется ровно один туз? Хотя бы один туз?

Задача 59. Сколько различных четырехзначных чисел, делящихся на 4, можно составить из цифр 1, 2, 3, 4, 5, если каждая цифра может встречаться в записи числа несколько раз?

Задача 60. Сколько ожерелий можно составить из семи бусинок разного цвета?

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

Задача 62. Сколькими способами можно расставить 20 книг в книжном шкафу с 5 полками, если каждая полка может вместить все двадцать книг?

Задача 63. Найти сумму четырехзначных чисел, полученных при всевозможных перестановках цифр 1, 2, 3, 4.

Задача 64. Тот же вопрос для цифр 1,2, 2, 5.

Задача 65. Сколькими способами можно выбрать из натуральных чисел от 1 до 20 два числа так, чтобы их сумма была нечетной?

Задача 66. Сколькими способами можно выбрать из натуральных чисел от 1 до 30 три числа так, чтобы их сумма была четной?

Задача 67. Сколькими способами можно выбрать из чисел от 1 до 100 три числа так, чтобы их сумма делилась на 3?

Задача 68. Доказать, что нечетное число предметов можно выбрать из данных n предметов 2^n-1 способами.

Задача 69. Сколькими способами можно построить в ряд 6 учеников, если: а) Петя хочет стоять рядом с Вовой; б) Петя не хочет стоять рядом с Вовой; в) Петю нельзя ставить первым, а Вову последним.

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

Задача 70. Сколько различных анаграмм можно составить из букв слова «МАТЕМАТИКА»?

Решение. Первый способ. Если бы все буквы этого слова были различными, то мы имели бы 10! анаграмм. Однако, меняя между собой местами различные экземпляры буквы «а», мы будем получать одинаковые анаграммы. Три экземпляра буквы «а» можно переставить 3! способами, то есть 10! анаграмм распадутся на группы, каждая из которых состоит из 6 одинаковых анаграмм. Кроме того, одинаковые анаграммы получаются при перестановке двух букв «м» и двух букв «т». Таким образом, различных анаграмм будет =151200.

Второй способ. Букву Е можно поставить на одно из 10 мест, букву И – на одно из 9 мест, букву К – на одно из восьми, два места для букв М можно выбрать способом, два места для букв Т можно выбрать способами, а на оставшиеся три места поставим буквы А. Всего получается 10×9×8×21×10 анаграмм.

Сформулируем задачу в общем виде. Пусть имеется выборочное множество . Перестановкой с повторениями состава (k₁, k₂,…,k_n) называется упорядоченная выборка, в которой k₁ раз встречается элемент х₁, k₂ раз встречается элемент х₂ и т.д. Общее число таких перестановок обозначается P(k₁, k₂,…,k_n). Справедлива формула

Задача 71. Докажите приведенную выше формулу.

Поговорим теперь немного о биномиальных коэффициентах.

Задача 72. Докажите, что коэффициент перед x^k в многочлене (1+ x)ⁿ равен , иными словами .

Решение. Раскроем скобки в выражении (1+ x)ⁿ=(1+х)×(1+х)×…×(1+х), не приводя подобные члены. У нас получится сумма 2ⁿ слагаемых, каждое из которых равно произведению n множителей; некоторые из этих множителей – единицы, остальные равны х. При этом первый множитель выбирается из первой скобки, второй множитель – из второй скобки и т.д. Чтобы получить слагаемое, в котором k множителей равны х, нужно из k скобок выбрать в качестве множителя х, из остальных n–k – единицу. Так как k скобок из n имеющихся можно взять способами, то всего будет слагаемых вида x^k. После приведения подобных членов получим .

Задача 73. Докажите, что . (эта формула известна как бином Ньютона).

Задача 74. Докажите, что .

Решение. В формуле бинома Ньютона положим a=b=1.

Задача 75. Докажите, что .

Задача 76. Докажите, что .

Задача 77. Найти член разложения (1+х)¹² с наибольшим коэффициентом.

Указание. Рассмотрите отношение .

Задача 78. Найти член разложения (1+2х)¹⁰ с наибольшим коэффициентом.

Задача 79. Докажите, что после раскрытия скобок и приведения подобных членов коэффициент перед x^k в выражении будет равен .

Задача 80. Найдите коэффициент перед x⁵ в многочлене (1–2 x+x²)⁶.

Решение. После раскрытия скобок слагаемое с переменной х в пятой степени может появиться двумя способами. Во-первых, из одной скобки будет выбран множитель 1, а из пяти скобок – множитель –2 х. Таких слагаемых всего будет 6, а их сумма будет равна 6×(–2 х)⁵=–192 х ⁵. Во-вторых, из двух скобок возьмем множитель х ², из одной скобки – множитель –2 х, из оставшихся скобок – единицу. Таких слагаемых будет Р(1,2,3)=60, их сумма равна –120 х ⁵. Таким образом, после приведения подобных членов коэффициент перед x⁵ будет равен –312.

Задача 81. Найдите коэффициент перед x⁷ в многочлене (1+2 x–x²)¹⁰.

Задача 82. Найдите коэффициент перед x^k в многочлене (1+ x+x²+…+xⁿ)².

Задача 83. Найдите коэффициент перед a³b³ в многочлене (1+ a–ab+b²)¹⁰.

Приложение.

Контрольная работа по комбинаторике (проводилась в 2001 году в 11б классе сш №17 г. Твери).

Вариант 1

1. Сколькими способами можно построить в ряд 5 мальчиков и 5 девочек

а) так, чтобы они чередовались;

б) так, чтобы девочки не стояли рядом.

2. Сколькими способами можно распределить между 5 сладкоежками 10 шоколадок и 20 конфет.

3. Сколько существует трехзначных чисел, у которых

а) цифры расположены в порядке возрастания;

б) все цифры разные, причем первая цифра самая большая.

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

5. Найти коэффициент перед x⁶ в многочлене (1+2x–x²)¹².

6. Сколько анаграмм можно составить из слова АБСЦИССА? А сколько можно составить анаграмм, начинающихся на гласную букву?

Вариант 2

1. Сколькими способами можно построить в ряд 5 мальчиков и 6 девочек

а) так, чтобы они чередовались;

б) так, чтобы все девочки стояли рядом.

2. Сколькими способами могут распределиться между 5 спортсменами комплекты наград в забегах на 3 различные дистанции.

3. Сколько существует трехзначных чисел, у которых

а) цифры расположены в порядке убывания;

б) есть повторяющиеся цифры.

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

5. Найти коэффициент перед x⁷ в многочлене (1+2x–3x²)¹⁰.

6. Сколько анаграмм можно составить из слова ПЕРИМЕТР? А сколько можно составить анаграмм, начинающихся на согласную букву?

Дата добавления: 2014-12-29