сколькими способами можно расставить на полке 6 различных книг

Первую книгу мы можем поставить на любое из 6 мест, это уже 6 способов.
Когда мы захотим поставить вторую книгу, одно из мест будет уже занято, поэтому вторую книгу мы сможем поставить только 5 способами.

Получается что первые две книги мы можем расставить 6*5=30 способами.

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

Тогда первые три книги мы можем расположить 6*5*4=120 спомобами.

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

Тогда первые четыре книги мы сможем расположить 6*5*4*3=360 способами.

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

Тогда первые пять книг мы можем зазместить 6*5*4*3*2=720 способами.

Когда мы захотим разместить шестую книгу, то сводобным останеться только одно место, и последнюю книгу мы сможем разместить только одним единственным образом.

Поэтому все шесть книг мы можем разместить 6*5*4*3*2*1=720 способами.

Источник

Введение в комбинаторику и теорию вероятностей

Разделы: Математика

Пояснительная записка

Давно уже стало очевидным универсальность вероятностно-статистических законов, они стали основой описания научной картины мира. Современная физика, химия, биология, демография, социология, весь комплекс социально-экономических наук развиваются на вероятностно-статистической базе. В нашу жизнь вошли выборы и референдумы, банковские кредиты и страховые полисы, таблицы занятости и диаграммы социологических опросов. Круг вопросов, связанных с осознанием соотношений понятий вероятности и достоверности, проблемой выбора наилучшего из нескольких вариантов решения, оценкой степени риска и шансов на успех – всё это находится в сфере реальных интересов становления личности.

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

Цели и задачи

— введение в комбинаторику, знакомство с основными понятиями: перестановки, размещения, сочетания;

— введение в теорию вероятностей (частота и вероятность, сложение и умножение вероятностей);

— коррекция базовых математических знаний, систематизация, расширение и углубление знаний;

— развитие познавательных интересов и творческих способностей учащихся, психических способностей ребенка, обеспечивающих его адаптацию в дальнейшей жизни, научить школьников учиться посредствам личностно-ориентированного подхода;

— воспитание творческой личности, умеющей самореализовываться и интегрироваться в системе мировой математической культуры;

— акцентировать внимание учащихся на единых требованиях к правилам оформления различных видов заданий, включаемых в итоговую аттестацию за курс полной общеобразовательной средней школы;

— развивать способности учащихся к математической деятельности;

— способствовать совершенствованию и развитию важнейших математических знаний и умений, предусмотренных программой.

Урок 1. “Престановки”

Цели урока:

— познакомить с понятием “комбинаторика”, привести примеры комбинаторных задач;

— ввести (повторить) понятие “факториал”;

— дать определение понятия “перестановка”;

— доказать равенство Рn=n!;

— решать задачи на перестановки.

Ход урока

1) Что такое комбинаторика, решение комбинаторных задач, исторические комбинаторные задачи.

В науке и практике часто встречаются задачи, решая которые приходиться составлять различные комбинации из конечного числа элементов и подсчитывать число этих комбинаций. Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются эти задачи, называют комбинаторикой. Слово “комбинаторика” происходит от латинского слова combinare – “соединять, сочетать”.

Определение. Комбинаторика – это раздел математики, посвящённый задачам выбора и расположения предметов из различных множеств.

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

Пример 1. Дано три элемента a, b и c. Сколькими способами можно расставить эти элементы друг за другом?

Решение: abc, acb, bac, bca, cab, cba. Всего 6 различных способов.

Пример 2. Сколько трёхзначных чисел можно составить из цифр 1, 3, 5, 7, используя в записи числа каждую цифру не более одного раза?

Итого 24 числа: 135, 137, 153, 157, 173, 175, 315, 317, 351, 357, 371, 375, 513, 517, 531, 537, 571, 573, 713, 715, 731, 735, 751, 753. Такой способ решения называют деревом возможных вариантов.

Некоторые комбинаторные задачи решали ещё в Древнем Китае, а позднее – в Римской империи. Как самостоятельный раздел математики комбинаторика оформилась в Европе в XVIII веке в связи с развитием теории вероятностей.

Все составные числа древние математики представляли в идее прямоугольников размером m x n, выложенных из камней, где обязательно m 1 и n 1. Простые числа представляли в виде линий 1 х n. В связи с этим составные числа древние учёные называли прямоугольными, а простые – непрямоугольными числами.

Определение. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Обозначение n!

