Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 64
Текст из файла (страница 64)
Сколько различных размещений можно образовать, используя буквы в слове ипзиссезз)и1? 3. Сколько различных размещений можно образовать, используя буквы в слове 5иггех? 4. Сколько различных размещений можно образовать, используя буквы в слове ТаДапаззее? 5. Предположим, что нужно расставить на полке 26 книг, среди которых 8 одинаковых учебников по математике, 6 одинаковых учебников по информатике, 9 одинаковых учебников по физике и 3 — по химии.
Сколькими способами это можно сделать? 6. В урне находятся 6 синих, 5 красных и 14 желтых шаров. Если шары одного цвета неразличимы, то сколько существует способов одновременно вытащить из урны шары одного цвета? 7. Тест содержит 35 вопросов, каждый вопрос имеет пять вариантов ответа: а, б, в, г и д. Сколько может быть различных ответных листов, в которых выбрано равное количество ответов а, б, в, г и д. 8. У профессора Крепка в группе 20 студентов.
Согласно критерию, известному лишь ему одному, он решил поставить две оценки А, три оценки В, десять С, три Р и две оценки с. Сколькими способами он может поставить оценки студентам? 8. В бейсбольной команде 24 игрока. В гостинице они остановились в шести четырехместных номерах. Сколькими способами можно расселить игроков? РАЗДЕП 8.7.
Перестановки и сочетания с повторением 369 при хзузз4 в разложении (х+ у+ з)э? при хзувхз в разложении (х+ 2у+ Зз)щ? при шзх у~а~ в разложении (ю + х + у + с)'т? при швхзувхз в разложении (2т + 4х+ у+ 5з)'з? при хзувз'з в разложении (х+ 2уз+ 4хз)'о? при ш'охшу4зз в разложении (4иР+2хз+уз+5з)ы? 10. Чему равен коэффициент 11. Чему равен коэффициент 12. Чему равен коэффициент 13. Чему равен коэффициент 14. Чему равен коэффициент 16. Чему равен коэффициент 8.7. ПЕРЕСТАНОВКИ И СОЧЕТАНИЯ С ПОВТОРЕНИЕМ ТЕОРЕМА 8.66. Пусть о — множество, содержащее и неразличимых объектов.
Тогда количество различных перестановок, образованных выбором к элементов с повторением, равно и". ПРИМЕР 8.67. Лототрон содержит 500 шаров с номерами. Из него выбирают шар, номер которого записывают. Шар возвращают в лототрон и процедура повторяется. Так продолжается до тех пор, пока не наберется комбинация из пяти номеров. Идея перестановки с повторением может показаться бессмысленной, поскольку перестановки ассоциируются с перегруппировками, которые, похоже, не допускают повторений. Если допустить повторение, то необходимо пересмотреть наше представление о перестановке. Главным свойством перестановки является порядок.
Строка саЬ отличается от строки аЬс. Если опять рассмотреть задачу о номерных знаках автомобилей с тремя буквами, за которыми следуют три цифры, и не допускать повторений, то получим 26х 25х24х10х9х8 различных номерных знаков. Существует Р(25,3) способов выбора букв и Р(10,3) способов выбора цифр. Таким образом, существуют Р(25,3) х Р(10,3) различных номерных знаков. В этом и состоит обычное представление о перестановках. Заметим, что допуская повторение, мы не отказываемся от понятия порядка.
Номерной знак ФПФ199 отличается от номерного знака ПФФ 919. Говоря о перестановках с повторением, имеется в виду, что этот порядок сохраняется. Вспомним, что если в номерном знаке разрешить повторения букв и цифр, то существуют 26 возможных способов выбора для каждой буквы и 10 возможных способов выбора для каждой цифры. Таким образом, если разрешить повторение, то будут существовать 26з х 10з возможных номерных знаков. В общем случае, если имеется к упорядоченных мест, для каждого из которых можно выбрать любой из п объектов, существуют и" способов выбора объектов. Таким образом, число перестановок с повторением, когда й объектов выбираются из п объектов, равно и".
Наверное, идея повторения, использованная здесь, требует разъяснений. Одни из способов трактовки повторения — это думать, что повторение предполагает возвращение объекта и повторное его использование. Другой способ трактовки данного типа повторения состоит в том, что имеется столь достаточное количество объектов каждого типа, которое нельзя исчерпать.
Например, в случае с номерными знаками требуется теперь только три копии каждой буквы и каждой цифры. Приведенная ниже теорема сформулирована для такого представления о повторении. 360 ГЛАВА б. Комбинаторика и вероятность Подсчитаем количество возможных комбинаций чисел. Для каждого из пяти чисел имеется 500 способов выбора. Следовательно, число различных комбинаций составляет 500з. П ПРИМЕР 8.68.
Сколько существует индивидуальных номеров карточек социального страхования? Поскольку номер следует выбирать из неотрицательных целых чисел, меньших десяти, то выбираются девять цифр, причем каждая выбирается из десяти цифр с повторением, поэтому имеются 10э различных номеров карточек социального страхования. П Предположим, что комитет состоит из восьми человек. При принятии решения они голосуют "за", "против" или воздерживаются от голосования. Сколько возможных исходов голосования по данному решению? Если интересует вопрос, кто и как голосовал, тогда речь идет о числе перестановок, когда для каждого голосующего имеются три варианта ответа, что дает Зз возможных исходов голосования.
Допустим, что нас интересует только общий результат голосования. Таким образом, четыре голоса "за", три голоса "против" и один воздержавшийся — это один из возможных исходов. Таким же возможным исходом является вариант: два голоса "за", четыре голоса "против" и два воздержавшихся. Для удобства перечислим сначала голоса "за", затем "против" и, наконец, голоса воздержавшихся. Таким образом, голосование можно изобразить, например, в виде ЗЗЛПВВВВ, где два голоса "за", два "против" и четыре воздержавшихся. Далее можно строить разбиение голосов, например, ЗЗ~ЛП~ВВВВ. Поскольку порядок расположения голосов понятен, можно перейти к записи хх)хх)хххх, изображающей ЗЗ~ПП~ВВВВ. Таким образом, запись ххЙхххххх будет представлять два голоса "за" и четыре воздержавшихся, а запись хххххххх)) будет соответствовать голосованию "за" всех восьми членов комитета.
Таким образом, установлено взаимно однозначное соответствие между возможными исходами голосования и различными способами размещения восьми знаков х и двух знаков !. Но это ни что иное, как количество способов выбора двух мест из десяти для размещения знака ~ или, что эквивалентно, количество способов выбора восьми мест из десяти для размещения знака х. Следовательно, существуют 10! С(10,2) = С(10,8) = —,, способов разместить х и ~.
А значит, существуют 10! С(10,2) = С(10,8) = —,, возможных исходов голосования. Предположим, что п объектов выбираются из й типов объектов с неограниченным повторением. Пусть а, — объект типа 1, тогда п,а,+пзаз+пзаз+..+икая, где и, ) 0 для всех г, а п1+ из+из+ +пь = п представляет выбор п, объектов типа г. Как и прежде, это можно записать в виде а1а1а1 а1~азазаз .
аз~ .. ~аьаьаь. аь, РАЗДЕЛ 8.7. Лврвствновко и сочвтвния с повторением 361 где каждое а; повторено и, раз. Поскольку место расположения каждого типа понятно, то выборку можно записать в виде ххх . х(ххх. х! )ххх х. Заметим, что разделителей ! на один меньше количества типов. Таким образом, имеем п объектов плюс 9 — 1 разделителей, образующих п + й — 1 мест для размещения х или !. Каждое расположение знаков х и ( дает новый способ выбора и объектов из й типов объектов с неограниченным повторением. Поскольку существует С(и+ 9 — 1, и) = С(и+ 9 — 1, и — 1) способов выбора места для знака х или, что эквивалентно, для знака ~, то существуют С(и+ 9 — 1,п) = С(п+ lс — 1,!с — 1) различных способов выбора и из )с типов объектов с неограниченным повторением.
Такие выборки будем называть сочетаниями из гс объектов по п с повторением. Получаем следующую теорему. ТЕОРЕМА 8.69. Количество различных сочетаний из к объектов по п равно С(и+ 9 — 1, п) = С(и+ /с — 1,к — 1) = (и + /с — 1)! и)(й — 1)! ' ПРИМЕР 8.70. Если в булочной продается 10 различных видов пончиков, то сколькими способами можно выбрать дюжину пончиков? Поскольку 12 пончиков выбираются из 10 различных типов с повторением, то имеются (10 + 12 — 1)! 21! 12 )(10 — 1) 9 12! 9! различных способов выбрать дюжину пончиков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
