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

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

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

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

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

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

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

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

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

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

a₁a₁a₁...a₁a₁|a₂ a₂ a₂ ...a₂|...a_ka_ka_k...a_k

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

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) не считаем четырехзначными.