Элементы комбинаторики

Комбинаторика – это раздел математики, в котором изучают некоторые операции над конечным множеством элементов и в котором решаются задачи, связанные с этими операциями.

Приведем наиболее распространенные определения и формулы.

Из конечного множества {a₁, a₂, …, a_n}, состоящего из n различных элементов, можно образовать различные наборы, состоящие из k (k n) элементов. Упорядоченные наборы называются размещениями, а неупорядоченные – сочетаниями. Например, из множества {1, 2, 3}, выбирая по 2 элемента (n = 3, k = 2), можно образовать 6 размещений ((1,2), (2,1), (1,3), (3,1), (2,3), (3,2)) и 3 сочетания ((1,2), (1,3), (2,3)).

Число размещений, которые можно образовать, выбирая различными способами k элементов из n, обозначают , а число сочетаний – обозначают . Числа и вычисляют по формулам:

= = n(n - 1)…(n – k + 1). (2)

= = . (3)

где n! = . Размещения из n элементов по n называют перестановками. Различные перестановки содержат одни и те же элементы, расположенные в разном порядке. Общее число P_n различных перестановок из n элементов вычисляют по формуле:

P_n = n! (4)

Рассмотрим задачи на применение вышеприведенных формул.

2.1 Задача. Из пяти карточек с буквами А, Б, В, Г, Д извлекаются наудачу и складываются друг за другом в порядке их извлечения 3 карточки (буквы). Какова вероятность получить при этом слово ДВА (событие А)?

Решение. Общее число n всевозможных троек букв (x, y, z) из букв А, Б, В, Г, Д равно (числу размещений из 5 по 3), т.к. порядок расположения букв здесь существенен. Число m исходов, благоприятствующих событию А равно 1, следовательно

P(A) = = = = .

2.2 Задача. Компания из 10 человек садится на скамейку. Какова вероятность того, что 2 определенных лица окажутся рядом (событие А)?

Решение. Пусть М и N два лица, которые должны сидеть рядом. Могут быть следующие случаи: N сядет правее M, при этом M может сесть на 1, 2, …, 9 место, число таких случаев 9. Кроме того, М и N можно поменять местами и, следовательно, существует способов размещения М и N рядом. Каждому из этих случаев соответствует 8! Способов размещения остальных членов компании. Значит всего способов для рассаживания компании из 10 человек, при которых М и N сидят рядом m = . Общее число способов для произвольного рассаживания компании из 10 человек равно 10!, следовательно

P(А) =

Решите задачи самостоятельно.

2.3 В урне a белых и b черных шаров. Из этой урны вынимают один шар и откладывают в сторону. Этот шар оказался белым. После этого из урны берут еще один шар. Какова вероятность того, что этот шар тоже белый? ((а-1) / (а+b-1)).

2.4 Наудачу выбрано натуральное число, не превосходящее 100. Какова вероятность того, что выбранное число при делении на 8 дает в остатке 2? (0,13).

2.5 Из множества 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 наудачу выбрано число q, после чего составлено уравнение x² + 4x + q = 0. какова вероятность того, что корни этого уравнения окажутся: а) действительными числами; б) целыми рациональными числами; в) действительными иррациональными числами? (а) 0,5; б) 0,3; в) 0,2).

2.6 Наугад выбирается по одной букве из слов «дама» и «мама». Какова вероятность того, что эти буквы: а) одинаковы; б) различны? (а) 0,375; б) 0,625).

2.7 Игральная кость бросается трижды. Пусть x – сумма очков, полученных при всех бросаниях. Что более вероятно: х = 12 или х = 11?

2.8 Частота попадания в мишень при стрельбе 0,6. Сколько было сделано выстрелов, если получено 12 промахов? (30).

2.9 У одного студента 5 книг, у другого – 9. Все книги различные. Сколькими способами студенты могут произвести обмен: а) одной книги на книгу; б) 2 книг на 2 книги? (а) 45; б) 360).

2.10 На вершину горы ведут 5 тропинок. Сколькими способами турист может подняться на гору и потом спуститься с нее? Решите эту задачу с дополнительным условием: подъем и спуск должны происходить по разным тропинкам. (25; 20).

2.11 В пассажирском поезде 9 вагонов. Сколькими способами можно рассадить в поезде 4 человек при условии, что все они должны ехать в различных вагонах? (3024).

2.12 Сколькими способами 3 различных подарка А, В и С можно сделать каким-то 3 из 15 лиц, если: а) никто не должен получить более одного подарка; б) подарок А должно получить определенное лицо? (а) 2730; б) 182).

2.13 В группе 9 человек. Сколько можно образовать разных подгрупп при условии, что в подгруппу входит не менее 2 человек? (502).

2.14 3 дороги соединяют города А и В, 4 дороги соединяют города В и С. Сколькими способами можно совершить поездку из А в С через В и вернуться в А также через С? (144).

2.15 Сколькими способами можно расставить на полке 7 различных книг, если: а) 2 определенные книги должны стоять рядом; б) эти 2 книги не должны стоять рядом? (а) 1440; б) 3600).

2.16 Для участия в команде тренер отбирает 5 мальчиков из 10. сколькими способами он может сформировать команду, если 2 определенных мальчика должны войти в команду? (56).

2.17 Сколько шестизначных чисел можно образовать из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9, если каждое число должно состоять из 3 четных и 3 нечетных цифр, причем никакая цифра не входит в число более одного раза? (28800).

2.18 Игральная кость брошена 3 раза. Какова вероятность того, что при этом все выпавшие грани различны? (5/9).

2.19 В урне 6 белых и 4 черных шара. Из одной урны наудачу извлекли 5 шаров. Какова вероятность того, что 2 из них белые, а 3 черные? (5/21).

2.20 В некоторый день недели во всех классах школы должно быть по 6 уроков. В этот день случайным образом ставятся в расписание 3 урока одного учителя и 2 урока другого. Какова вероятность того, что эти учителя не будут одновременно заняты? (0,2).

2.21 В урне 10 шаров, из которых 2 белых, 3 черных и 5 синих. Наудачу извлечены 3 шара. Какова вероятность того, что все 3 шара разного цвета? (0,25).

2.22 Ребенок играет с 10 буквами разрезной азбуки А, А, А, М, М, Т, Т, Е, И, К. Какова вероятность того, что при случайном расположении букв в ряд он получит слово «математика»? (24/10!).

2.23 В урне 5 белых и 5 черных шаров. Из этой урны последовательно извлечены все шары по одному и разложены в ряд. Какова вероятность того, что цвета шаров чередуются? (1/252).

2.24 Автобусу, в котором 15 пассажиров, предстоит сделать 20 остановок. Предполагая, что все возможные способы распределения пассажиров по остановкам равновозможны, найдите вероятность того, что никакие 2 пассажира не выйдут на одной остановке. ( /20¹⁵).

2.25 n друзей садятся случайным образом за круглый стол. Найти вероятность того, что а) два фиксированных лица М и N сядут рядом, причем N слева от М; б) три фиксированных лица М, N и Q сядут рядом, причем М справа от N, а Q слева. (а) 1/(n - 1); б) 1/(n - 1)(n - 2)).

2.26 Из последовательности чисел 1, 2, 3, …, n наудачу выбираются два числа. Какова вероятность, что одно из них меньше k, а другое больше k, где 1 < k < n – произвольное целое число? ().

2.27 В шкафу находится 10 пар ботинок различных сортов. Из них случайно выбирается 4 ботинка. Найти вероятность того, что среди выбранных ботинок: а) отсутствуют парные; б) имеется ровно одна пара; в) имеются две пары ботинок? (а) 224/323; б) 96/323; в) 3/323).

2.28 Группа, состоящая из 2N мальчиков и 2N девочек, делится случайным образом на две равные части. Найти вероятность того, что в каждой части число мальчиков и девочек одинаково? (()² / ).

2.29 Некий математик носит с собой 2 коробки спичек. Каждый раз, когда он хочет достать спичку, он выбирает наугад одну из коробок. Найти вероятность того, что, когда математик вынет в первый раз пустую коробку, в другой коробке окажется r спичек (r = 0, 1, 2, …, n; n – число спичек, бывших первоначально в каждой из коробок). ( / ).

2.30 В некоторых сельских местностях России существовало когда-то следующее гадание. Девушка зажимала в руке 6 травинок так, чтобы концы травинок торчали сверху и снизу; подруга связывает эти травинки попарно между собой сверху и снизу в отдельности. Если при этом все шесть травинок оказываются связанными в одно кольцо, то это должно было означать, что девушка в текущем году выйдет замуж. Найти вероятность того, что травинки при завязывании наудачу образуют кольцо. (8/15).

2.31 Найти вероятность того, что дни рождения 12 человек приходятся на разные месяцы года. (12!/ 12¹²).

2.32 Имеется n шариков, которые случайным образом разбрасываются по m лункам. Найти вероятность того, что в первую лунку упадет ровно k₁ шарик, во вторую – k₂ шариков и т.д., в m-ю – k_m шариков, если k₁ + k₂ + … + k_m = n.

().

2.33 Вы задались целью найти человека, день рождения которого совпадает с Вашим. Сколько незнакомцев Вам придется опросить, чтобы вероятность встречи такого человека была бы не меньше, чем 0,5 (считать, что в году 365 дней)? (Не менее 253).

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