Комбинаторика. Перестановки, сочетания, размещения без повторений. Основные правила комбинаторики

Комбинаторика. Перестановки, сочетания, размещения без повторений.  Основные правила  комбинаторики Реферат

Бином ньютона и его обобщения

В главе I (§ 1, п. 8) была выведена формула бинома Ньютона:

Через комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторика

— и раскроем скобки в этом произведении, причем будем записывать все множители в том порядке, в котором они нам встретятся. Например, запишем

или

Видно, что в формулу (3) входят все размещения с повторения­ми из букв х и а, по две буквы в каждом размещении , а в формулу (4) — размещения с повторениями из тех же букв, содержащие по три буквы. То же самое будет в общем случае — после раскрытия скобок в формуле (2) получаются все размещения с повторениями из букв х и а, по n букв в каждом размещении.

Приведем подобные члены. Подобными будут члены, содержа­щие одинаковое количество букв а (тогда и букв х в них будет поровну). Найдем число членов, содержащих k букв а (и, следователь­но, n — k букв х). Эти члены являются всевозможными перестановками с повторениями, составленными из k букв а и n — k букв Их число равно

Отсюда вытекает, что после приведения подобных членов коэффициент при комбинаторикакомбинаторикакомбинаторика

Рассмотрим несколько задач, связанных с формулой бинома Ньютона.

Пример:

Определить коэффициент при комбинаторикакомбинаторика

Решение:

Запишем данное нам выражение в виде:

где комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторика

Пример:

С каким коэффициентом входит комбинаторикакомбинаторика

Решение:

Выясним сначала, каким числом способов можно представить комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторика

Подставляя в (1) х=1, получим другой вывод формулы (1) из § 5. Аналогично, приняв в (1) х = — 1, получим еще одну любопытную формулу:

или, иначе,

то есть для любого n сумма сочетаний из n элементов по четному числу элементов равна сумме сочетаний из п элементов по нечетному числу элементов.

Формулу, аналогичную формуле бинома Ньютона, можно полу­чить и для возведения в степень суммы нескольких слагаемых. Если число слагаемых невелико, то ее легко получить, приме­няя несколько раз формулу бинома Ньютона. Например, для трех слагаемых можно написать:

раскрывая, в свою очередь, каждое слагаемое справа по формуле (2). При небольших n это нетрудно сделать.

Пусть, например, n = 2. Тогда получаем:

При n = 3 находим:

Таким образом, мы получили формулы для квадрата и куба суммы трех слагаемых, которые имеют вид:

Однако для больших n, не говоря уже о большом числе слагаемых , такой способ вывода формулы потребует уже чересчур сложных и громоздких вычислений.

Формулу для возведения в степень суммы нескольких слагаемых можно получить и непосредственно, подобно тому как мы это делали для формулы бинома Ньютона.

Действительно, n-я степень суммы комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторика

то есть все они суть целые неотрицательные числа и их сумма равна n.

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

Полученное можно выразить в виде следующей теоремы.

Теорема:

Результат возведения суммы m слагаемых в n-ю сте­пень имеет вид:

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

Эту теорему называют полиномиальной, а коэффициенты (5) — полиномиальными коэффициентами.

Легко убедиться в том, что формула бинома Ньютона является частным случаем полиномиальной формулы (6).

Решение заданий и задач по предметам:

Дополнительные лекции по высшей математике:

  1. Тождественные преобразования алгебраических выражений
  2. Функции и графики
  3. Преобразования графиков функций
  4. Квадратная функция и её графики
  5. Алгебраические неравенства
  6. Неравенства
  7. Неравенства с переменными
  8. Прогрессии в математике
  9. Арифметическая прогрессия
  10. Геометрическая прогрессия
  11. Показатели в математике
  12. Логарифмы в математике
  13. Исследование уравнений
  14. Уравнения высших степеней
  15. Уравнения высших степеней с одним неизвестным
  16. Комплексные числа
  17. Непрерывная дробь (цепная дробь)
  18. Алгебраические уравнения
  19. Неопределенные уравнения
  20. Соединения
  21. Бином Ньютона
  22. Число е
  23. Непрерывные дроби
  24. Функция
  25. Исследование функций
  26. Предел
  27. Интеграл
  28. Двойной интеграл
  29. Тройной интеграл
  30. Интегрирование
  31. Неопределённый интеграл
  32. Определенный интеграл
  33. Криволинейные интегралы
  34. Поверхностные интегралы
  35. Несобственные интегралы
  36. Кратные интегралы
  37. Интегралы, зависящие от параметра
  38. Квадратный трехчлен
  39. Производная
  40. Применение производной к исследованию функций
  41. Приложения производной
  42. Дифференциал функции
  43. Дифференцирование в математике
  44. Формулы и правила дифференцирования
  45. Дифференциальное исчисление
  46. Дифференциальные уравнения
  47. Дифференциальные уравнения первого порядка
  48. Дифференциальные уравнения высших порядков
  49. Дифференциальные уравнения в частных производных
  50. Тригонометрические функции
  51. Тригонометрические уравнения и неравенства
  52. Показательная функция
  53. Показательные уравнения
  54. Обобщенная степень
  55. Взаимно обратные функции
  56. Логарифмическая функция
  57. Уравнения и неравенства
  58. Положительные и отрицательные числа
  59. Алгебраические выражения
  60. Иррациональные алгебраические выражения
  61. Преобразование алгебраических выражений
  62. Преобразование дробных алгебраических выражений
  63. Разложение многочленов на множители
  64. Многочлены от одного переменного
  65. Алгебраические дроби
  66. Пропорции
  67. Уравнения
  68. Системы уравнений
  69. Системы уравнений высших степеней
  70. Системы алгебраических уравнений
  71. Системы линейных уравнений
  72. Системы дифференциальных уравнений
  73. Арифметический квадратный корень
  74. Квадратные и кубические корни
  75. Извлечение квадратного корня
  76. Рациональные числа
  77. Иррациональные числа
  78. Арифметический корень
  79. Квадратные уравнения
  80. Иррациональные уравнения
  81. Последовательность
  82. Ряды сходящиеся и расходящиеся
  83. Тригонометрические функции произвольного угла
  84. Тригонометрические формулы
  85. Обратные тригонометрические функции
  86. Теорема Безу
  87. Математическая индукция
  88. Показатель степени
  89. Показательные функции и логарифмы
  90. Множество
  91. Множество действительных чисел
  92. Числовые множества
  93. Преобразование рациональных выражений
  94. Преобразование иррациональных выражений
  95. Геометрия
  96. Действительные числа
  97. Степени и корни
  98. Степень с рациональным показателем
  99. Тригонометрические функции угла
  100. Тригонометрические функции числового аргумента
  101. Тригонометрические выражения и их преобразования
  102. Преобразование тригонометрических выражений
  103. Вычислительная математика
  104. Прямая линия на плоскости и ее уравнения
  105. Прямая и плоскость
  106. Линии и уравнения
  107. Прямая линия
  108. Уравнения прямой и плоскости в пространстве
  109. Кривые второго порядка
  110. Кривые и поверхности второго порядка
  111. Числовые ряды
  112. Степенные ряды
  113. Ряды Фурье
  114. Преобразование Фурье
  115. Функциональные ряды
  116. Функции многих переменных
  117. Метод координат
  118. Гармонический анализ
  119. Вещественные числа
  120. Предел последовательности
  121. Аналитическая геометрия
  122. Аналитическая геометрия на плоскости
  123. Аналитическая геометрия в пространстве
  124. Функции одной переменной
  125. Высшая алгебра
  126. Векторная алгебра
  127. Векторный анализ
  128. Векторы
  129. Скалярное произведение векторов
  130. Векторное произведение векторов
  131. Смешанное произведение векторов
  132. Операции над векторами
  133. Непрерывность функций
  134. Предел и непрерывность функций нескольких переменных
  135. Предел и непрерывность функции одной переменной
  136. Производные и дифференциалы функции одной переменной
  137. Частные производные и дифференцируемость функций нескольких переменных
  138. Дифференциальное исчисление функции одной переменной
  139. Матрицы
  140. Линейные и евклидовы пространства
  141. Линейные отображения
  142. Дифференциальные теоремы о среднем
  143. Теория устойчивости дифференциальных уравнений
  144. Функции комплексного переменного
  145. Преобразование Лапласа
  146. Теории поля
  147. Операционное исчисление
  148. Системы координат
  149. Рациональная функция
  150. Интегральное исчисление
  151. Интегральное исчисление функций одной переменной
  152. Дифференциальное исчисление функций нескольких переменных
  153. Отношение в математике
  154. Математическая логика
  155. Графы в математике
  156. Линейные пространства
  157. Первообразная и неопределенный интеграл
  158. Линейная функция
  159. Выпуклые множества точек
  160. Система координат

Комбинаторные задачи

Среди различных задач, которые приходится решать математикам, встречаются такие, где нужно ответить на вопрос: каким числом различных способов можно осуществить требуемое? Такие задачи принято называть комбинаторными задачами. Для реше­ния таких задач созданы общие методы и выведены готовые форму­лы.

Пример:

Каким числом способов можно обить 12 раз­ личных стульев, если есть 12 образцов обивочного материала, при­чем каждый материал имеется в любом количестве?

Решение:

Поскольку имеется 12 различных образцов обивочного материала, то один стул можно обить двенадцатью различ­ными способами. То же самое справедливо и для второго стула, так как каждый обивочный материал имеется в любом количестве. Но каждый способ обивки первого стула можно соединить с любым способом обивки второго, так что число различных способов обивки двух стульев равно комбинаторика

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

Итак, для двух различных стульев мы получили комбинаторикакомбинаторикакомбинаторикакомбинаторика

Пример:

Каким числом способов можно рассадить 12 гостей на имеющихся 12 различных стульях?

Решение:

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

Дальнейший ход решения теперь уже ясен. Для гостя, входя­щего третьим, останется только 10 различных возможностей, так как из 12 мест два места окажутся уже занятыми. Поэтому для трех гостей число различных способов рассадить их составляет 12 • 11 • 10 = 1320.

Пример:

В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них должен быть назначен старшим?

Решение этой задачи очень похоже на решение предыду­щей. Действительно, если назначить сначала старшего по наряду, то для его выбора у нас имеется 12 различных возможностей: каж­дый солдат отделения может быть назначен старшим наряда. Пос­ле того как старший наряда назначен, вторым в наряд может быть назначен любой из оставшихся одиннадцати. Как и во всех предыдущих случаях, общее число различных нарядов составляет 12- И = 132.

Пример:

Какое число различных парных нарядов можно назначить из 12 солдат отделения, если не требуется назначать старшего по наряду?

Решение:

Легко понять, что число таких нарядов должно быть меньше, чем в предыдущем примере. Действительно, наряды —Иванов (старший) и Петров или Петров (старший) и Иванов — различны, тогда как, если не требуется назначать старшего, эти два солдата в обоих случаях составляют один и тот же наряд. Каждый парный наряд без старшего можно превратить в два различных на­ряда со старшим. Поэтому число различных парных нарядов со старшим в два раза больше, чем нарядов без старших. Отсюда сле­дует, что интересующее нас в данном примере число различных пар­ных нарядов из 12 солдат отделения в два раза меньше, чем получено в предыдущем примере, т. е. равно комбинаторика

Рефераты:  Биологическая очистка сточных вод — Рефераты бесплатно

Пример:

Клавиатура пианино состоит из 88 клавиш. Сколько различных музыкальных фраз можно составить из 6 нот, допуская повторения одних и тех же нот в одной фразе?

Решение:

Как и в примере 1, в качестве первой ноты для музыкальной фразы можно взять любую из 88 нот, т. е. для первой ноты мы имеем 88 возможностей. Так как повторения допускаются, то для второй ноты мы снова имеем те же 88 возможностей, и по­этому музыкальных фраз из двух нот существует комбинаторикакомбинаторика

Пример:

Сколько различных музыкальных фраз можно составить из 6 нот, если не допускать в одной фразе повторений уже встречавшихся звуков?