Для того, чтобы в различных формулах не делать исключения для числа 0, принято соглашение: 0! = 1.

Таблица факториалов от 0 до 10:

В примерах 1 и 2 мы составляли различные комбинации элементов и чисел, переставляя их различными способами.

Определение. Перестановкой называется конечное множество, в котором установлен порядок элементов.

В приведённых примерах различных перестановок относительно не много. Но возможны другие задачи, в которых количество перестановок достаточно большое. Выписывать их неудобно, это занимает достаточно много времени и вероятность “потерять” какое-нибудь решение велика.

Число всевозможных перестановок из n элементов вычисляется по формуле:

Если n = 1, то P_n = 1! = 1 – верно.

Докажем, что P_k+1 = (k + 1)! – тоже верно:

Мы имеем k + 1 элемент. На первое место можно поставить любой из них. Для каждого выбора первого элемента на второе место можно поставить один из оставшихся k элементов. Для каждого выбора первых двух элементов на третье место можно поставить один из оставшихся k – 1 элементов и т.д. В результате получим, что

4) Примеры решения задач.

Пример 1. Сколькими способами могут быть расставлены восемь участниц финального забега на восьми беговых дорожках?

Значит, существует 40 320 способов расстановки восьми участниц на восьми беговых дорожках. (Понятно, что решить эту задачу методом построения дерева возможных вариантов практически невозможно.)

Ответ: 40 320 способов.

Пример 2. Сколько различных четырёхзначных чисел можно составить из цифр 0, 1, 2, 3, причём в каждом числе цифры должны быть разные?

Решение: Количество четырёхзначных чисел, которые можно составить из 4-х различных цифр (без повторения цифр) равно числу перестановок из четырёх элементов P₄. Но в этом случае будут образовываться числа, начинающиеся с 0, что невозможно. И таких перестановок будет P₃. Следовательно, Р₄ – Р₃ = 4! – 3! = 18.

Пример 3. Имеется 10 различных книг, среди которых есть трёхтомник одного автора. Сколькими способами можно расставить эти книги на полке, если книги трёхтомника должны находиться вместе, но в любом прядке?

Решение: Будем считать трёхтомник одной книгой (т.к. порядок книг в самом трёхтомнике возможен любой). Тогда у нас всего не 10 книг, а 8. Их можно расставить Р₈ способами. Но книги в трёхтомнике можно расставить Р₃ способами. Для каждой перестановки из 8-и элементов соответствует определённая перестановка из 3-х элементов. Следовательно, .

Ответ: 241 920 способов.

5) Задачи для самостоятельного решения (в классе и дома).

1). Сколькими различными способами могут сесть на скамейку

Ответ: а) 120 способов; б) 5 040 способов.

2). Сколько различных трехцветных флагов с тремя горизонтальными полосами можно получить, используя красный, синий и белый цвета?

3). Сколькими способами можно расставить по этапам четырёх участниц эстафеты в беге 4 х 100 м?

4). Составьте всевозможные трёхзначные числа, в которых все цифры разные, используя лишь цифры:

а) Р₃ = 3! = 6 – всего 6 чисел: 751, 715, 571, 517, 175, 157.

б) Р₃ – Р₂ = 3! – 2! = 4 – всего 4 числа: 209, 290, 902, 920.

5). Сколько четырёхзначных чисел можно составить из цифр 1, 2, 5, 7, если каждая цифра может использоваться только один раз?

6). Учащиеся должны посетить во вторник по расписанию 5 уроков по следующим предметам: литература, алгебра, география, физкультура и биология. Сколькими способами можно составить расписание на этот день, чтобы физкультура была пятым уроком?

7). Из цифр 2, 3, 4, 7 составлены всевозможные четырёхзначные числа (без повторения цифр). Сколько среди этих чисел таких, которые:

а) начинаются с цифры 7;

б) не начинаются с цифры 4?

Ответ: а) 6 чисел; б) 18 чисел.

8). Из цифр 1, 2, 0, 5, 6 составлены всевозможные пятизначные числа (без повторения цифр). Сколько среди этих чисел таких, которые:

Решение: а) признак делимости на 4: если две последние цифры числа делятся на 4, то и всё число делится на 4. Следовательно, кратны 4 будут числа ***12, ***16, ***20, ***56. Количество чисел, оканчивающихся на 12, 16 и 56: Р₃ – Р₂ = 3! – 2! = 4 (т.к. 0 не может стоять на первом месте). Количество чисел, оканчивающихся на 20: Р₃ = 3! = 6. Следовательно, .

