Перестановки, размещения и сочетания с повторениями




 

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

 

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

 

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

Например, требуется определить различные размещения букв в слове Миссисипи. Предположим сначала, что все буквы различны. В таком случае существовало бы 11! способов размещения 11 букв. Теперь обратим внимание, что буква "и" встречается четыре раза. Тогда все 11! комбинаций можно разбить на группы, элементы которых буду отличаться только расположением буквы «и» (наппр: «М и1 с с и2 с и3 п и4 », «М и2 с с и1 с и3 п и4 »...). В каждой группе будет по 4! комбинаций (по числу перестановок буквы и). Сейчас они подсчитаны, как различные, хотя это не так. Значит каждым 4! комбинациям из 11! соответствует только одна перестановка. Тогда число перестановок, с учётом того, что все буквы «и» одинаковы будет 11!/4!. Размышляя аналогично относительно остальных повторяющихся букв (с — входит 3 раза — делить на 3!...), получаем

 

 

Рассмотрим общий случай. Пусть у нас есть объекты k различных типов и из них n1 объектов первого типа, n2 объектов второго типа … nk объектов типа №k. Рассуждая таким же образом, как и при решении предыдущей задачи задачи, получим формулу для подсчёта числа перестановок с повторениями.

 

 

//Размещения с повторениями.

 

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

Например, необходимо сколько номеров автобусных билетов можно составить, если номер каждого билета состоит из 4-х цифр от 1 до 7. Заметим, что каждую цифру можно использовать в номере билета неограниченное число раз (номера типа 7777 и 7772 допустимы). Порядок цифр в номере важен (номера 7772 и 2777 различны). Каждую цифру можно выбрать 7 способами. Т. к. выбор каждой следующей следующей цифры не зависит от результата выбора предыдущей, для подсчёта всех возможных вариантов воспользуемся правилом произведения. Получим

 

 

Теперь, рассуждая аналогично для m разновидностей объектов и n мест размещения получим формулу для размещений с повторениями

 

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

 

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

Предположим, что комитет состоит из восьми человек. При принятии решения они голосуют "за", "против" или воздерживаются от голосования. Сколько возможных исходов голосования по данному решению? Если интересует вопрос, кто и как голосовал, тогда речь идет о числе перестановок, когда для каждого голосующего имеются три варианта ответа, что дает 3^8 возможных исходов голосования. Допустим, что нас интересует только общий результат голосования. голосование можно изобразить, например, в виде ЗЗППВВВВ, где два голоса "за", два "против" и четыре воздержавшихся. Далее можно строить разбиение голосов, например, 33|ПП|ВВВВ. Поскольку порядок расположения голосов понятен, можно перейти к записи хх|хх|хххх, изображающей 33|ПП|ВВВВ. Таким образом, запись хх||хххххх будет представлять два голоса "за" и четыре воздержавшихся, а запись хххххххх|| будет соответствовать голосованию "за" всех восьми членов комитета. Таким образом, установлено

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

 

 

вариантов голосования

 

Предположим, что n объектов выбираются из k типов объектов с неограниченным повторением. Пусть аi — объект типа i, тогда, как и в предыдущей задаче можно записать:

a1a1a1...a1a1|a2 a2 a2 ...a2|...akakak...ak

 

Поскольку место расположения каждого типа понятно, то выборку можно записать в виде

xxx...xx|xxx...xx|...xxx...xx

 

Заметим, что разделителей | на один меньше, чем количество типов. Таким образом, имеем n объектов и k - 1 разделителей, образующих и n + k - 1 мест для размещения х или |. Поскольку существует С(n + k - 1, n) = С(n + k - 1, k - 1) способов выбора места для знака х или, что эквивалентно, для знака |, то существуют C(n + k - 1, n) = С(n + k - 1, k - 1) различных способов выбора n из k типов объектов с неограниченным повторением.

 

 

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

 

Задачи

 

Задача №1.

Сколькими способами на шахмотной доске можно расположить 2 белых и 2 чёрных ладьи так, ч.б. они не «били» друг друга (мат олимпиада 8класс:)) (5-10 мин)

Долго рисовать...

64 * (14*С((64 - 22), 2) + (64 - 15) * С(36, 2))

 