Решение этой задачи так же отличается от решения предыдущей, как решение задачи примера 2 от примера 1. Действи­тельно, при составлении произвольной музыкальной фразы для первой ноты мы имеем по-прежнему 88 возможностей. Для второй ноты число возможностей уменьшится уже до 87, так как нота, использованная первой, не должна больше употребляться.

Пример:

Сколько существует различных аккордов из шести нот?

Решение:

Аккорд отличается от музыкальной фразы тем, что все ноты, в него входящие, звучат одновременно. Отсюда сле­дует, что все ноты аккорда должны быть различными. Кроме то­го, различные музыкальные фразы могут приводить к одному и тому же аккорду, если они состоят из одних и тех же нот, но рас­положенных в фразе в различном порядке.

Поэтому, подобно при­меру 4, так как число различных музыкальных фраз уже известно, нам остается определить, сколько различных музыкальных фраз могут «склеиваться» в один и тот же аккорд, или, наоборот, сколь­ко различных фраз получается из одного и того же аккорда.

Мы приходим, таким образом, к задаче, аналогичной рассмотренной в примере 6: имеется аккорд из шести различных нот, сколько различных музыкальных фраз можно из него составить? В качестве первой ноты для составляемой музыкальной фразы мож­но взять любую из входящих в аккорд нот, то есть мы имеем для нее шесть различных возможностей. Для второй ноты остается уже только пять возможностей, для третьей — четыре и т. д.

Теперь уже ясно, что число различных музыкальных фраз, которые можно получить из одного аккорда из шести нот, равно 6 • 5 • 4 • 3 • 2 • 1 =6!= 720. Это означает, что 6! различных музыкальных фраз склеиваются в один и тот же аккорд, так что число возможных аккордов будет в 61 раз меньше, чем число раз­личных музыкальных фраз. Итак, мы получаем, что число различ­ных возможных аккордов из 6 нот равно:

Пример:

Из города А в город В ведет k дорог, а в город С — l дорог. В город D из города В ведет m дорог, а из города С — n дорог. Города В и С дорогами не соединяются. Сколько различных автобусных маршрутов можно провести между городами А и D?

Решение:

Число автобусных маршрутов определяется чис­лом различных дорог между городами. Всего из города А выхо­дит k l дорог, а в город D входит m n дорог. Мы не можем, однако, сказать, что общее число дорог равно произведению этих чисел, так как здесь невозможно комбинировать любую дорогу, выходящую из A, с любой дорогой, входящей в D . Если же рассматривать отдельно дороги, проходящие через В или через С, то такая комбинация возможна.

Рассмотрим всевозможные маршруты, идущие из A в D через В. Из A в В ведет k дорог, а из В в D —m дорог. Каждую из таких дорог, выходящих из A, можно комбинировать с любой дорогой,, входящей в D поэтому общее число различных маршрутов, как и во всех предыдущих задачах, получается перемножением числа возможностей и равно km, Следовательно, число различных маршрутов, идущих из A в D через В, равно km.

Аналогично подсчитывается число различных маршрутов, иду­щих из A в D через С; оно равно ln. Далее, мы замечаем, что всякий автобусный маршрут, соединяющий города A и D, должен проходить или через В, или через С, и, значит, он должен входить либо в число km маршрутов, идущих через В, либо в число ln мар­шрутов, идущих через С. Общее число различных маршрутов равнo тогда сумме km ln.

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

Фактически при решении всех задач мы пользовались этим общим правилом, и нужно было только определить число различных возможностей в том или ином случае. Это число менялось в зави­симости от условий задачи.

Другое общее правило имеет следующий вид: если некоторый выбор может быть сделан т различными способами, а другой выбор—n различными способами {отличными от предыдущих), то общее число способов, которыми можно осущест­вить какой-нибудь один из этих выборов, равен сумме m n.

Это правило также применялось нами в предыдущем параграфе (см. пример 8).

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

Пример:

Во взводе 5 сержантов и 50 солдат. Сколькими способами можно составить наряд из одного сержанта и трех солдат?

Решение:

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

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

Представим себе сначала, что назначаемых в наряд солдат мы вызываем по одному и строим в шеренгу. Тогда легко подсчитать, что при вызове первого солдата у нас есть 50 различных возможностей; после того как один солдат уже вызван, для выбора второго остается 49 возможностей, а для выбора третьего — лишь 48.

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

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

Но это число легко под считать, пользуясь обычным приемом: чтобы поставить какого-либо солдата на первое место, есть три различные возможности, на второе место остается два солдата и на третье — только один Поэтому общее число возможных перестановок трех солдат в ше­ренге равно 3 • 2 • 1 = 3! = 6.

Итак, каждый наряд из трех солдат можно расставить в шерен­гу 3! различными способами, а, значит, в произведении 50 • 49 • 48, показывающем число возможностей при выборе трех человек в определенном порядке, каждый наряд считается ровно 3! раз. Поэтому общее число различных способов, которыми можно назначить в наряд трех солдат из пятидесяти, равно

Число различных нарядов из одного сержанта и трех солдат
равно теперь

Пример:

Сколько членов, содержащих две буквы, полу­чится после раскрытия скобок в выражении

Решение:

После раскрытия всех скобок мы получим сум­му некоторого числа слагаемых (нетрудно подсчитать, что общее число слагаемых равно комбинаторика

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

Действительно, для выбора первой буквы у нас есть шесть возможностей, а для выбора второй — пять. Кроме того, каждую пару букв мы считаем дважды, один раз полагая первой одну из них, а другой раз — вторую.

Рефераты:  Образовательный портал . Всё для учебы, работы и отдыха. Шпаргалки, рефераты, курсовые. Сочинения и изложения. Конспекты и лекции. Энциклопедии. Учебники.

Пример:

Подсчитаем, сколько в рассмотренном в преды­дущем примере произведении слагаемых, содержащих четыре буквы.

Решение этой задачи аналогично решению предыдущей. Тем же методом можно подсчитать, что выбор четырех букв в определенном порядке может быть сделан 6 • 5 • 4 • 3 = 360 различными способами. С другой стороны, каждая четверка счи­тается здесь несколько раз, именно столько, каким числом спосо­бов можно ее упорядочить.

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

Пример:

В классе m мест. Каким числом способов можно рассадить в нем n учеников (n < m)?

Решение:

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

Представим себе, что ученики входят в класс по одному. Тогда для первого из них имеется m возможностей выбрать место. После того как первый выбрал какое-то место, для второго остается m — 1 возможностей. Далее, для третьего будет m — 2 различных возможностей и т. д. Искомое число способов рассадить всех учеников выразится произведением

Найдем последний сомножитель этого произведения. Его мож­но определить по-разному, например так: каждый сомножитель на единицу меньше предыдущего и получается вычитанием из m числа, на единицу меньшего, чем номер сомножителя. Поэтому сом­ножитель с номером п получается вычитанием из т числа n — 1, то есть равен m — (n — 1) = m — n 1.

Можно рассуждать и иначе: после того как все ученики рассядутся, в классе должно остаться m — n свободных мест. Перед входом последнего ученика свободных мест было на 1 больше, то есть m — n 1. Таково же число возможностей для выбора мест последним учеником, то есть последний сомножитель в про­изведении.

Итак, искомое число различных способов рассадить n учеников на m местах равно произведению п последовательных целых чисел от m до m — n 1 включительно:

Пример:

В комнате имеется пять лампочек. Сколько су­ществует различных способов освещения?

Решение:

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

Между тем задача допускает простое и короткое решение, если проводить рассуждение в другом порядке. Рассмотрим сначала случай, когда в комнате имеется всего лишь одна лампочка. Тогда, очевидно, возможны ровно два различных способа освещения: лампочка либо горит, либо не горит.

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

Пример:

Чему равен коэффициент при комбинаторикакомбинаторикакомбинаторика

Решение:

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

Выражение комбинаторикакомбинаторика

Благодаря замеченной общности задач мы могли бы воспользоваться уже готовым результатом; но мы повторим совсем корот­ко приведенные там рассуждения в новых терминах, относящихся уже к данной задаче.

Шесть букв а можно разместить на 88 возможных местах числом способов, равным произведению

если выбрать эти буквы в определенном порядке. Поскольку порядок выбора букв нам безразличен, то каждая комбинация счи­тается в этом произведении несколько раз: столько же, каким число способов можно переставлять между собой уже выбранные буквы на определенных шести местах.

Число возможных способов переставлять между собой шесть букв на шести местах, как мы уже видели, равно 6! Поэтому число различных способов выбрать шесть букв а из 88, а значит, и коэф­фициент при члене комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторика

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

Если рассмотреть теперь снова задачи, разобранные в §§ 1 и 2, то мы увидим, что решение почти всех из них не требует уже ни­каких рассуждений, а получается непосредственным применением нужной формулы из выведенных в предыдущем параграфе. Соб­ственно говоря, все рассуждения, которые приводились при реше­нии задач, были не чем иным, как именно выводом соответствующей формулы, но только для данного конкретного случая.

Однако в числе приведенных там примеров есть и такие, которые не укладываются в уже рассмотренные схемы. К ним отно­сятся, скажем, примеры 1 и 5 из § 1. Дело в том, что при определе­нии различных видов соединений в предыдущем параграфе мы брали некоторое определенное множество, элементы которого существо­ вали «в единственном экземпляре» и в каждое данное соединение могли входить только один раз.

Между тем в некоторых случаях элементы в соединении могут повторяться, как например ноты в музыкальной фразе в примере 5 из § 1. Для того чтобы охватить общей теорией и такие задачи, необходимо рассмотреть соедине­ния с повторениями, которым и посвящен настоящий параграф.

Пусть имеется m непересекающихся множеств комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикасовпадающими между собой.

Слова «одинаковые» или «совпадающие» употребляются здесь в том смыс­ле, в каком одинаковыми являются, например, 12 белых или 12 черных ша­шек. Именно в таком смысле понимается распространенное выражение «мно­жество с повторяющимися элементами», хотя оно и не согласуется с описан­ным во Введении пониманием терминов «множество» и «элемент» (согласно которому множества, содержащие одни и те же элементы, считаются совпа­дающими).

Вообще, в таких случаях правильнее говорить о множестве различ­ных вхождений «одинаковых» (точнее — одноименных) эле­ ментов. Так, слово «алгебра» состоит из ш е с т и букв, но содержит семь вхождений букв (буква «а» входит дважды, остальные — по одному разу). С совершенно аналогичной по существу ситуацией мы уже имели дело о гл. I, говоря о «кратных» корнях многочленов.

Из элементов множества A, то есть элементов, входящих в различные его подмножества комбинаторикаразмещениями с повторениями из элементов m сортов по n элементов, или, более коротко, просто размещениями с повторениями из m элементов по n.

В первом из этих терминов (более точном, но менее употребительном из-за своей громоздкости) явным образом указывается, что име­ется не т различных элементов, а m различных сортов элементов; число же элементов любого сорта в размещении может быть каким угодно.

Для наглядности будем представлять себе, что элементами рассматриваемых множеств являются буквы. Если, например, m=3, то это могут быть буквы а, b, с. Тогда возможны следующие размещения с повторениями этих трех элементов по n = 2:

Размещения с повторениями можно рассматривать и в случае n > m, то есть неравенство комбинаторикакомбинаторика

Теорема:

Число различных размещений с повторениями из m элементов по n элементов определяется по формуле:

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

Прежде всего заметим, что разме­щения с повторениями по n элементов могут быть получены из раз­мещений по (n — 1) элементу присоединением еще одного элемента. Так как к каждому размещению по (n — 1) элементу можно при­соединить любой из имеющихся m элементов, то каждое размещение по (n — 1) элементу порождает т различных размещений по n элементов, то есть

Проведем теперь доказательство формулы (1) по индукции. Ясно, что при n = 1 число размещений равно m:

Допустим, что для некоторого числа n справедливо равенство

и найдем число размещений с повторениями из m элементов по n. Пользуясь формулой (2), получаем:

Таким образом, формула (1) справедлива для n — 1 и из ее справедливости для некоторого п следует и справедливость для n 1. Теорема доказана.

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

Определение:

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

Пусть рассматриваемое множество состоит из комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторика

n различных элементов, и число перестановок этого множества, в силу теоремы 2 предыдущего параграфа, равно n!, причем

Теперь мы заметим, что элементы комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторика

Теорема:

Число различных перестановок из п элементов, в ко­ торых элементы а, b, с, …, l повторяются соответственно комбинаторикакомбинаторика раз, выражается формулой

Определение:

Сочетанием с повторениями из m элементов по n элементов называется всякое множество, содержащее n элементов, каждый из которых является элементом одного из данных m сортов.

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

Например, из трех элементов а, b, с можно образовать такие сочетания с повторениями по два элемента:

Рефераты:  Реферат: «система оценивания и сравнительный анализ результатов обучения» -

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

Ясно, что из элементов а, b, с можно составлять сочетания с повторениями и по четыре элемента и вообще по любому чис­лу n элементов, так что для сочетаний с повторениями неравенство комбинаторикакомбинаторика

Теорема:

Число различных возможных сочетаний с повторения­ ми из т элементов по п элементов может быть найдено по формуле

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

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

Например, если имеются элементы четырех сортов, то сочета­ние вполне определится, если сказать, что оно содержит два эле­ мента первого сорта, четыре элемента второго, ни одного элемента третьего и один элемент четвертого сорта. Это есть одно из возможных сочетаний с повторениями из четырех элементов по семи.

Другие сочетания определятся, например, комбинациями (3, 0, 0, 4) или (1, 1,2, 3). Первая из них определяет сочетание, состоящее из трех элементов первого сорта и четырех элементов чет­вертого. Элементы второго и третьего сорта в это сочетание не входят.

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

В общем случае, если мы захотим условной комбинацией чисел изобразить некоторое сочетание с повторением из m элементов по n элементов, то придется написать уже m целых неотрицательных чисел, снова по одному числу на каждый имеющийся сорт элемен­тов, обозначив их, скажем, комбинаторикакомбинаторикакомбинаторикакомбинаторика

Запись из нулей и единиц, соответствующая сочетанию из m элементов по n элементов, будет содержать ровно n единиц и m — 1 нулей. Действительно, количество единиц равно числу элементов в сочетании, а количество нулей на единицу меньше числа сортов элементов, поскольку нуль употребляется лишь для их разделения.

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

Если сравнить полученное выражение с формулой (7) для чис­ла сочетаний без повторений, выведенной в предыдущем параграфе, то мы заметим, что

Таким образом, число сочетаний с повторениями из m элементов по n элементов равно числу сочетаний без повторений из n m — 1 элементов по m — 1 элементов.

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

Пример:

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

Решение:

Эту задачу можно решить двумя способами. Пер­вый способ заключается в том, что мы сначала ищем, сколько людей может иметь k зубов, а потом просуммируем полученные результа­ты от k= 0 до k=32. Ясно, что k мест из 32 можно выбрать комбинаторикакомбинаторика

Полученный этим способом ответ оказался очень громоздким. Выгоднее избрать другой путь, которым мы уже пользовались при решении примера 5 в § 2, — применить метод индукции.

Если речь идет об одном зубе, то возможны только два челове­ка—один с зубом и второй без него. При двух зубах число возможных наборов зубов становится равным четырем: нет ни одного зуба, есть первый, есть второй и есть оба.

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

Обозначим число возможных наборов k зубов через комбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторикакомбинаторика

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

Более того, из приведенного выше доказательства по индукции вытекает, что аналогичное равенство справедливо при любом n, то есть что имеет место формула

Пример:

Дана прямоугольная сетка квадратов размером m х n. Каково число различных дорог на этой сетке, ведущих из левого верхнего угла в правый нижний (рис. 46)? (Все звенья дороги предполагаются идущими или вправо, или вниз — без возвращений; сходная ситуация возникает, скажем, при выборе одного из кратчайших маршрутов между двумя городскими перекрестками.)

Решение:

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

Сравнивая полученную сумму с найденным выше выражением для числа дорог, мы придем к формуле:

Пример:

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

Решение:

Прежде всего необходимо указать, что задача сформулирована недостаточно точно и допускает два различных толкования. Нас может интересовать или только число пассажиров в каждом вагоне или же кто именно в каком ва­гоне находится. Рассмотрим обе возможные формулировки.

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

Здесь мы имеем размещения с повторениями из трех элементов по шесть элементов: для каждого из шести пасса­жиров имеются три возможности. Пользуясь формулой (1) из § 4, получаем, что число различных способов, которыми шесть пассажиров могут распределиться в трех вагонах, равно:

Иной результат получится в том случае, если нас интересует лишь число пассажиров в каждом вагоне, так что случай «один пас­сажир в первом вагоне и один во втором» является единственным, независимо от того, кто из пассажиров где находится. Здесь нужно подсчитывать уже не размещения, а Сочетания с повто­рениями. По формуле (4) из §4 находим, что число различных способов распределения пассажиров в этом случае равно

Пример:

Сколькими способами можно распределить 28 костей домино между 4 игроками так, чтобы каждый получил 7 костей?

Решение:

Первый игрок может выбрать 7 костей комбинаторикакомбинаторикакомбинаторикакомбинаторика

способов раздела костей.

Эту задачу можно решить иначе. Упорядочим все кости и отдадим первые 7 костей первому игроку, вторые 7 костей — второму игроку и т. д. Так как 28 костей можно упорядочить 28! способа­ми, то получаем 28! способов раздела. Но некоторые из этих спо­собов приводят к одинаковым результатам — игрокам неважно, в каком порядке приходят к ним кости, а важно лишь, какие имен­но кости они получат. Поэтому результат не изменится, если мы как угодно переставим друг с другом первые 7 костей, потом вторые 7 костей и т. д. Первые 7 костей можно переставить 7! способами, вторые 7 костей — тоже 7! способами и т. д. Всего получим комбинаторика

Пример:

Сколькими способами можно разделить 40 яблок между 4 мальчиками (все яблоки считаются одинаковыми)?

Решение:

Возьмем три одинаковые перегородки и рассмо­трим всевозможные перестановки 43 предметов: 40 яблок и 3 пере­ городок. Каждой такой перестановке соответствует свой способ раздела: первый мальчик получает все яблоки от начала до первой перегородки, второй — все яблоки между первой и второй перего­родками, третий — все яблоки между второй и третьей пере­городками, а четвертый — все остальные яблоки.

(Если, например, первая и вторая перегородки оказались рядом, то второй мальчик ничего не получает.) Значит, число способов раздела равно числу перестановок 40 яблок и 3 перегородок. По формуле числа переста­новок с повторениями получаем, что это число равно

Пример:

Сколькими способами можно разделить 40 яблок между 4 мальчиками так, чтобы каждый получил по крайней мере 3 яблока (все яблоки по-прежнему считаются одинаковыми)?

Решение:

Сначала дадим каждому мальчику по 3 яблока. А потом разделим оставшиеся 28 яблок так, как было сделано в предыдущей задаче. Всего получаем

способов раздела.

Пример:

Имеется m различных сигнальных флагов и k мачт, на которых их вывешивают. Значение сигнала зависит от того, в каком порядке развешаны флаги. Сколько сигналов можно передать этими флагами, если все флаги должны быть использованы, но некоторые из мачт могут оказаться пустыми?

Решение:

Добавим к m флагам k — 1 перегородку и рас­смотрим всевозможные перестановки из m различных флагов и k одинаковых перегородок. Как ив примере 5, каждой перестановке соответствует свой сигнал (на первую мачту вывешиваются по по­рядку все флаги от начала до первой перегородки и т. д.). Поэтому число сигналов равно числу таких перестановок, то есть равно

Если бы мы не потребовали, чтобы все флаги были использованы, то число сигналов оказалось бы больше. В этом случае задача решалась бы в два этапа. Сначала выберем, какие флаги будут участвовать в сигнале. Если число выбираемых флагов равно s, то выбор можно сделать комбинаторикакомбинаторикакомбинаторика

Оцените статью
Реферат Зона
Добавить комментарий