б) Кратны 5 будут числа ****0: Р₄ = 4! = 24 и ****5: Р₄ – Р₃ = 4! – 3! = 18. Следовательно, 24 + 18 = 42.

Ответ: а) 18 чисел; б) 42 числа.

9). В автомашине 5 мест. Сколькими способами в этой автомашине могут разместиться 5 человек, если место водителя могут занять только двое из них?

10). Чтобы открыть сейф, нужно набрать шифр, содержащий определённую последовательность из цифр 1, 2, 3, 4, 5, 6, и другой шифр, содержащий последовательность из букв a, b, c, d, в которых буквы и цифры не повторяются. Сколько существует комбинаций, при которых сейф НЕ открывается?

Решение: (все возможные варианты минус один вариант, с помощью которого сейф можно открыть).

Ответ: 17 279 комбинаций.

11). Сколькими способами можно расставить на полке четыре книги по алгебре и три по геометрии, причём так, чтобы все книги по алгебре (в любом порядке) стояли рядом?

Решение: .

Ответ: 576 способов.

12). Найдите сумму всех трёхзначных чисел, которые можно составить из цифр 2, 4, 6, не повторяя цифр.

Решение: Р₃ = 3! = 6 – всего 6 чисел.

246 + 264 + 426 + 462 + 624 + 642 = 2 664.

13). Число a = n! + 1, где , является квадратом натурального числа. Найдите наименьшее значение a, если:

а) a – двузначное число;

б) a – трёхзначное число.

Решение: а) a = 25 при n = 4; б) a = 121 при n = 5.

Источник

КОМБИНАТОРИКА РАЗБИЕНИЙ. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ.

КОМБИНАТОРИКА РАЗБИЕНИЙ. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Поскольку в данной формулировке полки не различимы, то речь идет о неупорядоченном разбиении множества книг на три подмножества мощности 2, 3 и 3. Параметры m ₁ = 1, m ₂ = 2, поэтому число разных способов расставить книги так, как это требуется в условии задачи, равно

Приведенные выше примеры показывают, как важно для решения задачи выбрать наиболее подходящую комбинаторную схему, правильно определить, какие именно комбинаторные операции требуется выполнить над исходным множеством. Иногда формулировка задачи допускает неоднозначное понимание того, какие результаты комбинаторной операции считаются одинаковыми, а какие – разными. В таких случаях нужно самостоятельно сделать необходимые уточнения.[24]

Задача 5.2. одинаковых шариков случайным образом рассыпаются по 4 лункам (в одну лунку может поместиться любое число шаров). Сколько существует различных способов распределения 7 шариков по 4 лункам?[11]

Задача 5.3. Стадион имеет 4 входа. Сколькими способами болельщик может войти на стадион в один вход, а выйти через другой?[12]

Решение. Воспользуемся формулой о разбиениях (3), число способов равно = 12.

Задача 5.4. При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать? [11]

Решение. Это задача о разделе 28 костей между 4 игроками по 7 костей.

Используя формулу для числа способов такого раздела (3)

Задача 5.5. Сколькими способами можно разместить 4 книги на полке?[16]

Задача 5.6. Сколькими способами можно поставить в ряд 6 человек для выполнения их группового портрета? Сколькими способами можно это сделать, если поставить трех человек в переднем ряду и трех во втором?[12]

Задача 5.7. Сколько различных «слов» можно составить, переставляя буквы слова «лодка»?[12]

Задача 5.8. Сколько различных «слов» можно составить, переставляя буквы слова «математика»?[20]

Решение. Слово «математика» состоит из 10 повторяющихся букв: 3 буквы «а», 2 буквы «м», 2 буквы «т». Значит можно воспользоваться формулой (3), число различных «слов» будет = = 151200.

Задача 5.9. Сколько различных слов можно составить, переставляя буквы слова «комбинаторика»?[11]

Решение. Слово «комбинаторика» состоит из 13 повторяющихся букв: 2 буквы «к», 2 буквы «о», 2 буквы «и», 2 буквы «а». Значит можно воспользоваться формулой (3), число различных «слов» будет = = 389188800.

Задача 5.10. В классе изучают 10 предметов. В понедельник 6 уроков, причем все уроки разные. Сколькими способами можно составить расписание на понедельник?[13]

Задача 5.11. Сколькими способами можно выбрать трех делегатов на студенческую конференцию из группы в 20 человек?[21]

Задача 5.12. Сколькими способами можно расставить 40 различных книг по шести полкам так, чтобы не было пустых полок, если на полку помещаются все 40 книг?

Задача 5.13. Рассеянный почтальон должен разнести
12 писем по 12 адресам. Сколькими способами он может разложить письма по почтовым ящикам так, чтобы

а) ни один адресат не получил адресованное ему письмо;

б) ровно 5 человек получили адресованные им письма;

в) хоть один адресат получил адресованное ему письмо;

г) ровно один адресат получил адресованное ему письмо?

г) Очевидно, что такой ситуации быть не может.

Задача 5.15. Контрольную работу по дискретной математике, содержащую три задачи, писали 105 студентов III курса. Первую задачу решили 70 человек, вторую – 59, а третью – 62. С первой и второй задачами справились – 39 студентов, со второй и третьей – 32, с первой и третьей – 41. Шесть человек не решили ни одной задачи. Сколько студентов полностью справились с контрольной работой?

Задача 5.16. Имеются цветы трех видов: 10 васильков, 15 незабудок, 12 ромашек. Требуется разложить их на 2 букета.[11]

Задача 5.17. Из группы в 15 человек нужно отобрать бригаду, в которую должно входить не менее 5 человек. Сколько имеется вариантов выбора?

Решение. Подсчитаем число неблагоприятных комбинаций выбора, т. е. со ставим варианты бригад из 1, 2, 3, 4 человек. Их количество равно:

А общее количество бригад равно 2 15 – 1. Разность дает число благо приятных комбинаций.[17]

Задача 5.18. Трое мальчиков собрали 40 яблок. Сколько имеется способов раздела яблок между ними?

Решение. Напишем 40 единиц и 2 нуля, выполняющих как и ранее функции раз делителя, и затем начнем их переставлять всеми возможными спосо бами. Каждой перестановке будет соответствовать некоторый способ раздела 40 яблок на 3 кучки. Каждому способу раздела будет соответствовать некоторый код, содержащий 40 единиц и 2 нуля. Поэтому коли чество способов раздела:

Задача 5.19. В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

Решение: В задаче речь идёт о выборке из 4 деталей, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:

2365 способами можно взять 4 детали из ящика.

Ответ: 1365 способами

В данном примере множество из восьми книг разбивается на три непересекающихся подмножества мощности 1, 3 и 4. Согласно формуле (3) количество различных вариантов выполнить такое разбиение равно

Источник

Алгебра

Именная карта банка для детей
с крутым дизайном, +200 бонусов

Закажи свою собственную карту банка и получи бонусы

План урока:

Комбинаторика и ее основные принципы

Очень часто приходится решать задачи, в которых надо посчитать количество возможных вариантов для той или иной ситуации. Например, сколько позиций может возникнуть на шахматной доске после первого хода обоих игроков? Сколько разных паролей длиною в десять символов можно записать, если ни один символ не использовать дважды? Сколько разнообразных комбинаций чисел может выпасть при игре в лотерею «6 из 49»? На все эти вопросы помогает ответить специальный раздел математики, называемый комбинаторикой. Почти всегда комбинаторную задачу можно сформулировать так, чтобы ее вопрос начинался словами «сколькими способами…».

Очевидно, что если в конечном множестве содержится n элементов, то есть ровно n способов выбрать один из них.

Пример. В классе 15 человек. Сколькими способами учитель может назначить одного из них ответственным за чистоту доски?

Ответ. Таких способов ровно 15.

В комбинаторике существует два основных правила. Первое из них называется правилом сложения.

Несмотря на формулировку, по сути это очень простое правило.

Пример. В магазине продается 14 телевизоров Panasonic и 17 телевизоров Sony. Петя хочет купить один телевизор. Сколько у него вариантов покупки?

Решение. По правилу сложения Петя может выбрать один из 14 + 17 = 31 телевизоров.

Ответ: 31 телевизор.

Особое значение имеет второе правило, которое называют правилом умножения.

Проиллюстрируем это правило.

Пример. В секции бадминтона 15 мальчиков и 20 девочек. Тренер должен отправить на соревнования смешанную пару. Сколько вариантов действий у него?

Решение. Тренер может составить 15•20= 300 разнополых пар из своих воспитанников.

Пример. Пете нужно купить технику для компьютера. В магазине продается 20 различных клавиатур, 25 моделей геймпадов и 30 компьютерных мышей. Купить надо по одному экземпляру каждого из этих устройств. Сколько вариантов покупки есть у него?

Решение. Сначала подсчитаем число возможных пар «клавиатура-геймпад». Их количество равно 20•25 = 500. Теперь составим «тройку» из одной из 500 пар и одной из 30 мышей. Число троек равно 500•30 = 15000.

Правила сложения и умножения можно комбинировать.

Пример. Сколько слов не более чем из трех букв можно составить, используя алфавит, содержащий ровно 30 букв?

Решение. Очевидно, что слов из одной буквы можно составить ровно 30. Количество двухбуквенных слов равно количеству пар, которые можно составить из этих букв, то есть 30•30 = 900. Трехбуквенных слов можно составить 30•30•30 = 27000. Всего же слов длиною не более 3 букв будет

30 + 900 + 27000 = 27930

Далее мы изучим основные понятия комбинаторики – перестановки, размещения, сочетания.

Перестановки

Рассмотрим простейшую комбинаторную задачу. На полке расставляют по порядку книги. Их ставят вертикально друг за другом. Сколькими способами можно расставить на полке 2 книги? Очевидно, что двумя:

Либо синяя книжка будет первой слева, либо она будет находиться в конце полки, третьего варианта здесь нет. Здесь условно считается, что варианты, когда между книгами есть зазоры, идентичны вариантам без зазоров:

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

Например, если в забеге на 100 метров стартует 8 спортсменов, то они образуют множество участников забега. После финиша становится известно, кто занял 1-ое место, кто оказался вторым или третьим, а кто стал последним. Результат забега будет перестановкой, ведь он представляет собой список спортсменов с указанием их мест, то есть он определяет порядок между ними.

Вернемся к примеру с книгами. Обозначим количество возможных перестановок n элементов как Р_n. Две книжки можно расставить двумя разными способами, поэтому Р₂ = 2. Обозначим эти перестановки как АБ и БА. Сколько способов расстановки есть в случае трех книжек? Их все можно получить из вариантов с 2 книжками, добавляя между ними книгами ещё один том:

Видно, что между 2 книгами есть три позиции, на которые можно поставить 3-ий том. Общее количество вариантов равно произведению числа этих позиций и количества вариантов для 2 книг, то есть Р₃ = 3•Р₂ = 3•2 = 6:

Итак, мы имеем 6 перестановок для 3 книг:

А сколько перестановок существует для 4 книг? Снова-таки, между тремя книгами 4-ый том можно поставить четырьмя способами:

То есть из перестановки трех книг АБВ можно получить 4 перестановки:

Всего существует 6 перестановок для 3 книг (Р₃ = 6), и для каждой из них можно построить 4 перестановки из 4 книг. Получается, что общее количество перестановок 4 книг равно

Продолжая подобные рассуждения, можно убедиться, что количество перестановок 5 предметов в 5 раз больше, чем перестановок для 4 объектов:

И вообще, если число перестановок n объектов равно Р_n, то количество перестановок (n + 1)объекта равно в (n + 1)раз больше:

При этом отметим, что 1 книгу можно расставить на полке только одним способом:

То есть Р₁ = 1. Теперь выпишем значения чисел Р при разном количестве переставляемых предметов, используя формулуР_n+1 = (n + 1)Р_n

Видно, что количество перестановок n объектов равно произведению всех натуральных чисел от 1 до n. В математике есть специальная функция для вычисления значения этого произведения. Она называется факториалом и обозначается восклицательным знаком.

Например, факториал 6 вычисляется так:

Мы убедились на примере с книгами, что количество перестановок из n различных объектов, которое обозначается как Р_n, равно n!.

Относительно факториала надо заметить несколько важных моментов. Во-первых, очевидно, что факториал единицы равен 1:

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

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

5! = 1•2•3•4•5 = (1•2•3•4)•5 = 4!•5

7! = 1•2•3•4•5•6•7 = (1•2•3•4•5•6)•7 = 6!•7

В общем случае формула выглядит так:

Из неё несложно получить, что

Подставив в эту формулу единицу, получим

Пример. Сколькими способами тренер может расставить 4 участников эстафеты 4х400 м по этапам эстафеты?

Решение. Количество таких способов равно числу перестановок 4 различных объектов Р₄:

Пример. Вася решил изучать сразу 7 иностранных языков, причем на занятия по каждому из них он собирается выделить ровно один день в неделе. Сколько вариантов расписаний занятий может составить себе Вася?

Решение. В данном случае расписание занятий – это порядок, в котором Вася в течение недели будет изучать иностранные языки, например:

Такое расписание можно описать последовательностью символов:

Создавая расписание, Вася переставляет 7 языков, поэтому общее количество расписаний равно 7!:

Пример. Сколько пятизначных цифр можно записать, используя цифры 0, 1, 2, 3, 4, причем каждую не более одного раза?

Решение. Общее количество перестановок 5 цифр составляет Р₅. Однако нельзя начинать запись числа с нуля. Так как, перестановка 12340 – это пятизначное число (двенадцать тысяч триста сорок), а перестановка 03241 – не является пятизначным числом.

Расстановок, начинающихся с нуля, ровно Р₄, поэтому общее количество допустимых цифр равно Р₅ – Р₄:

Р₅ – Р₄ = 5! – 4! = 120 – 24 = 96

Пример. На полке расставляют 7 книг, однако 3 из них образуют трехтомник. Тома трехтомника должны стоять друг за другом и в определенном порядке. Сколько существует способов расстановки книг?

Решение. Будем считать трехтомник одной книгой. Тогда нам надо расставить 5 книг

Пример. Необходимо расставить 7 книг на полке, но три из них принадлежат одному автору. Их надо поставить друг с другом, но они могут стоять в любом порядке. Сколько возможно перестановок книг.

Решение. Снова будем считать три книги как один трехтомник. Получается, что существует 5! = 120 вариантов. Однако каждому из них соответствует 3! = 6 расстановок книг внутри трехтомника, например:

В итоге на каждую из 120 расстановок приходится 6 вариантов расстановки трехтомника, а общее число расстановок равно, согласно правилу умножения, произведению этих чисел:

Перестановки с повторениями

До этого мы рассматривали случаи, когда все переставляемые объекты были различными. Однако порою некоторые из них не отличаются друг от друга. Пусть на полке надо расставить 3 книги, но две из них одинаковые. Сколько тогда существует перестановок? Общее число перестановок 3 книг составляет 3! = 6:

Здесь одинаковые книги отмечены как А и А1. Очевидно, что 1-ый и 2-ой варианты (А1АБ) и (АА1Б) на самом деле не отличаются друг от друга. В них отличается лишь порядок одинаковых книг А и А1. В первом случае за А1 следует А, а во втором, наоборот, за А следует А1. Тоже самое можно сказать про варианты 3 и 4, 5 и 6. Получается, что все возможные перестановки можно разбить на группы, в которых находятся «перестановки-дубликаты»:

В каждой группе находится ровно по два «дубликата». Почему именно по два? Это число равно количеству перестановок одинаковых книг. Так как одинаковых томов 2, а Р₂ = 2, то в каждой группе по 2 «дубликата». Действительно, если бы мы «убрали» с полки все книги, кроме повторяющихся, то там осталось бы только 2 одинаковых тома, которые можно переставить двумя способами.

Для того чтобы найти количество «оригинальных» перестановок, надо их общее количество поделить на число дубликатов в каждой группе.

Пусть теперь надо расставить 4 книги, из которых 3 одинаковы. Обозначим тома как А, А1, А2 и Б. Всего можно записать 4! = 24 перестановки. Однако каждые 6 из них будут дублировать друг друга. То есть их можно разбить на группы, в каждой из которых будет 6 идентичных «дубликатов»:

1-ая группа: БАА1А2, БАА2А1, БА1АА2, БА1А2А, БА2АА1, БА2А1А

2-ая группа: АБА1А2, АБА2А1, А1БАА2, А1БА2А, А2БАА1, А2БА1А

3-ая группа: АА1БА2, АА2БА1, А1АБА2, А1А2БА, А2АБА1, А2А1БА

4-ая группа: АА1А2Б, АА2А1Б, А1АА2Б, А1А2АБ, А2АА1Б, А2А1АБ

И снова для подсчета числа оригинальных перестановок надо из общее число расстановок поделить на количество дубликатов в каждой группе:

Для обозначения перестановок с повторениями используется запись

где n – общее количество объектов, а n₁, n₂, n₃,… n_k – количество одинаковых элементов. Например, в задаче с 4 книгами мы искали величину Р₄(3, 1), потому что всего книг было 4, но они были разбиты на две группы, в одной из которых находилось 3 одинаковых тома (буквы А, А1, А2), а ещё одна книга (Б) составляла вторую группу. Мы заметили, что для вычисления числа перестановок с повторениями надо общее число перестановок делить на количество дублирующих перестановок. Формула в общем случае выглядит так:

Пример. Вася решил, что ему стоит изучать только два иностранных языка. Он решил 4 дня в неделю тратить на английский, а оставшиеся три дня – на испанский. Сколько расписаний занятий он может себе составить.

Решение. Вася должен расставить 3 урока испанского и 4 урока английского, тогда n₁ = 3, а n₂ = 4. Общее количество уроков равно 3 + 4 = 7. Тогда

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

Пример. У мамы есть 3 яблока, 2 банана и 1 апельсин. Эти фрукты она распределяет между 6 детьми. Сколькими способами она может это сделать, если каждый должен получить по фрукту?

Решение. Всего есть три группы фруктов. В первой находится 3 яблока, поэтому n₁ = 3. Во второй группе 2 банана, поэтому n₂ = 2. В третьей группе только 1 апельсин, поэтому n_k = 1. Общее число фруктов равно 6. Используем формулу:

В знаменателе формулы для перестановок с повторениями мы записываем число объектов в каждой группе одинаковых предметов. Так, если переставляются 3 яблока, 2 банана и 1 апельсин, то в знаменателе мы пишем 3!•2!•1!. Но что будет, если в каждой группе будет находиться ровно один уникальный объект? Тогда мы запишем в знаменателе произведение единиц:

В итоге мы получили ту же формулу, что и для перестановок без повторов. Другими словами, перестановки без повтора могут рассматриваться просто как частный случай перестановок с повторами.

Размещения

Пусть в футбольном турнире участвуют 6 команд. Нам предлагают угадать те команды, которые займут призовые места (то есть первые три места). Сколько вариантов таких троек существует?

Сначала запишем ту команду, которая выиграет турнир. Здесь есть шесть вариантов, по количеству участвующих команд. Запишем эти варианты:

Далее выберем один из вариантов и для него укажем серебряного призера соревнований. Здесь есть только 5 вариантов, ведь 1 из 6 команд уже записана на 1-ом месте:

Такую пятерку можно записать для каждого из шести вариантов того, кто станет чемпионом. Получается, что всего есть 6•5 = 30 пар «чемпион – серебряный призер». Наконец, для одной такой пары можно записать 4 варианта того, кто окажется третьим (две команды писать нельзя, так как они уже записаны на первых двух строчках):

Для каждой пары можно записать 4 тройки призеров. Так как число пар «чемпион – вице-чемпион» равно 6•5 = 30, то число троек составит 6•5•4 = 120.

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

Если общее число команд обозначить как n (в этом примере n = 6), а количество упорядочиваемых команд равно k, то количество таких размещений в комбинаторике обозначается как

В примере с командами количество размещений равнялось 120:

Читается эта запись как «число размещений из 6 по 3 равно 120».

Для нахождения этого числа мы перемножили k (3)множителей. Первый из них был равен n(6), так как каждая из n команд могла занять первая место. Второй множитель был равен (n– 1), так как после определения чемпиона мы могли поставить на вторую позицию одну из (n– 1) команд. Третий множитель был равен (n– 2). По этой логике каждый следующий множитель будет меньше предыдущего на единицу. Например, чтобы вычислить число размещений из 7 по 4, надо перемножить 4 множителя, первый из которых равен 7, а каждый следующий меньше на 1:

Однако математически удобнее представлять это произведение как отношение двух факториалов. Для этого умножим количество размещений на дробь 3!/3!, равную единице. Естественно, число размещений из-за умножения на единицу не меняется:

Число 3 в данном случае можно получить, если из 7 вычесть 4. В общем случае из числа n надо вычесть число k. Тогда формула для вычисления количества размещений примет вид:

Пример. В программе 8 «А» класса 12 различных предметов. В понедельник проводится 5 занятий подряд. Сколько существует вариантов расписаний для класса, если в течение понедельника нельзя проводить два одинаковых урока?

Решение. Для составления расписания нужно выбрать 5 предметов и расставить их по порядку. Поэтому нам необходимо найти размещение из 12 по 5:

Пример. В вагоне 10 свободных мест. В него зашло 6 пассажиров. Сколькими способами они могут расположиться в вагоне?

Решение. Из десяти мест надо выбрать шесть и указать для каждого, какому пассажиру оно соответствует. То есть каждый вариант рассадки пассажиров – это размещение из 10 по 6. Найдем их количество:

Заметим, что перестановка – это частный случай размещения, когда k = n. Действительно, если нам надо указать тройку призеров турнира, в котором участвуют 6 команд, то мы указываем размещение из 6 по 3. Но если мы указываем для каждой из 6 команд, какое место она займет в чемпионате, то это размещение из 6 по 6. С другой стороны, это расстановка одновременно является и перестановкой 6 команд. Убедимся, что в этом частном случае формула для подсчета количества размещений покажет тот же результат, что и формула для перестановок

Для примера с 6 командами это будет выглядеть так:

Здесь мы использовали тот факт, что факториал нуля принимается равным единице. Данное рассуждение можно, наоборот, использовать для того, чтобы доказать, что факториал нуля – это единица.

Сочетания

Выбирая размещение, мы должны были выбрать из множества несколько объектов и упорядочить их. В частности, мы выбирали три команды из шести и указывали, какая из них будет первой, какая второй, а какая третьей. Поэтому размещения «Локомотив, Зенит, Краснодар» и «Локомотив, Краснодар, Зенит» отличались друг от друга.

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

Количество возможных сочетаний из n по k обозначается буквой С:

Для вычисления количеств сочетаний из n по k сначала найдем количество аналогичных размещений. Оно вычисляется по формуле:

Однако все они соответствуют только одному сочетании – ЛКЗ. Таким образом, считая количество размещений, мы посчитали каждое сочетание не один, а 3! раз. Поэтому для нахождения количества сочетаний в комбинаторике надо поделить число размещений на число перестановок k элементов:

Эта формула связывает важнейшие понятия комбинаторики – перестановки, сочетания и размещения. Подставим в неё формулы для размещений и перестановок и получим:

Пример. Сколько троек призеров турнира можно составить, выбирая три футбольные команды из шести?

Решение. Посчитаем число сочетаний из 6 по 3:

Пример. Сколько комбинаций чисел может составить игрок, играющий в лотереи «5 из 36», «6 из 45», «7 из 49»?

Решение. В каждом из этих случаев игрок выбирает сочетание нескольких чисел. Посчитаем их число:

Ответ: 376992; 8145060; 85900584

Пример. На плоскости отмечены 8 точек, причем никакие три из них не лежат на одной прямой. Сколько различных прямых можно провести через них? Сколько треугольников и четырехугольников можно построить с вершинами в этих точках?

Решение. Для того чтобы провести прямую, достаточно выбрать любые 2 точки из 8. Общее количество прямых будет равно числу сочетаний из 8 по 2:

Заметим принципиальную важность того условия, что никакие три точки не лежат на одной прямой. Оно гарантирует, что при выборе двух различных точек мы будем получать различные прямые. Если бы, например, точки АВС лежали бы на одной прямой, то при выборе сочетаний АВ, ВС и АС мы получали бы одну и ту же прямую:

Это же условие гарантирует, что, выбрав любые 3 и 8 точек, мы сможем построить треугольник с вершинами в этих точках, а выбрав 4 точки, получим четырехугольник. Поэтому для подсчета количества треугольников и четырехугольников следует искать число сочетаний по 3 и 4:

Ответ: 28 прямых, 56 треугольников и 70 четырехугольников.

Пример. В одной урне находится 10 различных шаров с номерами от 0 до 9, а в другой – 8 различных шаров с первыми восемью буквами алфавита. По условиям лотереи ведущий вытаскивает из первой урны два шара с числами, а из второй – три шара с буквами. Для победы в лотерее надо угадать выпавшие шары. Сколько комбинаций шаров может выпасть в игре?

Решение. Посчитаем отдельно, сколькими способами можно выбрать 2 шара с цифрами из 10 и 3 шара с буквами из 8:

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

Заметим, что выбирая, например, сочетание из 49 по 7, мы одновременно выбираем и сочетание из 49 по 49 – 7 = 42. Действительно, игрок, обводящий в кружок в лотерейном билете свои 7 счастливых чисел, одновременно и определяет остальные 42 числа, какие числа он НЕ считает счастливыми. Для наглядности запишем число сочетаний в обоих случаях:

Получили одну и ту же дробь, в которой отличается лишь последовательность множителей в знаменателе. Можно показать, что и в общем случае число сочетаний из n по k совпадает с количеством сочетаний из n по (n– k):

Источник

• ← alex andreev биография певец
• какое море рядом с англией →