Урны и шары

ОСНОВНЫЕ ФОРМУЛЫ КОМБИНАТОРИКИ

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

Правило произведения Пусть требуется выполнить одновременно два каких-либо действия. Если первое действие можно выполнить k способами, а второе – m способами, то выполнить эти действия можно k + m способами.

Правило суммы Пусть требуется выполнить одно из каких-либо двух действий, взаимно исключающих друг друга. Если первое действие можно выполнить k способами, а второе – m способами, то выполнить одно из этих двух действий можно k + m способами.

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

Задачи

№4. У двух аудиофилов имеется 5 и 7 CD-дисков соответственно. Сколькими способами они могут обменяться двумя дисками? (5·4·7·6 = 20·42 = 840).

№5. Подсчитайте количество всех четных трехзначных чисел (9·10·5=450).

№6. Подсчитайте количество всех трехзначных чисел, у которых все цифры различные (9·9·8 = 648: числа без нуля – 9·8·7 = 504, числа с одним нулем – 9·8·1+9·1·8=144; 504+144=648).

№7. Руководителю надо назначить двух дежурных, работающих в одном и том подразделении. Всего имеется три подразделения, в которых трудятся 3, 5 и 10 работников соответственно. Сколько вариантов назначения дежурных имеется у руководителя? (3·2 + 5·4 + 10·9 = 6 + 20 + 90 = 116).

№8. Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они не били друг друга (64·49·36·25·16·9·4·2·1 = 3 251 404 800).

Принцип Дирихле Если в n клетках сидит n+1 кроликов, то найдётся клетка, в которой сидят по крайней мере два кролика.

Задачи

№9. В темной комнате в ящике комода лежат вперемешку 100 пар белых и 100 пар черных носков. Какое наименьшее количество носков надо взять, чтобы образовалась одна одноцветная пара? (n + 1, где n – количество цветов).

Факториал Факториалом натурального числа n называется число: n! = n ·(n–1)·(n–2)·...·2·1, причем 0! = 1 по определению.

Бинома Ньютона C^k_n = n !/[ k !×( n – k )!] определяет значение k -го коэффициента в биноминальном разложении: (a + b)ⁿ = C⁰_n×aⁿ + C¹_n×a^n–1×b + + C^k_n×a^n–k×b^k +... + C^n–1_n×a×b^n–1 + Cⁿ_n×bⁿ.

C^k_n = C^n–k_n – симметрия; C^k_n + C^k+1_n = C^k+1_n+1 – равенство Паскаля;

C⁰_n + C¹_n +...+ Cⁿ_n = 2ⁿ; (C⁰_n)² + (C¹_n)² +...+ ( Cⁿ_n )² = Cⁿ_2n.

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

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

Рассмотрим следующие возможные способы выбора:

1. Выбор без возвращения: вынутые шары в урну не возвращаются, и в полученном наборе не могут встречаться одни и те же номера.

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

Условимся, какие результаты выбора (наборы из k номеров шаров) мы будем считать различными. При этом есть следующие две возможности:

1. Выбор без учета порядка: два набора номеров шаров считаются различными, если они отличаются составом. Наборы, отличающиеся лишь порядком следования номеров, считаются одинаковыми. Так, например, при выборе трех шаров из пяти, наборы (1, 2, 5) и (1, 5, 2) не различаются и считаются одинаковыми.

2. Выбор с учетом порядка: два набора номеров шаров считаются различными, если они отличаются составом или порядком номеров. Так, например, при выборе трех шаров из пяти, наборы (1, 2, 5), (1, 5, 2) и (5, 2, 1) считаются различными.

Задачи

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

[1/1] = 3: (1, 2), (1, 3), (2, 3).

[2/1] = 6: (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

[1/2] = 6: (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2).

[2/2] = 9: (1, 1), (1, 2), (2, 1), (1, 3), (3, 1), (2, 2), (2, 3), (3, 2), (3, 3).

Дата добавления: 2014-01-05