Задача №2

Человек покупает 12 игрушек для своих четверых детей. Сколькими способами можно распределить игрушки, что-бы всем детям досталось поровну (4 шт).

 

Для первого ребёнка существует С(12,3) способов выбрать игрушки. Для второго С(9,3), для третьего С(6, 3), для четвёртого С(3,3) =1. И по правилу произведения Q=С(12,3)*С(9,3)*С(6, 3)*1

 

Задача №3

 

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

 

Поставим сначала всех львов так, чтобы между ними был промежуток. Это можно сделать 5! Между львами получили 6 свободных мест. Теперь только осталось распределить эти места между 4 тиграми А(6,4) = 360. Искомое число способов по правилу произведения А(6,4)*5!

 

Задача №4

 

Сколько существует чисел, меньших 10000 и таких, что сумма цифр равна 12?

 

12=1+1+1+1+1+1+1+1+1+1+1+1

 

Если в числе две значащие цифры.

1+1+1+1+1 / 1+1+1+1+1+1+1 — пример 2-х значащих цифр (57)

Число различных положений знака / - С(10,1)=10

Числа <10000 c двумя значащими цифрами:

хх

хх0

хх00

 

Всего таких чисел С(10,1)*3

 

Если в числе три значащие цифры.

1+1+1+1+1 +1 / 1+1+1 / 1 +1+1 — пример 2-х значащих цифр (633)

Число различных положений знака / - С(10,2)

Числа <10000 c тремя значащими цифрами:

ххх

ххх0

 

….

 

Всего чисел С(10,1)*3+С(10,2)*2+С(10,3)

 

 

Задача №5

Если многоугольник имеет n сторон, то сколько у него диагоналей?

 

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

Т.е. число диагоналей равно числу сочетаний вершин по 2: C(n,2) — n.

Проверим:

Для треугольника:

Для четырехугольника:

Для пятиугольника:

 

Задаче №6

У профессора Кренка в группе 20 студентов. Согласно критерию, известному лишь ему одному, он решил поставить две оценки А, три оценки В, десять С, три D и две оценки F. Сколькими способами он может поставить оценки студентам?

 

Судя по всему, этот критерий — это гауссово распределение со средним где-то в районе тройбана (C);-) Кроме того, кого-то мне этот Кренк напоминает...

Задача на перестановки с повторениями. Общее число их вычисляем следующим образом:

 

 

Задача №7

Сколько существует решений уравнения

таких, что

 

Эта задача эквивалентна следующей:

1+1+1+1+1+1+1+1+1+1+1+1 = 12

Нужно расставить три разделителя на место плюсов. Число способов равно C(12,3) = 220

 

 

Задача №8

Показать, что коэффициент при в разложении равен C (n, m)

 

(n раз)

 

Для получения слагаемого нужно при перемножении скобок взять a ровно m раз. После приведения подобных членов коэффициент при этом слагаемом будет равен числу способов такого выбора. Считая все скобки (и выбираемые из них символы) разными, получаем, что искомое количество способов равно как раз C (n, m)

 

 

Задача 1. Определите сколькими способами можно выбрать 10 шаров из 9 красных, 7 черных, 6 белых и 11 синих шаров.

 

Решение

Если считать, что шаров бесконечно, то таких комбинаций . Однако у нас шаров некоторых цветов < 10. Значит из полученного числа надо удалить комбинации.

 

1) где более 9 красных шаров. То есть 10 - такая комбинация одна.

2) где более 7 черных шаров. То есть от 8 до 10. Таких комбинаций - заполняем 8 мест черными, а остальные места шарами любого цвета.

3) где более 6 белых шаров. То есть от 7 до 10. Таких комбинаций - заполняем 7 мест белыми, а остальные места шарами любого цвета.

 

Итого:

 

 

Задача 2. Сколько нечетных целых чисел находятся между числами 100 и 1000?

 

Решение

Пусть S — множество нечетных целых чисел между 100 и 1000. Для пусть - подмножество множества S такое, что i является последней цифрой его элементов. Для каждого i существуют 9 вариантов выбора первой цифры и 10 вариантов выбора второй цифры, так что каждое множество S i содержит 90 элементов.. поэтому между 100 и 1000 есть 450 нечетных чисел.

 

 

