Лекции 1-4. Лекции 14 Е. А. Бунимович, В. А. Булычев Е. А. Бунимович, В. А. Булычев, 2005 Педагогический университет Первое сентября
 Скачать 0.58 Mb.
|
|
Сколько различных символов можно закодировать таким образом? Другими словами, сколько существует различных двоичных кодов дли- ны 8? Выстраивая комбинацию из восьми нулей и единиц, мы можем вы- брать первую цифру двумя способами, после чего вторую цифру — тоже двумя способами и т.д. Всего получаем 2 · 2 · … · 2 = 2 8 = 256 комбина- ций. Именно столько символов содержит так называемая таблица ASCII, давно ставшая стандартом для представления символов в памяти компью- тера (сейчас ей на смену пришли более длинные 16-разрядные коды, по- зволяющие кодировать уже 2 16 = 65536 различных символов). Выписывать все 256 комбинаций мы здесь не будем, напишем только начало и конец этой последовательности: 00000000; 00000001; 00000010; … 11111110; 11111111. В предыдущих примерах при выписывании комбинаций мы не заду- мывались, в каком порядке они перечислялись: комбинаций было мало, они и так были все «на виду». Теперь этот порядок необходим, посколь- ку иначе мы рискуем потерять какие-то из комбинаций или выписать некоторые из них повторно. Комбинаторика и вероятность 40 Самый естественный порядок, который можно установить на комби- нациях, называется лексикографическим. За этим устрашающим сло- вом стоит очень простой принцип упорядочивания: сначала сравнивают- ся первые элементы комбинаций; если они совпадают, то сравниваются вторые, и так далее до первой пары несовпадающих элементов. Та ком- бинация, у которой этот элемент меньше, считается меньшей. Если срав- нение элементов оборвалось из-за того, что одна из комбинаций оказа- лась короче, то она также считается меньшей. Именно так упорядочива- ются слова в словаре — отсюда и название способа — «лексикографи- ческий». Иногда удобное начинать сравнение элементов не с начала, а с конца комбинации, и упорядочивать комбинации не по возрастанию, а по убыванию соответствующих элементов. Полученный в результате такого сравнения порядок называется антилексикографическим, но мы им пользоваться не будем. Отметим еще, что при сравнении комбинаций мы предполагаем, что порядок уже установлен на элементах, из которых строится комбинация. Когда элементами являются цифры, числа, буквы, — это действительно так. Если же никакого естественного порядка на самих элементах нет (например, объекты — это люди или цвета), то мы может установить его сами. После всего сказанного попробуйте ответить на вопрос: какая комби- нация в последовательности кодов из последнего примера следует за комбинацией 00101111? А какая предшествует ей? Еще один пример иллюстрирует применение двух комбинаторных правил — умножения и сложения — вместе. Пример 5. Сколькими способами можно посадить шестерых школь- ников на скамейку так, чтобы Коля и Оля оказались рядом? Будем считать, что на скамейке 6 пустых мест. Посадить на одно из них Колю можно шестью различными способами, после чего посадить рядом с ним Олю можно… одним или двумя различными способами. Это зависит от того, куда мы посадили Колю — на крайнее место или нет. Самое время применить правило сложения. Разобьем все искомые комбинации на два класса: 1-й класс: Коля сидит на краю, Оля рядом с ним; 2-й класс: Коля сидит где-то в середине, Оля рядом с ним. Заметим, что эти классы действительно не пересекаются и исчерпывают все комбинации — ведь, в конце концов, Коля сидит либо на краю, либо Лекция 2 41 где-то в середине. Посчитаем число комбинаций в 1-ом классе: место с краю для Коли можно выбрать двумя способами, после чего Олю можно посадить рядом с ним только одним способом, после чего оставшиеся 4 места можно занять 4 3 2 1 ? ? ? способами. Значит, в этом классе будет 2 1 4 3 2 1 48 ? ? ? ? ? = комбинаций. Посчитаем число исходов во 2-ом классе: место в середине скамей- ки для Коли можно выбрать четырьмя способами, после чего Олю мож- но посадить рядом с ним двумя способами, после чего оставшиеся 4 ме- ста можно занять 4 3 2 1 ? ? ? способами. Значит, в этом классе будет 4 2 4 3 2 1 192 ? ? ? ? ? = комбинации. Итого по правилу сложения 48 + 192 = 240 способов. Попробуйте выписать часть из них в лексикографическом порядке. 2. Перестановки и размещения. Факториал В комбинаторике принято каждому виду комбинаций давать специ- альное название. Сейчас мы познакомимся с двумя такими видами — перестановками и размещениями. Перестановкой из n элементов называется комбинация, в которой все эти n элементов расположены в определенном порядке. Таким обра- зом, перестановки отличаются друг от друга только порядком располо- жения элементов. Пример 1. Вот все перестановки из букв A, B, C, выписанные в лек- сикографическом порядке: ABC, ACB, BAC, BCA, CAB, CBA. Размещением из n элементов по k называется комбинация, в кото- рой какие-то k из этих n элементов расположены в определенном поряд- ке. Таким образом, размещения отличаются друг от друга не только по- рядком расположения элементов, но и тем, какие именно k элементов выбраны в комбинацию. Пример 2. Вот все размещения из букв A, B, C по 2: AB, BA, AC, CA, BC, CA. * * * С помощью правила умножения легко вычисляются количества пе- рестановок и размещений. Найдем эти количества. Комбинаторика и вероятность 42 При формировании перестановки из n элементов первый элемент можно выбрать n способами, после чего второй элемент — (n – 1) спо- собами (так как один элемент уже выбран), после чего третий элемент — (n – 2) способами и так далее. Всего получаем ( 1) ( 2) ... 2 1 n n n ? ? ? ? ? ? ? перестановок. Полученное количество — произведение натуральных чисел от 1 до n — в математике называется факториалом числа n и обозначается n!. Отметим одну важную особенность этой замечательной функции — ее быстрый рост. Приведем для примера несколько значений факториала для возрастающих значений n: Отметим также, что для удобства полагают 0! = 1. Теперь найдем количество размещений из n элементов по k. Первый элемент в размещении можно выбрать n способами, после чего второй элемент — (n – 1) способами (так как один элемент уже выбран), после чего третий элемент — (n – 2) способами и так далее. Пока все, как в перестановке. Только такой выбор будет делаться не n раз, а только k, поэтому по правилу произведения получим ( 1) ( 2) ... ( 1) n n n n k ? ? ? ? ? ? ? + размещений (в этом произведении как раз k сомножителей). Это произ- ведение можно «свернуть» в дробь с использованием факториалов: ( 1) ( 2) ... ( 1) n n n n k ? ? ? ? ? ? ? + = ! ( )! n n k ? Найденные нами количества перестановок и размещений имеют в комбинаторике специальные обозначения — n P и k n A соответственно (читаются как «пэ из эн» и «а из эн по ка»). С использованием этих обозначений выведенные формулы для числа перестановок и размеще- ний запишутся так: n 0 1 2 3 4 5 6 7 n! 1 1 2 6 24 120 720 5040 8 9 10 11 12 13 40 320 362 880 3 628 800 39 916 800 479 001 600 6 227 020 800 Лекция 2 43 ! n P n = , ! ( )! k n n A n k = ? А теперь решим с помощью этих формул несколько задач. Пример 3. Сколькими способами можно расставить на книжной полке собрание сочинений Диккенса, включающее 30 томов? Каждый такой способ — это перестановка из 30 элементов. Всего таких перестановок будет 30 30! 265 252 859 812191058 636 308 480 000 000 P = = Пример 4. На книжную полку влезает только 8 любых томов из 30-томного собрания Диккенса. Сколькими способами можно запол- нить этими томами такую полку? Каждый способ — это размещение из 30 элементов по 8. Всего таких размещений будет 8 30 30! 30! 235989 936 000 (30 8)! 22! A = = = ? * * * Поскольку число перестановок быстро растет с ростом N, то выпи- сывать их вручную даже для небольших N дело безнадежное. Но инте- ресно решить другую задачу. Будем считать, что на перестановках уста- новлен лексикографический порядок. Рассмотрим какую-нибудь пере- становку из чисел от 1 до 7: 1 6 7 3 5 4 2. Какая перестановка будет следовать непосредственно за ней? Чтобы найти такую перестановку, нужно увеличить как можно более далекие от ее начала элементы на как можно меньшую величину. Начнем с последнего элемента и будем двигаться от конца к началу перестановки. • Можно ли увеличить 2, не изменяя предыдущие элементы? Нет. • Можно ли увеличить 4, не изменяя предыдущие элементы? Нет. • Можно ли увеличить 5, не изменяя предыдущие элементы? Нет. • Можно ли увеличить 3, не изменяя предыдущие элементы? Да, по- скольку после 3 в этой перестановке есть элементы, большие 3. Наи- меньший из этих элементов — 4. Комбинаторика и вероятность 44 Заменяем 3 на 4. Оставшиеся элементы выписываем по возрастанию: 1 6 7 4 2 3 5. Это будет перестановкой, которая следует непосредственно за исход- ной в лексикографическом порядке. 3. Сочетания Поскольку мы уже рассмотрели комбинаторные правила умножения и сложения, естественно ожидать, что есть аналогичные правила с деле- нием и вычитанием. Это действительно так, хотя их не всегда формулируют в таком явном виде, как правило умножения. Это скорее не правила, а некоторые об- щие принципы для подсчета комбинаций. Итак, правило вычитания: при подсчете комбинаций, обладающих заданным свойством, иногда проще найти количество комбинаций, которые этим свойством НЕ обла- дают, и вычесть его из общего количества комбинаций. Пример 1. Найдите количество трехзначных чисел, в записи кото- рых есть хотя бы один 0. Воспользуемся правилом вычитания. Сначала найдем количество всех трехзначных чисел — это можно сделать и без всякой комбинаторики — их будет 999 – 99 = 900. Теперь найдем, сколь- ко из них не содержат ни одного 0: на первое место можно поставить любую из девяти цифр, на второе — любую из девяти цифр и на третье — любую из девяти цифр (каждый раз исключаем 0). Всего по правилу умножения будет 9 · 9 · 9 = 729 вариантов. А теперь найдем ответ по правилу вычитания: 900 – 729 = 171 — столько трехзначных чисел содержат хотя бы один 0. Теперь сформулируем правило деления: если при подсчете иско- мых комбинаций мы каждую из них посчитали m раз, то нужно поделить найденное количество комбинаций на m. Формулировка кажется довольно странной — зачем считать каждую из комбинаций по несколько раз? Но из примеров сейчас все будет ясно. Пример 2. Из класса, в котором учится 25 учеников, нужно выбрать троих для участия в школьной олимпиаде. Сколькими способами можно это сделать? Первого ученика можно выбрать 25 способами, после чего второго ученика — 24, после чего третьего — 23. Всего по правилу умножения Лекция 2 45 получится 25 · 24 · 23 = 13 800 способов. Но это еще не ответ! Дело в том, что при таком подсчете мы считали каждый искомый вариант по несколько раз: скажем, вариант, в котором на олимпиаду отправляются Иванов, Петров и Сидоров встречался в виде комбинаций: • Иванов — Петров — Сидоров; • Иванов — Сидоров — Петров; • Петров — Иванов — Сидоров; • Петров — Сидоров — Иванов; • Сидоров — Иванов — Петров; • Сидоров — Петров — Иванов; то есть в виде шести различных размещений. Легко понять, что лю- бой другой вариант считался тоже шесть раз: именно столько перестано- вок можно составить из трех выбранных учеников. Для получения отве- та воспользуемся правилом деления: разделим найденное количество вариантов на 6: 13800 : 6 = 2300 — столько способов выбрать трех учеников из 25. В последнем примере мы столкнулись еще с одним важнейшим ти- пом комбинаций, часто использующемся в комбинаторике — сочета- ниями. Сочетанием из n элементов по k называется комбинация, в ко- торой из этих n элементов выбраны любые k без учета их порядка в комбинации. Таким образом, для сочетания имеет значение только состав выбранных предметов, а не их порядок. Другими словами, со- четание — не что иное, как любое k-элементное подмножество n-эле- ментного множества. Пример 3. Вот все сочетания из букв A, B, C по две: [AB], [AC], [BC]. Квадратные скобки использованы здесь специально для того, чтобы показать, что порядок следования элементов в комбинации не имеет зна- чения, т.е. [AB] = [BA]. Такое обозначение часто используется в матема- тической литературе. * * * Формулу для числа сочетаний мы выведем из формулы для числа размещений с помощью правила деления. При подсчете размещений из n по k мы считали число способов, которым можно выбрать k предме- Комбинаторика и вероятность 46 тов из n с учетом их порядка. Каждое сочетание учитывалось при этом столько раз, сколько существует способов упорядочить выбранные k предметов, т.е. k! раз. По правилу деления, чтобы найти число сочета- ний, нужно поделить число размещений на k!: ! ( )! ! n n k k ? ? Найденное количество сочетаний имеет в комбинаторике специаль- ное обозначение — k n C (читается как «цэ из эн по ка»). С использовани- ем этого обозначения выведенная формула запишется так: ! ( )! ! k n n C n k k = ? ? А теперь решим с ее помощью несколько задач. Пример 4. Из колоды, в которой 36 карт, выбирают 6 карт. Скольки- ми способами можно это сделать? Каждая интересующая нас комбина- ция — это сочетание из 36 по 6. Всего таких сочетаний будет 6 36 36! 36 35 34 33 32 31 1947 792 30! 6! 6 5 4 3 2 1 C ? ? ? ? ? = = = ? ? ? ? ? ? * * * Часто при подсчете комбинаций приходится применять формулы для числа сочетаний вместе с правилом умножения. Пример 5. Из колоды, в которой 36 карт, выбирают 6 карт. Сколько способов сделать это так, чтобы среди них оказалось 2 туза? Для получения любой интересующей нас комбинации нужно сначала выбрать любые 2 туза из 4, после чего выбрать любые 4 карты из 32 «нетузов». Первое действие можно осуществить 2 4 4! 6 2! 2! C = = ? способами, после чего второе действие – 4 32 32! 32 31 30 29 35960 28! 4! 4 3 2 1 C ? ? ? = = = ? ? ? ? способами. Лекция 2 47 По правилу умножения общее число способов будет 2 4 4 32 6 35960 215 760 C C ? = ? = Можно обобщить вопрос, заданный в условии приведенной задачи, и найти количество способов, при которых среди выбранных шести карт окажется 0, 1, 2, 3, 4 туза: Кол-во тузов Число способов 0 0 6 4 32 906192 C C Ч = 1 1 5 4 32 805 504 C C Ч = 2 2 4 4 32 215 760 C C Ч = 3 3 3 4 32 19 840 C C Ч = 4 4 2 4 32 496 C C Ч = Не всегда в задачах, где следует применять формулу для подсчета сочетаний, в явном виде присутствует выбор из n по k. Иногда этот вы- бор скрыт в тексте, и его нужно еще увидеть. Пример 6. Сколькими способами можно расположить в один ряд 3 белых и 4 черных шара? Чтобы было понятно, о каких комбинациях идет речь, выпишем несколько из них, обозначая белые шары буквой Б, черные — буквой Ч: БББЧЧЧЧ, ББЧБЧЧЧ, ББЧЧБЧЧ, … Если считать, что Б < Ч, то эти комбинации выписаны в лексиког- рафическом порядке. Нужно сказать, что полученные комбинации не совпадают ни с од- ним из рассмотренных ранее типов (перестановка, размещение, сочета- ние), но для их подсчета наших знаний вполне достаточно. Каждая ком- бинация состоит из семи букв и однозначно определяется выбором тех трех из семи мест, на которых будут стоять буквы Б. Выбрать три места из семи можно 3 7 7! 35 4!3! C = = способами — это и есть искомое количе- ство комбинаций. Комбинаторика и вероятность 48 Задачу можно решать и по-другому, выбирая те четыре из семи мест, на которых будут стоять буквы Ч: 4 7 7! 35 3! 3! C = = ? . Разумеется, ответ тот же самый. Кроме того, мы обнаружили одно интересное свойство числа сочетаний: k n k n n C C ? = Это свойство сразу следует из формулы для числа сочетаний — фор- мула симметрична относительно k и (n – k). Но обосновать это равен- ство можно чисто комбинаторным способом: выбор тех k элементов из n, которые мы собираемся включить в комбинацию, равносилен выбору тех (n – k) элементов, которые мы собираемся оставить. Найденное замечательное свойство числа сочетаний далеко не един- ственное. В следующем пункте мы поговорим об этих свойствах под- робнее. 4. Комбинаторика при вычислении вероятностей Перейдем теперь к использованию полученных сведений из комби- наторики для решения вероятностных задач. Сначала зададимся вопро- сом, какая вообще может быть связь между комбинаторикой, где все жестко определено и детерминировано, и теорией вероятностей, изучаю- щей случайные явления? В первой лекции, обсуждая понятие вероятно- сти, мы выяснили, что существует довольно широкий круг случайных опытов, в которых вероятность любого события можно вычислить a priory — без проведения экспериментов — по формуле классиче- ской вероятности ( ) m P A n = , где n — количество всех исходов опыта, а m — количество исходов, благоприятных для события A. Это так называемые опыты с равновоз- можными исходами. Рассматривая примеры таких опытов, мы специально выбирали их до- статочно простыми, чтобы при подсчете числа возможных и благоприят- ных исходов можно было провести этот подсчет простым перечислением всех вариантов. Однако зачастую количество исходов опыта настолько Лекция 2 49 велико, что перечислить все такие исходы не представляется возможным. Вот здесь и приходят на помощь комбинаторные правила и формулы, рас- смотренные выше. Чаще всего это происходит в опытах, где либо уча- ствует много объектов (монет, кубиков, шаров и т.д.), либо с одним и тем же объектом производят многократные действия (монету или кубик бро- сают несколько раз, несколько раз участвуют в лотерее и т.д.). Еще раз подчеркнем, что для использования комбинаторных методов пригодны только те задачи, в основе которых лежат опыты с равновоз- можными исходами — иначе подсчет количества таких исходов ничего не дает для вычисления вероятности. Начнем с примеров, уже разобран- ных в предыдущих разделах. Только теперь в каждом из них создадим вероятностную ситуацию. Пример 1 (см. пример 1.5). Шесть школьников случайным образом рассаживаются на скамейку. С какой вероятностью Коля и Оля будут сидеть рядом? Фразу «рассаживаются случайным образом» нужно понимать так, что все возможные варианты рассаживания равновозможны. Каждый такой вариант — это перестановка из 6 элементов, значит, всего воз- можных исходов у этого опыта будет 6 6! n P = = Исходы, благоприятные для события «Коля и Оля будут сидеть ря- дом» мы уже считали ранее — их получилось 240 m = . Отсюда находим вероятность: 240 1 ( ) 6! 3 m P A n = = = . Пример 2 (см. пример 3.2). В классе, в котором учится 25 учеников, |