Задачи по теории вероятности
статья по алгебре (11 класс) по теме

Л.А.Померанцева,

руководитель дисциплины

«Математика, информатика и ИКТ»

МсСВУ.

Элементы комбинаторики в школьном курсе математики.

 Вступление.

Несколько лет назад в школьный курс математики был включён такой предмет, как «Статистика и теория вероятности». Рекомендованным учебником был учебник Тюрина с тем же названием. В нём подробно рассматривались все темы, решались задачи и предлагались самостоятельные и контрольные работы. Но в последнее время в связи с ограниченностью учебных часов по математике этот курс сокращают до нескольких глав в учебнике алгебры с 7 по 9 класс. Хотя в диагностических и экзаменационных работах в формате ГИА и ЕГЭ  задачи на нахождение вероятности и статистические задачи присутствуют.

Зачастую преподавателям недостаточно материала  в учебниках для изучения данной темы. Я предлагаю материал по теме «Элементы комбинаторики» в помощь преподавателям математики.

Простейшие комбинаторные задачи

Пусть дана одна или несколько совокупностей каких- либо предметов (объектов) и требуется составить комбинации из этих предметов, удовлетворяющие некоторым поставлен ным условиям. Задачи о подсчете числа возможных комби наций называются комбинаторными. Например, сколькими способами можно расположить в ряд три различных пред мета? Здесь ответ ясен — шестью способами, так как легко перебрать возможные расположения: 1 2 3, 1 3 2, 2 1 3, 231,312,321 (роль «различных предметов» играли цифры 1, 2 и 3). Но уже значительную трудность пред ставляет собой решение такой довольно широко известной комбинаторной задачи: сколько существует «счастливых» номеров среди 1000 000 шестизначных номеров трамвай ных билетов (номер считается «счастливым», если сумма первых трех цифр равна сумме последних трех цифр)? Здесь ответ 55252 совсем не очевиден, а получить его прямым перебором можно лишь на самой мощной ЭВМ.

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

Задача 1. О числе выборок из нескольких множеств. Даны два множества предметов, в первом т элементов, второе множество содержит n элементов. Сколько можно составить пар элементов, выбирая по одному из каждого множества? Например, из двух мно жеств

{I, II, III}, {1, 2, 3, 4, 5}

можно составить 15 пар:

{I, 1}, {I, 2} {I, 3}, {I, 4}, {I, 5}, {И, 1}, {11,2}, {11,3}, {11,4}, {11,5}, {111,1}, {111,2}, {III, 8}, {III, 4}, {III, 5}.

Решить задачу в общем виде совсем просто. Из пер вого множества один элемент можно выбрать m спосо бами. При каждом выборе этого элемента из второго мно жества один элемент выбирается n способами. Всего полу чается m∙n комбинаций, составляющих пары.

Задача естественно обобщается на выборки из несколь ких множеств. Пусть даны k множеств, содержащие по m1,m2 ..., mk элементов, соответственно. Сколькими способами можно составить комбинации, содержащие по одному элементу из каждого множества? Из первых двух множеств можно составить m1∙m2 пар. Присоединение к каждой такой паре элемента из третьего множества можно сделать т3 способами, так что число выборок троек равно m1∙m2∙m3. К каждой тройке можно присоединить элемент из четвертого множества m4 способами, так что число выборок четверок равно m1∙m2∙m3∙m4. Продолжая аналогичные рассуждения, мы придем к тому, что число выборок по одному элементу из всех k множеств равно т1∙т2∙т3...∙mk.

Задача 2. Перестановки. Сколькими способами можно расположить в ряд n элементов?

Без нарушения общности можно считать, что перестав ляемыми элементами являются числа натурального ряда 1, 2,…n. Рассмотрим сначала «маленькие» частные случаи. При n = 2 имеются две перестановки: (1, 2) и (2, 1). При n = 3, как мы видели выше, имеется шесть перестановок. При п = 4, не перебирая все перестановки, проведем следующее несложное рассуждение. На первом месте может находиться один из четырех элементов. При каждом выборе первого элемента остальные три во все возможных порядках занимают остальные три места, так что существует шесть различных перестановок при фикси рованном первом элементе. Следовательно, общее число перестановок равно 6∙4 = 24. Это рассуждение имеет общий характер. Обозначим через Рn-1 число перестановок (n-1) элементов и через Рп число перестановок п элементов. В каждой перестановке n элементов на первом месте может оказаться один из элементов 1,2, …n, так что имеется n возможностей выбора первого элемента. При каждом из них для оставшихся (n-1) элементов имеется Pn-1 воз можностей расположений на остальных n - 1 местах, ибо эти расположения отличаются только порядком элементов. Итак, пришли к соотношению Pn =n∙ Pn-1 откуда после довательно получаем, исходя из Р2 = 2, что 

Р3 = 3∙2 = 3!,P4 = 4∙ P3 = 4∙3∙2 = 4!; P5 = 5∙P4 = 5∙4∙3∙2 = 5! и т. д. Допустив, что Рn-1=(п—1)!, получим, что Pn=n∙ Pn-1= n!

Это рассуждение является фактически доказательством посредством метода математической индукции формулы Рn = n!, которая и решает задачу.

Задача 3. Размещения. Сколькими способами можно выбрать и расположить в ряд m элементов из дан ного множества, содержащего n элементов? Такие распо ложения, состоящие из m элементов, выбранных из данных n элементов, и отличающиеся либо самими элементами, либо их порядком, либо и тем и другим, называются разме щениями, а их число принято обозначать символом Anm (читается «A из n по m»). Например, из четырех элемен тов 1, 2, 3, 4 (п = 4) можно составить 12 размещений по 2 элемента (m = 2):

(1, 2), (2, 1), (1, 3), (3, 1), (1, 4), (4, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3).

Таким образом, A42= 12. Как же вычислить Anm ? По ступим следующим образом. Возьмем все перестановки из n элементов и «вырежем» в каждой из них первые m эле ментов, отбросив остальные      n - m элементов. Останутся размещения из п элементов по т, но каждое размещение встретится столько раз, сколько перестановок можно со ставить из отброшенных п—т элементов, т. е. Рп-т раз. Таким образом, число размещений из n элементов по m в Рn-m раз меньше числа перестановок п элементов, т. е.

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

откуда следует уже выведенная формула числа размеще ний из n по m.

Задача 4. Сочетания. Сколькими способами из множества, содержащего n элементов, можно выбрать под множество, составленное из m элементов? Такие подмно жества, которые различаются только набором элементов без учета их взаимного расположения, называются соче таниями. Так, например, из четырех элементов 1, 2, 3, 4 можно составить шесть сочетаний по два: {1, 2}, {1, 3}, ]1, 4}, {2, 3}, {2, 4},      {3, 4}. (Фигурные скобки подчеркивают отличие сочетаний от размещений; размещения (1, 2) и (2, 1) считаются различными, хотя и составлены из одних и тех же элементов, а {1, 2} и {2, 1} считаются одним и тем же сочетанием.) Число сочетаний из n  элементов по m обозначается символом   , например .

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

или, если подставить вместо и Рт их значения, , откуда

Мы получили, что число сочетаний равно биномиаль ному коэффициенту, т. е. коэффициенту при  an-mxm   в мно гочлене, равном       (а + х)п. Это совпадение неслучайно. Би ном Ньютона, т. е. формула для записи (а + х)п по сте пеням x, легко может быть установлена на основании ком бинаторных соображений. Именно,

(а + х)п = (а + х ) (а + х) ∙... ∙ (а + х) (п сомножителей).

Для того чтобы умножить несколько многочленов, доста точно перемножить их члены по одному из каждого во всех возможных комбинациях и сложить результаты. Здесь в каждом сомножителе два слагаемых. Из каждого сом ножителя можно брать либо первое слагаемое a, либо второе х. Если взять n-m раз первое слагаемое и  m раз второе, то произведение равно ап-т∙хт. Но выбрать т раз второе слагаемое из n биномов можно как раз  способами, так что одночлен  an-mхт входит в (a+x)n с коэффи циентом

Приведем несколько примеров, связанных с рассматри ваемыми вопросами.

Пример 1. Сколькими способами можно расположить в ряд 5 черных и 5 белых шашек?

Решение. Всего в рассматриваемом ряду 10 мест. Зная номера мест, в которые устанавливаются 5 черных шашек, мы знаем и все расположения. Следовательно, искомое число равно

Пример 2. Сколькими способами можно расположить в ряд 5 черных, 4 белых и 3 красных фишки?

Решение. В отличие от предыдущего примера, не посредственно применить выведенные формулы нельзя, но для решения нетрудно применить рассуждения, подобные выводу формулы для числа сочетаний. Именно, зануме руем черные фишки числами 1, 2, 3, 4, 5; белые - чис лами 6, 7, 8, 9; красные - числами 10, 11, 12. Мы знаем, что 12 предметов можно расположить в ряд 12! спосо бами. Но все расположения фишек не меняются при всех перестановках фишек с номерами 1—5, с номерами 6—9 и о номерами 10—12. Поэтому число различных расположений равно

Пример 3. Доказать, что число способов появления 10 очков при трехкратном бросании игральных костей равно коэффициенту при x10 в многочлене (х+х2 + х3 + x4 + x5 +x6)3

Решение. Нужно найти, сколькими способами можно разбить число 10 на три слагаемых, порядок которых не безразличен, причем каждое слагаемое принимает только значения 1, 2, 3, 4, 5, 6. Точно та же задача возникает при трехкратном умножении многочлена х + х2 + х3 +x4 +x5 +x6 на себя по правилу умножения каждого слагаемого первого сомножителя на каждое слагаемое второго и третьего. Это и решает задачу. Искомый коэф фициент можно вычислить, например, так. Многочлен

(х + х2 + х3 +x4 +x5 +x6)3

равен 

Выполнив деление по правилу деления многочленов, по лучим

x18 +   Зx17 + 6x16 + 10x15 + 15x14 + 21x13 + 25x12 + 27x11 + 27х10 + 25х9 + 21x8+15x7+10xв + 6x5 + 3x4+x3.

Коэффициент при xk дает число случаев, при которых число очков при трехкратном бросании кости равно k. Искомое число равно 27.

Пример 4.  Опыт состоит в подбрасывании монеты n раз, при этом записывается последовательность появле ний герба и цифры. Каково число возможных комбина ций появлений герба и цифры? В скольких комбинациях герб встретится ровно k раз?

Решение. Каждое бросание монеты имеет два воз можных исхода: герб или цифра. Всего монета подбрасы вается n раз. Каждая возможная комбинация гербов и цифр - выборка из n двухэлементных множеств, следова тельно, общее число комбинаций равно 2п (см. задачу 1). Второй вопрос аналогичен задаче о числе сочетаний из n элементов по m?т. е. число комбинаций, в которых герб встречается ровно k раз, равно  Cnk.

Упражнения

1. Сколько существует перестановок элементов 1, 2, в которых элемент 1 находится не на первом месте?

Ответ. Рn-  Pn-1=        (n— 1) (n — 1)!

2. Сколько существует перестановок элементов 1, 2, …,n, в ко торых элементы 1 и 2 находятся не на своих местах?

Ответ. Pn – Pn-1 – Pn-1 +Pn-2  = (n2-3n+3) (n-2)!

3. Сколько существует сочетаний из элементов 1,2, ..., n по m    (2

Ответ.