Задача 3. Берутся все перестановки из 5 чисел 1, 2, 3, 4, 5. Во скольких из них ни одно число не стоит на своем месте?

Решение проводится методом включения/исключения. Обозначим через () свойство перестановки, заключающееся в том, что число стоит на своем месте, а через - количество перестановок, обладающих этим свойством. Точно так же через обозначим количество перестановок, одновременно обладающих свойствами и и т. д. Наконец, через обозначим количество перестановок, не обладающих ни одним из свойств (1), (2), (3), (4), (5), т. е. перестановок, в которых ни одно число не стоит на своем месте.

По формуле включений и исключений имеем:

Здесь - общее число всех перестановок из 5 элементов.

В данном случае задача облегчается тем, что свойства (1), (2), (3), (4), (5) совершенно равноправны. Поэтому ясно, например, что Точно так же имеем В последнем случае число пар равно Аналогично имеем троек, четверок и пятерок.

Поэтому предыдущую формулу можно переписать так:

Задача 4. Сколько существует различных четырехзначных положительных чисел, если, по крайней мере, две цифры в числе совпадают? Числа, начинающиеся с нуля (например, 0001) не считаем четырехзначными.

Решение.

Всего четырехзначных целых чисел существует 9000. Определим, сколько существует четырехзначных чисел с различными цифрами. Очевидно, первую цифру можно выбрать 9 способами. Вторую цифру — также 9 способами (т.к. появляется возможность выбрать 0), третью — 8 способами, четвертую — 7 способами. Если вычесть число четырехзначных чисел с разными цифрами из общего числа четырехзначных чисел, получим искомое число:

Задача 5. По пустыне идет караван из 9 верблюдов. Путешествие длится много дней, и наконец, всем надоедает видеть впереди себя одного и того же верблюда. Сколькими способами можно переставить верблюдов так, чтобы впереди каждого верблюда шел другой, чем раньше?

 

Решение. Такие перестановки наверняка существуют (например, можно переставить верблюдов в обратном порядке). Для решения задачи перенумеруем верблюдов в первоначальном порядке от конца каравана к началу числами 1, 2, 3, 4, 5, 6, 7, 8, 9. Таким образом, последний верблюд получает номер 1, предпоследний - 2 и т д. Нам нужно найти все перестановки из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, в которых не встретится ни одна из пар (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9). Для решения снова используем формулу включений и исключений. Сосчитаем сначала, во сколько перестановок входит пара (1,2). Мы можем считать эту пару за один элемент. Поэтому общее число элементов будет 8, а не 9, и число перестановок, содержащих (1,2), равно Тот же результат получаем для всех 8 пар.

Теперь рассмотрим перестановки, содержащие данные две пары. В этом случае объединяем элементы, входящие в каждую из этих парю. При этом если обе пары содержат общий элемент, то объединяем все три элемента. Иначе объединяем элементы по 2. В обоих случаях после объединения получаем 7 новых элементов, которые можно переставить способами. А две пары можно выбрать способами.

Совершенно так же доказывается, что количество перестановок, содержащих данные k пар, равно По формуле включений и исключений получаем:

Задача 6.

Сколькими способами на шахмотной доске можно расположить 2 белых и 2 чёрных ладьи так, ч.б. они не «били» друг друга (мат олимпиада 8класс:)) (5-10 мин)

Долго рисовать...

Решение.

64 * (14*С((64 - 22), 2) + (64 - 15) * С(36, 2))

 

Задача 7.

Человек покупает 12 игрушек для своих четверых детей. Сколькими способами можно распределить игрушки, что-бы всем детям досталось поровну (4 шт).

 

Решение.

Для первого ребёнка существует С(12,3) способов выбрать игрушки. Для второго С(9,3), для третьего С(6, 3), для четвёртого С(3,3) =1. И по правилу произведения Q=С(12,3)*С(9,3)*С(6, 3)*1

 

Задача 8.

 

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

 

Поставим сначала всех львов так, чтобы между ними был промежуток. Это можно сделать 5! Между львами получили 6 свободных мест. Теперь только осталось распределить эти места между 4 тиграми А(6,4) = 360. Искомое число способов по правилу произведения А(6,4)*5!

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: