Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

2Дискретка / комбинаторика

.pdf
Скачиваний:
30
Добавлен:
27.03.2015
Размер:
217.83 Кб
Скачать
m!(n m )!
n!

4. Комбинаторика

Перестановка это упорядоченный набор чисел 1, 2,..., n , обычно трактуемый как биекция на множестве {1, 2,..., n} , которая числу i ставит в соответствие i-й

элемент из набора. Число n при этом называется порядком перестановки.

Число всех перестановок порядка n обозначается P и равняется факториалу

n

P = n! .

n

В более общем смысле, перестановкой произвольного (обычно конечного) множества называется всякая биекция этого множества на себя. Если

исходное

множество содержит qi элементов i -го

сорта,

q1 + ... + qm = n и

элементы

одного

сорта идентичны, то число

таких

перестановок

n (

1

m )

 

n!

.

 

 

 

 

 

 

P

q

,..., q

=

 

 

 

q1 ! qm !

Размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размещением (из n по m) называется упорядоченный набор из m различных элементов некоторого n-элементного

множества. Число размещений из n по

m обозначается

Am

и

задается

 

 

 

 

 

 

n

 

 

соотношением Am =

n!

.

Нетрудно

видеть, что при

n = m

число

 

 

(n m )!

n

 

 

 

 

 

 

размещений превратиться в число перестановок P = n! .

n

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

Anm = nm .

Если на каждую i-ю из m позиций можно поставить один из qi элементов, то количество таких размещений Anm (q1 ,..., qn )= q1 qn .

Сочетанием из n по m называется набор m различных элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания

отличаются от размещений. Число сочетаний Cnm = .

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

(m + n −1)!

повторениями равно Cnm = Cmm+ n−1 = m!(n −1)! .

Свойства сочетаний:

n

1. Бином Ньютона (a + b )n = Cmn ambn m ,

m=0

2. Cnm = Cnn m ,

3. Cnm = Cnm11 + Cnm−1 ,

4. Cnm = n Cnm11 ,

m

5. CnmCmk = Cnk Cnmkk .

Комбинаторные правила: 1. Правило суммы.

Если объект A выбирается n способами, объект B выбирается другими k способами, то «либо A , либо B » можно выбрать n + k способами.

2. Правило произведения.

Объект A выбирается n способами, и объект B после этого выбирается

kспособами, то выбрать « A , а после этого B » можно n k способами.

3.Принцип включений-исключений.

Пусть A , A ,..., A

- конечные множества, тогда

 

 

 

 

 

 

 

 

 

1

2

 

n

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

− ... +

−1

n−1

 

A A ∩ ... ∩ A

 

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A

=

A

 

A A

j

+

A A

A

 

 

 

i

 

i

 

 

i

 

i j

k

(

)

 

1 2

n

 

 

 

i

 

i

 

 

i< j

 

 

 

i < j <k

 

 

 

 

 

 

 

 

 

 

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

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

Пример 4.1:

Пусть есть m различных шаров и n различных урн. Найти число способов раскладки шаров по урнам.

Решение:

Каждый шар может занимать одно из n мест, то есть n число способов размещения одного шара по n урнам, воспользуемся правилом произведения, получим nm .

Пример 4.2:

Сколькими способами можно разместить m одинаковых шаров по n различным урнам?

Решение:

Каждой раскладке шаров по урнам сопоставим бинарный вектор из m + n − 1 элементов, нули шары ( m штук), единицы внутренние перегородки ( n − 1 штук).

0 0 0 1 0 1 1 0 0

Число раскладок равно числу перестановок элементов вектора без учёта

(m + n − 1)!

перестановок нулей и единиц, то есть Cmm+ n −1 = m!(n − 1)! .

Пример 4.3:

Из 12 девушек и 10 юношей выбирают команду, состоящую из пяти человек. Сколькими способами можно выбрать эту команду так, чтобы в неё вошло не более 3 юношей?

Решение:

Воспользуемся правилом суммы и получим ответ

Пример 4.4:

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

Решение:

Пример 4.5:

Сколько можно построить функций со значениями на множестве из m

элементов, если функции зависят от n переменных x1 ,..., xn , где xi может принимать одно из ki значений?

Решение:

Рассмотрим n =1 , тогда для каждого аргумента из k1 можно поставить одно

из m значений, то есть m m , обобщив на случай произвольного n , получим

ki

Пример 4.6:

Из колоды (52 карты) вынули 10 карт. Найти вероятность того, что

1.выбран ровно один туз,

2.выбран хотя бы один туз,

3.не менее двух тузов.

Решение:

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

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

сделать C 9

способами, в итоге получим ответ

4C489

.

 

48

 

C

10

 

 

 

 

 

 

 

52

 

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

C10

способами. В итоге получим ответ

C10

C10

52

 

48

.

 

 

10

48

 

C

 

 

 

 

 

 

 

 

52

 

3.Для выборки не менее двух тузов отнимем от общего числа способов число способов выборки без тузов и с одним тузом. В итоге получим

ответ C5210 C4810 − 4C489 .

C5210

Пример 4.7:

Сколькими способами можно составить три пары из n шахматистов?

Решение:

Для формирования трёх пар выберем с учётом порядка 6 шахматистов, это можно сделать An6 способами. Так как порядок внутри пары не важен (число способов установить порядок внутри пар 23 ) и порядок самих пар

(перестановки 3!) тоже не важен, то итоговый ответ будет

A6

n

.

 

 

23 3!

Пример 4.8:

Сколько существует n -значных чисел, у которых сумма цифр равна k ,

где k < 10 , k = 10 ?

Решение:

Задача сводится к урновой схеме, где n число различных урн и k количество одинаковых шариков (один шар единица). При рассмотрении случая, когда k < 10 мне не можем в одну из позиций положить больше девяти шаров. Один из шаров мы положим в первую урну, так как первая цифра числа не нуль, остаётся разложить k − 1 шар. Поэтому при k < 10 ответ будет Cnk+k1−2 способов.

Если k = 10 , то следует вычесть из общего числа способов варианты, когда в одной из урн становится более 9-ти шариков. Таких вариантов может быть только один, когда в первую урну к уже имеющемуся шарику добавляют ещё

9 шаров, поэтому ответ в случае k = 10 будет C k −1 − 1 .

n + k −2

Пример 4.9:

Сколько существует 10-значных чисел, в которых имеется хотя бы две одинаковые цифры?

Решение:

Для решения задачи из общего числа 10-значных чисел вычтем число чисел, без повторов цифр. Общее количество 10-значных чисел:

В случае чисел без повторов на первую позицию выбираем одну из цифр 1,2,…,9, а на каждую оставшуюся позицию одну из оставшихся цифр это можно сделать 9 9! способами. В итоге получим ответ 9 109 − 9 9!.

Пример 4.10:

Сколько слов можно составить из пяти букв А и не более чем из трёх букв Б?

Решение:

Для получения количества слов нужно просуммировать количество слов, полученных из 5 букв А и не одной Б, из 5 букв А и 1 буквы Б, из 5 букв А и 2 букв Б, из 5 букв А и 3 букв Б. Также следует не учитывать перестановки

одних и тех же букв. В итоге получим ответ 1

6!

 

7!

 

8!

 

= 84 .

+

 

 

+

 

 

+

 

 

5! 1!

5! 2!

5! 3!

 

 

 

 

 

Пример 4.11:

 

 

 

 

 

 

 

 

 

 

В урне a белых и b чёрных шаров ( a ≥ 2 ,

b ≥ 2 ).

Из урны без

возвращения извлекаются 2 шара. Найти вероятность того, что шары одного

цвета.

 

 

 

 

 

 

Решение:

 

 

 

 

 

 

Общее число исходов C 2

 

выбор двух шаров из

смеси шариков.

a +b

 

 

 

 

 

 

Благоприятные варианты C 2

(выбор белых шаров) или C 2

(выбор чёрных

a

 

 

 

 

b

 

шаров). В итоге получим ответ

 

C 2

+ C 2

 

 

a

b

.

 

 

 

 

 

 

 

 

Ca2+b

 

Пример 4.12:

Найти вероятность того, что при размещении n различных шаров по N различным урнам заданная урна будет содержать ровно k ( 0 ≤ k n ) шаров.

Решение:

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

выбрать k шариков из общего количества без учёта порядка в урне. После этого оставшиеся n k шариков разложим по N −1 урнам, применим урновую

C k (N −1)n k

схему и правило произведения. Получим итоговый ответ n .

N n

Пример 4.13:

Колода из 32 карт тщательно перетасована. Найти вероятность того, что все 4 туза лежат в колоде один за другим.

Решение:

Общее число перестановок колоды карт 32! . Представим туз одной картой, в итоге получим 32 − 4 + 1 = 29 карт, где одна карта есть склеенные тузы, число перестановок новой колоды 29! . Учитывая перестановки тузов 4! получим

окончательный ответ 29! 4! .

32!

Пример 4.14:

Какова вероятность угадать k номеров в спортлото 6 из 49?

Решение:

Общее число билетов C496 , то есть выбираем 6 чисел из 49. Для формирования нужного билета нужно выбрать k номеров из шести C6k , а затем добрать оставшиеся номера из 43 не выпавших чисел C436−k . В итоге получим ответ

C k C 6− k

6 43 . C496

Пример 4.15:

Поступающий в ВУЗ сдаёт 4 экзамена. Достаточно набрать 17 баллов. Сколькими способами можно набрать 17 и более баллов?

Решение:

Рассмотрим варианты набора 20, 19, 18 ,17 баллов. 20 баллов можно набрать при получении 5, 5, 5, 5 – 1 вариант. 19 баллов можно набрать при получении 5, 5, 5, 4 с учётом перестановок (получение разных оценок по разным

предметам), но без учёта перестановок пятёрок

4!

= 4 . 18 баллов можно

3!

 

 

набрать, если получить 5, 5, 5, 3 или 5, 5, 4, 4 с учётом получения разных оценок за разные экзамены и без учёта перестановок одинаковых оценок

4!

+

4!

 

= 10 . 17 баллов можно набрать, если получить 4, 4, 4, 5 или 3, 4, 4, 5 –

3!

 

2! 2!

 

 

 

 

4!

+

4!

= 16 . Просуммировав варианты получим 31 способ.

 

 

2!

 

3!

 

 

Пример 4.16:

Сколькими способами можно выбрать 6 карт из колоды (52 карты) так, чтобы среди них были карты каждой масти?

Решение:

Существует два варианта формирования шести карт. Первый: выбираем масть, которая даст три карты, затем выбираем эти три карты, потом

3

добираем из оставшихся мастей по любой карте C41C133 (C131 ) варианта.

Второй вариант: выбираем две масти, которые дадут по две карты, затем выбираем из каждой масти по две карты, потом добираем оставшиеся карты

2 2

C42 (C132 ) (C131 ) варианта. Воспользуемся правилом суммы и получим

3 2 2

итоговый ответ C41C133 (C131 ) + C42 (C132 ) (C131 ) способов.

Пример 4.17:

Сколько пятизначных чисел можно составить из цифр числа 75226522?

Решение:

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

7, 2, 6, 5, 5 – Ρ (1,1,1, 2), 7, 6, 5, 2, 2 – Ρ (1,1,1, 2), 7, 2, 2, 5, 5 – Ρ (1, 2, 2) , 6, 2, 2, 5, 5 – Ρ (1, 2, 2) , 7, 5, 2, 2, 2 – Ρ (1,1, 3) , 7, 6, 2, 2, 2 – Ρ (1,1, 3) , 5, 6, 2, 2, 2 – Ρ (1,1, 3) , 7, 2, 2, 2, 2 – Ρ (1, 4), 5, 2, 2, 2, 2 – Ρ (1, 4), 6, 2, 2, 2, 2 – Ρ (1, 4), 5, 5, 2, 2, 2 – Ρ (2, 3) ,

просуммировав варианты получим 265 вариантов.

Пример 4.18:

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

Решение:

Любой элемент может попасть в одно из множеств A и B или не попасть в них. Итоговый ответ 3n .

Пример 4.19:

Сколько существует n-значных натуральных чисел, у которых цифры расположены в неубывающем порядке?

Решение:

Рассмотрим урновую схему, где сначала идут единицы, затем двойки и т.д. Также возможен вариант, что каких либо цифр нет. Цифры будут служить

урнами, а разряды шариками. Получим ответ Cnn+9−1 = (n +8)! .

n! 8!

Задачи для самостоятельного решения

1.Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом?

2.Сколько существует чисел от 0 до 10n , в которые не входят две идущие друг за другом одинаковые цифры?

3.Сколько диагоналей в выпуклом n -угольнике?

4.В футбольной команде (11 человек) нужно выбрать капитана и ассистента. Сколькими способами можно это сделать?

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

6.В классе 31 человек, сколькими способами можно выбрать команду (11 человек) так, чтобы Петя и Вася не входили в команду одновременно?

7.Множество состоит из n элементов, сколько множеств можно построить из данного множества (мощность множеств всех подмножеств)?

Соседние файлы в папке 2Дискретка

Калькулятор

Сервис бесплатной оценки стоимости работы

  1. Заполните заявку. Специалисты рассчитают стоимость вашей работы
  2. Расчет стоимости придет на почту и по СМС

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

Номер вашей заявки

Прямо сейчас на почту придет автоматическое письмо-подтверждение с информацией о заявке.

Оформить еще одну заявку