Сколькими способами можно поставить на полке 4 различные вазы
Добавил пользователь Алексей Ф. Обновлено: 05.10.2024
Введение в комбинаторику и теорию вероятностей
Давно уже стало очевидным универсальность вероятностно-статистических законов, они стали основой описания научной картины мира. Современная физика, химия, биология, демография, социология, весь комплекс социально-экономических наук развиваются на вероятностно-статистической базе. В нашу жизнь вошли выборы и референдумы, банковские кредиты и страховые полисы, таблицы занятости и диаграммы социологических опросов. Круг вопросов, связанных с осознанием соотношений понятий вероятности и достоверности, проблемой выбора наилучшего из нескольких вариантов решения, оценкой степени риска и шансов на успех – всё это находится в сфере реальных интересов становления личности.
Подготовку человека к таким проблемам осуществляет школьный курс математики. Все перспективные государственные образовательные документы содержат вероятностно-статистическую линию в курсе математики. Теория сочетаний представляет средство для одной из важнейших способностей ума – способности представлять явления в различных комбинациях. Вопросы реформирования и модернизации нынешнего школьного образования подтверждают необходимость включения стохастической линии в школьный курс, так как изучение и осмысление теории вероятностей и стохастических проблем развивает комбинаторное мышление, так нужное в нашем перенасыщенном информацией мире.
Цели и задачи
- введение в комбинаторику, знакомство с основными понятиями: перестановки, размещения, сочетания;
- введение в теорию вероятностей (частота и вероятность, сложение и умножение вероятностей);
- коррекция базовых математических знаний, систематизация, расширение и углубление знаний;
- развитие познавательных интересов и творческих способностей учащихся, психических способностей ребенка, обеспечивающих его адаптацию в дальнейшей жизни, научить школьников учиться посредствам личностно-ориентированного подхода;
- воспитание творческой личности, умеющей самореализовываться и интегрироваться в системе мировой математической культуры;
- акцентировать внимание учащихся на единых требованиях к правилам оформления различных видов заданий, включаемых в итоговую аттестацию за курс полной общеобразовательной средней школы;
- развивать способности учащихся к математической деятельности;
- способствовать совершенствованию и развитию важнейших математических знаний и умений, предусмотренных программой.
Урок 1. “Престановки”
Цели урока:
- познакомить с понятием “комбинаторика”, привести примеры комбинаторных задач;
- ввести (повторить) понятие “факториал”;
- дать определение понятия “перестановка”;
- доказать равенство Рn=n!;
- решать задачи на перестановки.
Ход урока
1) Что такое комбинаторика, решение комбинаторных задач, исторические комбинаторные задачи.
В науке и практике часто встречаются задачи, решая которые приходиться составлять различные комбинации из конечного числа элементов и подсчитывать число этих комбинаций. Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются эти задачи, называют комбинаторикой. Слово “комбинаторика” происходит от латинского слова combinare – “соединять, сочетать”.
Определение. Комбинаторика – это раздел математики, посвящённый задачам выбора и расположения предметов из различных множеств.
Типичной задачей комбинаторики является задача перечисления комбинаций, составленных из нескольких предметов.
Пример 1. Дано три элемента a, b и c. Сколькими способами можно расставить эти элементы друг за другом?
Решение: abc, acb, bac, bca, cab, cba. Всего 6 различных способов.
Пример 2. Сколько трёхзначных чисел можно составить из цифр 1, 3, 5, 7, используя в записи числа каждую цифру не более одного раза?
| 1 | 3 | 5 | 7 | ||||||||||||||||||||
| 3 | 5 | 7 | 1 | 5 | 7 | 1 | 3 | 7 | 1 | 3 | 5 | ||||||||||||
| 5 | 7 | 3 | 7 | 3 | 5 | 5 | 7 | 1 | 7 | 1 | 5 | 3 | 7 | 1 | 7 | 1 | 3 | 3 | 5 | 1 | 5 | 1 | 3 |
Итого 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 веке в связи с развитием теории вероятностей.
В древности для облегчения вычислений часто использовались камешки. При этом, особое внимание уделялось числу камешков, которые можно было разложить в виде правильной геометрической фигуры. Так появились квадратные числа (1, 4, 16, 25, . ):
Были сконструированы и треугольные числа (1, 3, 6, 10, 15, . ):
Все составные числа древние математики представляли в идее прямоугольников размером m x n, выложенных из камней, где обязательно m 1 и n 1. Простые числа представляли в виде линий 1 х n. В связи с этим составные числа древние учёные называли прямоугольными, а простые – непрямоугольными числами.
Определение. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Обозначение n!
Для того, чтобы в различных формулах не делать исключения для числа 0, принято соглашение: 0! = 1.
Таблица факториалов от 0 до 10:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| n! | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5 040 | 40 320 | 362 880 | 3 628 800 |
В примерах 1 и 2 мы составляли различные комбинации элементов и чисел, переставляя их различными способами.
Определение. Перестановкой называется конечное множество, в котором установлен порядок элементов.
В приведённых примерах различных перестановок относительно не много. Но возможны другие задачи, в которых количество перестановок достаточно большое. Выписывать их неудобно, это занимает достаточно много времени и вероятность “потерять” какое-нибудь решение велика.
Число всевозможных перестановок из n элементов вычисляется по формуле:
Если n = 1, то Pn = 1! = 1 – верно.
Допустим, что Pk = k! – верно.
Докажем, что Pk+1 = (k + 1)! – тоже верно:
Мы имеем k + 1 элемент. На первое место можно поставить любой из них. Для каждого выбора первого элемента на второе место можно поставить один из оставшихся k элементов. Для каждого выбора первых двух элементов на третье место можно поставить один из оставшихся k – 1 элементов и т.д. В результате получим, что
4) Примеры решения задач.
Пример 1. Сколькими способами могут быть расставлены восемь участниц финального забега на восьми беговых дорожках?
Решение: P8 = 8! = 40 320
Значит, существует 40 320 способов расстановки восьми участниц на восьми беговых дорожках. (Понятно, что решить эту задачу методом построения дерева возможных вариантов практически невозможно.)
Ответ: 40 320 способов.
Пример 2. Сколько различных четырёхзначных чисел можно составить из цифр 0, 1, 2, 3, причём в каждом числе цифры должны быть разные?
Решение: Количество четырёхзначных чисел, которые можно составить из 4-х различных цифр (без повторения цифр) равно числу перестановок из четырёх элементов P4. Но в этом случае будут образовываться числа, начинающиеся с 0, что невозможно. И таких перестановок будет P3. Следовательно, Р4 – Р3 = 4! – 3! = 18.
Пример 3. Имеется 10 различных книг, среди которых есть трёхтомник одного автора. Сколькими способами можно расставить эти книги на полке, если книги трёхтомника должны находиться вместе, но в любом прядке?
Ответ: 241 920 способов.
5) Задачи для самостоятельного решения (в классе и дома).
1). Сколькими различными способами могут сесть на скамейку
Решение: а) Р5 = 5! = 120; б) Р7 = 7! = 5 040.
Ответ: а) 120 способов; б) 5 040 способов.
2). Сколько различных трехцветных флагов с тремя горизонтальными полосами можно получить, используя красный, синий и белый цвета?
Решение: Р3 = 3! = 6.
3). Сколькими способами можно расставить по этапам четырёх участниц эстафеты в беге 4 х 100 м?
Решение: Р4 = 4! = 24.
Ответ: 24 способа.
4). Составьте всевозможные трёхзначные числа, в которых все цифры разные, используя лишь цифры:
а) 7, 5, 1; б) 2, 0, 9.
а) Р3 = 3! = 6 – всего 6 чисел: 751, 715, 571, 517, 175, 157.
| 7 | 5 | 1 | |||
| 5 | 1 | 7 | 1 | 7 | 5 |
| 1 | 5 | 1 | 7 | 5 | 7 |
б) Р3 – Р2 = 3! – 2! = 4 – всего 4 числа: 209, 290, 902, 920.
| 2 | 9 | ||
| 0 | 9 | 0 | 2 |
| 9 | 0 | 2 | 0 |
5). Сколько четырёхзначных чисел можно составить из цифр 1, 2, 5, 7, если каждая цифра может использоваться только один раз?
Решение: Р4 = 4! = 24.
6). Учащиеся должны посетить во вторник по расписанию 5 уроков по следующим предметам: литература, алгебра, география, физкультура и биология. Сколькими способами можно составить расписание на этот день, чтобы физкультура была пятым уроком?
Решение: Р4 = 4! = 24.
Ответ: 24 способа.
7). Из цифр 2, 3, 4, 7 составлены всевозможные четырёхзначные числа (без повторения цифр). Сколько среди этих чисел таких, которые:
а) начинаются с цифры 7;
б) не начинаются с цифры 4?
Решение: а) Р3 = 3! = 6; б) Р4 – Р3 = 4! – 3! = 18.
Ответ: а) 6 чисел; б) 18 чисел.
8). Из цифр 1, 2, 0, 5, 6 составлены всевозможные пятизначные числа (без повторения цифр). Сколько среди этих чисел таких, которые:
Решение: а) признак делимости на 4: если две последние цифры числа делятся на 4, то и всё число делится на 4. Следовательно, кратны 4 будут числа ***12, ***16, ***20, ***56. Количество чисел, оканчивающихся на 12, 16 и 56: Р3 – Р2 = 3! – 2! = 4 (т.к. 0 не может стоять на первом месте). Количество чисел, оканчивающихся на 20: Р3 = 3! = 6. Следовательно, .
б) Кратны 5 будут числа ****0: Р4 = 4! = 24 и ****5: Р4 – Р3 = 4! – 3! = 18. Следовательно, 24 + 18 = 42.
Ответ: а) 18 чисел; б) 42 числа.
9). В автомашине 5 мест. Сколькими способами в этой автомашине могут разместиться 5 человек, если место водителя могут занять только двое из них?
Решение: Р4 + Р4 = 4! + 4! = 48.
Ответ: 48 способов.
10). Чтобы открыть сейф, нужно набрать шифр, содержащий определённую последовательность из цифр 1, 2, 3, 4, 5, 6, и другой шифр, содержащий последовательность из букв a, b, c, d, в которых буквы и цифры не повторяются. Сколько существует комбинаций, при которых сейф НЕ открывается?
Решение: (все возможные варианты минус один вариант, с помощью которого сейф можно открыть).
Ответ: 17 279 комбинаций.
11). Сколькими способами можно расставить на полке четыре книги по алгебре и три по геометрии, причём так, чтобы все книги по алгебре (в любом порядке) стояли рядом?
Ответ: 576 способов.
12). Найдите сумму всех трёхзначных чисел, которые можно составить из цифр 2, 4, 6, не повторяя цифр.
Решение: Р3 = 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.
Комбинаторика
Если в последовательности нет одинаковых элементов, то говорят о размещении без повторений. Их количество
Если в последовательности допускается наличие одинаковых элементов, то говорят о размещении с повторениями. Их количество
Любое подмножество (неупорядоченное), состоящее из k элементов, называется сочетанием из n элементов по k элементов.
Различные сочетания отличаются друг от друга только самими входящими в них элементами, порядок их следования безразличен, т.е. по условию задачи подмножества <1,2>и <2,1>не различны (соединены).
Число сочетаний без повторений
Число сочетаний с повторениями
Количество способов переставить элементов в заданном множестве (количество перестановок) вычисляется по формуле
При решении простейших комбинаторных задач можно использовать следующую таблицу, определяющую число множеств, состоящих из k элементов, отбираемых из множества, содержащего n элементов
| Выбор | Неупорядоченный | Упорядоченный |
| Без повтора | ||
| С повтором |
Рассмотрим разницу между сочетаниями, размещениями с повторениями, без повторений на следующих примерах.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
ПРИМЕР 13.2.1 В коробке 6 шаров, пронумерованных от 1 до 6. Из коробки вынимаются друг за другом 3 шара и в этом же порядке записывают полученные цифры. Сколько трехзначных чисел можно таким образом записать?
Решение: По условию задачи подмножества <1;2;3>и <3;1;2>– различные. Повторов в подмножестве быть не может, так как шары не возвращаются в коробку.
ПРИМЕР 13.2.2. В коробке 6 шаров пронумерованных от 1 до 6. Из коробки вынимаются 3 шара и записывают число в порядке возрастания цифр. Сколько трехзначных чисел можно таким образом записать?
Решение: По условию задачи подмножества <1;2;3>и <3;2;1>дают число 123, т.е. не являются различными.
ПРИМЕР 13.2.3. Условие задачи 2.1 (шары возвращаются в коробку)
ПРИМЕР 13.2.4. Условие задачи 2.2 (шары возвращаются в коробку)
ПРИМЕР 13.2.5. Сколько различных перестановок можно составить из букв слова «комар»?
ПРИМЕР 13.2.6. Сколько различных перестановок можно составить из букв слова «задача»?
Решение: Если бы все шесть букв слова были различны, то число перестановок было бы 6! Но буква «а» встречается в данном слове три раза, и перестановки только этих трех букв «а» не дают новых способов расположения букв. Поэтому число перестановок букв слова «задача» будет не 6!, а в 3! раза меньше, то есть .
ПРИМЕР 13.2.7. В мастерской имеется материал 5 цветов. Поступил заказ на пошив флагов, состоящих из трех горизонтальных полос разного цвета каждый. Сколько таких различных флагов может сшить мастерская?
Решение: Флаги отличаются друг от друга как цветом полос, так и их порядком, поэтому разных флагов можно сделать штук.
ПРИМЕР 13.2.8. Сколькими способами можно распределить 5 учеников по 3 параллельным классам?
Решение: Составим вспомогательную таблицу
Таким образом, видно, что если для одного ученика существует 3 варианта выбора класса, то для всех 5 учеников существует способов распределения по классам.
ПРИМЕР 13.2.9. На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй том не стояли рядом?
Решение: Произведем рассуждения “от обратного”. Тридцать томов на одной полке можно разместить 30! способами.
Если 1 и 2 тома должны стоять рядом, то число вариантов расстановки сокращается до , т.к. комбинацию из 1 и 2 тома можно считать за один том, но при этом они могут стоять как (1;2) или (2;1), т.е.
Тогда искомое число способов расстановки есть
ПРИМЕР 13.2.10. Чемпионат, в котором участвуют 16 команд, проводится в два круга, т.е. каждая команда дважды встречается с любой другой. Определить, какое количество встреч следует провести.
ПРИМЕР 13.2.11. Автомобильная мастерская имеет для окраски 10 основных цветов. Сколькими способами можно окрасить автомобиль, если смешивать от 3 до 7 основных цветов?
Решение: Составим схему.
Из рисунка видно, что вариантов маршрута из А в B существует 3, и из B в C – 4, т.е. всего маршрутов .
На обратном пути вариантов маршрута из С в B существует 3 (один уже пройден), и из B в А – 2, т.е. всего возможных обратных маршрутов осталось . Тогда всего вариантов маршрута .
ПРИМЕР 13.2.13. Двенадцати ученикам выданы два варианта контрольной работы. Сколькими способами можно посадить учеников в два ряда по 6 человек, чтобы у сидящих рядом не было одинаковых вариантов, а у сидящих друг за другом был один и тот же вариант?
Решение: Рассуждения произведем несколькими способами
I способ) Первоначально 12 учеников разбивают на 2 группы по 6 человек. Это можно сделать способами.
Затем они могут распределиться по своим рядам согласно схеме
Поэтому всего способов распределения учеников будет .
II способ) Первоначально 12 учеников запускают в класс, указывая место, где каждый должен сидеть, например “второй ряд, третье место”. Так как посадочных мест также 12, то всего вариантов распределения 12!
Варианты контрольной работы могут распределиться
“I вариант – I ряд, II вариант – II ряд”
“II вариант – I ряд, I вариант – II ряд”,
Таким образом, всего способов распределения учеников будет .
По приведенным решениям видно, что результаты решений совпадают.
ПРИМЕР 13.2.14. Сколько существует вариантов расположения шести гостей за круглым шестиместным столом?
Решение: Эта задача имеет разные решения и, соответственно разные ответы – в зависимости от того, что понимать под различным расположением гостей за столом. Поэтому исследуем возможные варианты.
Если считать, что нам важно, кто сидит на каком стуле, то это простая задача на перестановки и, следовательно, всего вариантов .
Если же важно не то, кто какой стул занял, а то, кто рядом с кем сидит, то требуется рассмотреть варианты взаимного расположения гостей. В таком случае, расположения гостей, получаемые одно из другого при повороте гостей вокруг стола, фактически являются одинаковыми (смотри рисунок).
В такой постановке вопроса общее число различных вариантов расположений гостей уменьшается вдвое и составляет 60.
Отметим, что каждое решение будет считаться правильным при соответствующей постановке задачи.
ПРИМЕР 13.2.15. Семнадцать студентов сдали экзамены по 4 предметам только на “хорошо” и “отлично”. Верно ли утверждение, что хотя бы у двух из них оценки по экзаменационным предметам совпадают?
Решение: Очевидно, что в данном случае речь идет о возможных вариантах вида
Данный пример можно решить способом, изложенным в примере 13.1.8., и получить количество вариантов . Приведем другой наглядный способ решения, использующий так называемое “дерево решений”,который представляет все варианты (16 штук) получения экзаменационных оценок.
По “дереву решений” видно, что 16 студентов могут сдать экзамены только на “хорошо” и “отлично” так, что их результаты будут отличаться, но если студентов 17, хотя бы одно повторение обязательно будет.
При решении задач комбинаторики используются следующие правила.
Если некоторый объект A может быть выбран из совокупности объектов m способами, а другой объект B может быть выбран nспособами, то:
Правило суммы: выбрать либо A, либо B можно m+n способами.
Правило произведения. Пара объектов (A,B) в указанном порядке может быть выбрана способами.
Примеры и задачи для самостоятельного решения
Решить комбинаторную задачу.
13.2.1.1. В группе 25 студентов. Сколькими способами можно выбрать старосту, заместителя старосты и профорга?
13.2.1.2. В группе 25 студентов. Сколькими способами можно выбрать актив группы, состоящий из старосты, заместителя старосты и профорга?
13.2.1.3. Сколькими способами можно составить список из 10 человек?
Отв.: 3628800
13.2.1.4. Сколькими способами из 15 рабочих можно создать бригады по 5 человек в каждой?
Отв.: 126126
13.2.1.5. Буквы азбуки Морзе образуются как последовательности точек и тире. Сколько букв можно составить, используя для кодировки каждой из букв: а) ровно 5 символов? б) не более пяти символов?
Отв.: а)32; б) 62
13.2.1.6. Кости для игры в домино метятся двумя цифрами. Кости симметричны, и поэтому порядок чисел не существенен. Сколько различных костей можно образовать, используя числа 0,1,2,3,4,5,6?
13.2.1.7. Сколько различных звукосочетаний можно взять на десяти выбранных клавишах рояля, если каждое звукосочетание может содержать от трех до десяти различных звуков?
Отв.: 9864000
13.2.1.8. В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?
13.2.1.9. В некоторых странах номера трамвайных маршрутов обозначаются двумя цветными фонарями. Какое количество различных маршрутов можно обозначить, если использовать фонари восьми цветов?
13.2.1.10. Команда компьютера записывается в виде набора из восьми цифровых знаков – нулей и единиц. Каково максимальное количество различных команд?
13.2.1.11. Десять групп занимаются в десяти расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы 1 и 2 находились бы в соседних аудиториях?
Отв.: 725760
13.2.1.12. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?
13.2.1.13. Замок открывается только в том случае, если набран определенный трехзначный номер. Попытка состоит в том, что набирают наугад три цифры из заданных пяти. Угадать номер удалось только на последней из всех возможных попыток. Сколько попыток предшествовало удачной?
13.2.1.14. Номер автомобильного прицепа состоит из двух букв и четырех цифр. Сколько различных номеров можно составить, используя 30 букв и 10 цифр?
Отв.: 9000000
13.2.1.15. У одного студента есть 7 DVD дисков, а у другого – 9 дисков. Сколькими способами они могут обменять 3 диска одного на 3 диска другого?
Отв.: 105840
13.2.1.16. На вершину горы ведут 7 дорог. Сколькими способами турист может два раза подняться на гору и спуститься с нее, если по одной и той же дороге нельзя проходить дважды?
13.2.1.17. У ювелира было 9 разных драгоценных камней: сапфир, рубин, топаз и т.д. Ювелир планировал изготовить браслет для часов, однако три камня было украдено. Насколько меньше вариантов браслета он может изготовить по сравнению с первоначальными планами?
Отв.: 362160
13.2.1.18. В поезд метро на начальной станции вошли 10 пассажиров. Сколькими способами могут выйти все пассажиры на последующих 6 станциях?
Отв.: 60466176
13.2.1.19. За одним столом надо рассадить 5 мальчиков и 5 девочек так, чтобы не было двух рядом сидящих мальчиков и двух рядом сидящих девочек. Сколькими способами это можно сделать?
13.2.1.20. В классе 25 учеников. Верно ли утверждение, что, по крайней мере, у трех из них день рождения в один и тот же месяц?
13.2.1.21. На участке железной дороги расположено 25 станций с билетной кассой в каждой. Касса каждой станции продает билеты до любой другой станции, притом в обоих направлениях. Сколько различных вариантов билетов можно выдать на этом участке?
13.2.1.22. На официальном приеме 50 человек обменялись рукопожатиями. Сколько было сделано рукопожатий?
Сколькими способами можно поставить на полке 4 различные вазы
Комбинаторика для начинающих. МФТИ. Разбор ряда задач недель 2-3
Эти недели были о тех самых четырёх формулах сочетания и размещения.
Жених и невеста выбирают трехъярусный свадебный торт. На выбор имеются 5 типов ярусов (бисквитный, йогуртовый, чизкейк и т.д.). Сколько различных тортов может предложить кондитер, если бисквитных ярусов может быть не больше двух, а ярусов любого другого типа не больше одного?
Ответ: 72.
Решение: используем правило сложения и суммируем результаты по трём вариантам - бисквитных ярусов нет, он один, их два.
Если их нет, мы просто размещаем по трём слоям четыре типа. Нам нельзя иметь более одного одинакового слоя из оставшихся. Это размещение без повторений из 4 по 3. Равно 24.
Один ярус может быть занят 3 способами, кроме того, каждому варианту соответствует размещение из 4 уже по 2. Это 3*12=36.
Наконец, бисквитных ярусов два. Они так же могут быть в составе торта 3 способами (чисто интуитивно 1-2, 2-3, 3-1) и им соответствует размещение уже из 4 по 1. 3*4=12.
Итого 24+36+12=72.
У королевы есть 12 одинаковых зеркал. Сколькими способами их можно повесить в 8 разных залах замка так, чтобы в каждом зале было хотя бы одно зеркало?
Ответ: 330.
Решение: внимательно прочитайте - ХОТЯ БЫ одно зеркало. То есть, или одно или два. Здесь нельзя вслепую выбрать сочетание (а порядок не важен и количество зеркал ограничено) 8 из 12. Нет.
Залов меньше, чем зеркал. Очевидно, будут залы с не одним зеркалом.
"Первые восемь" зеркал мы уже, давайте считать, повесили. Уточнение - да, залы разные, но сами зеркала одинаковые. Эти восемь взяли и повесили и, как потом не меняй их местами, суть не меняется.
А вот оставшиеся зеркала это уже другой вопрос. Их 4.
У нас есть 4 оставшихся зеркала. И 8 залов. Мы не обязаны раскидывать эти зеркала равномерно или через раз или ещё как. Мы вообще можем их все отнести в один зал. Это тонкий момент - если мы эти четыре зеркала можем отнести в один зал, то этот зал ПОВТОРЯЕТСЯ. Но при этом порядок тут не имеет значения.
Как вы уже догадываетесь - это сочетание с повторениями. Надо выбрать, в какой из восьми залов нести четыре зеркала. То есть, тут мы выбираем, по сути зал. Они разные, а зеркала одинаковые. Стало быть, это сочетание из 8 по 4 с повторами.
Сколькими способами в течение 5 дней можно выбирать на дежурство по 4 ученика из класса в 20 человек так, чтобы каждый день состав дежурных был разным?
Ответ: скрин.
Решение: легче, чем кажется. Без привязки к дням - как можно выбрать дежурных? Сочетание без повторений из 20 по 4. А дальше? А дальше просто из каждого нового дня вычитаем вариант, который был вчера. А затем это все умножить, ведь надо знать количество способов всего. И обратите внимание, как ловко сочетания тут свернулись в размещения.
элективный курс "Введение в комбинаторику"
элективный курс по информатике и икт (8 класс) по теме
Решение с учащимися комбинаторных задач на уроках информатики способствует значительному повышению их математической и алгоритмической культуры: развивается динамичность мышления, его гибкость, формируется умение разделить сложный объект на простые составляющие и определить взаимосвязи между ними. Опыт проведения уроков, посвященных этому классу задач, подтвердил роль комбинаторных задач в развития мышления учащихся, формировании умения ставить проблему, выдвигать гипотезу решения и проверять её.
| Вложение | Размер |
|---|---|
| vvedenie_v_kombinatoriku.docx | 220.75 КБ |
Предварительный просмотр:
Введение в комбинаторику.
Комбинаторные задачи в программировании.
Введение
Известно, что теме «комбинаторика» в курсе математики уделяется недостаточно внимания, между тем комбинаторные задачи имеют огромное практическое применение при решении прикладных задач, особенно в условиях рыночной экономики. Комбинаторные методы используются для решения задач линейного программирования, для составления и декодирования шифров, для решения маркетинговых задач и задач прикладной статистики, для составления биржевых прогнозов.
Решение с учащимися комбинаторных задач на уроках информатики способствует значительному повышению их математической и алгоритмической культуры: развивается динамичность мышления, его гибкость, формируется умение разделить сложный объект на простые составляющие и определить взаимосвязи между ними. Все это необходимо для изучения и построения формальных моделей и позволяет научиться такому подходу к любой задаче, при котором решение задачи выступает как объект конструирования и изобретения. В условиях рынка важно уметь выбирать из многих возможностей наиболее приемлемые, просчитывать варианты.
Комбинаторные задачи предоставляют богатый материал для изучения основных конструкций, методов и приемов программирования, позволяют показать не только красоту математики, но и возможности новых компьютерных технологий при решении практических математических задач.
Опыт проведения уроков, посвященных этому классу задач, подтвердил роль комбинаторных задач в развития мышления учащихся, формировании умения ставить проблему, выдвигать гипотезу решения и проверять её. В результате укрепляются межпредметные связи и учащиеся понимают, что информатика – это не только умение нажимать нужные кнопки в определенной ситуации, но и наука, тесно связанная с математикой.
Перестановки. Правило умножения
Многие поколения людей интересовали задачи, в которых необходимо было найти количество способов расположения множества объектов. Сколькими способами можно поставить 10 человек в очередь к билетной кассе? Сколько существует различных автомобильных номеров? Сколько «счастливых» трамвайных билетов? Сколько способов выбора маршрута из пункта А в пункт Б ? и т.п.
Рассмотрим пример 1. Сколькими способами можно расставить на полке 3 книги ? (Обозначим их А, В, С ).
Решение 1 . На первое место мы можем поставить любую из трех книг, следовательно это можно сделать тремя способами, поставив книгу А, или В, или С. Остаются две книги. На второе место можно поставить любую из двух оставшихся, т.е. имеем две возможности заполнить второе место на полке. На третье место ставим оставшуюся одну книгу:
Тест по комбинаторике с ответами
Нет времени или сил пройти тест онлайн? Поможем сдать тест дистанционно для любого учебного заведения: подробности.
Вопрос 1. Сколькими способами могут разместиться 8 человек в салоне автобуса на восьми свободных местах?
- 40320
- 1600
- 24
- 4
Вопрос 2. Комбинаторика отвечает на вопрос
- какова частота массовых случайных явлений;
- с какой вероятностью произойдет некоторое случайное событие;
- сколько различных комбинаций можно составить из элементов данного множества.
Вопрос 3. Сколько существует вариантов выбора двух чисел из восьми?
- 36
- 18
- 28
- 6
Вопрос 4. В партии из 4000 семян пшеницы 50 семян не взошли. Какова вероятность появления невсхожих семян?
- 0,05
- 0,0125
- 0,5
- 0,001
Вопрос 5. Выберите из предложенных множеств множество натуральных чисел
- N
- C
- Q
- R
Вопрос 6. Множество, состоящее из всех элементов, принадлежащих множеству А и не принадлежащих множеству В называют
- пересечением множеств А и В;
- разностью множеств А и В;
- объединением множеств А и В.
Вопрос 7. Любое множество, состоящее из $k$ элементов, взятых из данных $n$ элементов, называется
- сочетанием
- размещением
- перестановкой
Вопрос 8.Количество сочетаний из $n$ элементов по $k$ вычисляют по формуле:
- $\frac
- $\frac
- $\frac
Вопрос 9. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5?
- 120
- 3125
- 5
- 20
Вопрос 10. Сколькими способами из 9 учебных дисциплин можно составить расписание учебного дня из 6 различных уроков.
- 258
- 10000
- 60480
- 78356
Сдаем тесты по элементам комбинаторики и теории вероятностей: цены, результаты, отзывы
Вопрос 11. Если объект А можно выбрать х способами, а объект В – у способами, то каким количеством способов можно выбрать объект «А и В»
- xy
- x
- x-y
- x+y
Вопрос 12. Сколькими способами можно расставить 4 различные книги на книжной полке?
- 20
- 4
- 24
- 16
Вопрос 13. В футбольной команде 11 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами это можно сделать?
- 110
- 160
- 121
- 11
Вопрос 14. Вычислить $10!/5!$
- 2
- 125
- 2000
- 30240
Вопрос 15. В корзине лежат грибы, среди которых 10% белых и 40% рыжих. Какова вероятность того, что выбранный гриб белый или рыжий?
- 0.5
- 0.1
- 0.4
- 0.04
Вопрос 16. Сколько существует трехзначных чисел, все цифры которых нечетные и различные.
- 30
- 60
- 120
- 10
Вопрос 17. Число 14! НЕ делится на:
- 168
- 136
- 147
- 132
Вопрос 18. Сколько различных двухзначных чисел можно записать, используя цифры 2, 3, 8, если цифры в этих числах могут повторяться?
- 9
- 3
- 6
- 8
Вопрос 19. Что означает $K!$
- восклицание
- произведение целых чисел от 1 до $K$
- сумму квадратов целых чисел от 1 до $K$
- $K-1$
Вопрос 20. Сколькими способами могут разместиться 3 человека в четырехместном купе на свободных местах?
Сколькими способами можно поставить на полке 4 различные вазы
В магазине «Все для чая» есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?
Выберем чашку. В комплект к ней можно выбрать любое из трех блюдец. Поэтому есть 3 разных комплекта, содержащих выбранную чашку. Поскольку чашек всего 5, то число различных комплектов равно 15 (15 = 5 • 3).
В магазине «Все для чая» есть еще 4 чайные ложки. Сколькими способами можно купить комплект из чашки, блюдца и ложки?
Выберем любой из 15 комплектов предыдущей задачи. Его можно дополнить ложкой четырьмя различными способами. Поэтому общее число возможных комплектов равно 60 (60 = 15 • 4 = 5 • 3 • 4).
В Стране Чудес есть три города: А, Б и В. Из города А в город Б ведет 6 дорог, а из города Б в город В – 4 дороги. Сколькими способами можно проехать от А до В?
В Стране Чудес есть четыре города: А, Б и В и Г. Из города А в город Б ведет 6 дорог, а из города Б в город В – 4 дороги, Из города А в город Г – две дороги, и из города Г в город В – тоже две дороги. Сколькими способами можно проехать от А до В?
Выделим два случая: путь проходит через город Б или через город Г. В каждом из этих случаев легко сосчитать количество возможных маршрутов: в первом – 24, во втором – 6. Складывая, получаем общее количество маршрутов: 30.
В магазине «Все для чая» по-прежнему продается 5 чашек, 3 блюдца и 4 чайные ложки. Сколькими способами можно купить два предмета с разными названиями?
Возможны три разных случая: первый – покупаются чашка с блюдцем, второй – чашка с ложкой, третий – блюдце и ложка. В каждом из этих случаев легко сосчитать количество возможных вариантов (в первом – 15, во втором – 20, в третьем – 12). Складывая, получаем общее число возможных вариантов: 47.
Назовем натуральное число «симпатичным» , если в его записи встречаются только нечетные цифры. Сколько существует 4-значных «симпатичных» чисел?
Понятно, что однозначных «симпатичных» чисел ровно 5. К каждому однозначному «симпатичному» числу вторая нечетная цифра может быть дописана пятью различными способами. Таким образом, двузначных «симпатичных» чисел всего 5 • 5 = 25. Аналогично, трехзначных «симпатичных» чисел 5 • 5 • 5 = 125, и четырехзначных – 5 • 5 • 5 • 5 = 54 = 625.
Монету бросают трижды. Сколько разных последовательностей орлов и решек можно при этом получить?
Каждую клетку квадратной таблицы 2 ? 2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы?
Сколькими способами можно заполнить одну карточку в лотерее «Спорт-про-г-ноз»? (В этой лотерее нужно предсказать итог тринадцати спортивных матчей. Итог каждого матча – победа одной из команд либо ничья; счет роли не играет).
Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и В. Словом является любая последовательность, состоящая не более, чем из 4 букв. Сколько слов в языке племени Мумбо-Юмбо? Указание. Сосчитайте отдельно количества одно-, двух-, трех- и четырехбуквенных слов.
Ответ: 3 + 3? + 3? + 34 = 120.
В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?
Капитаном может стать любой из 11 футболистов. После выбора капитана на роль его заместителя могут претендовать 10 оставшихся человек. Таким образом, всего есть 11 • 10 = 110 разных вариантов выборов.
Сколькими способами можно сделать трехцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя шести различных цветов?
Цвет для верхней полоски флага можно выбрать шестью разными способами. После этого для средней полоски флага остается пять возможных цветов, а затем для нижней полоски флага – четыре различных цвета. Таким образом, флаг можно сделать 6 • 5 • 4 = 120 способами.
Сколькими способами можно поставить на шахматную доску белую и черную ладьи так, чтобы они не били друг друга?
Белую ладью можно поставить на любую из 64 клеток. Независимо от своего расположения она бьет 15 полей (включая поле, на котором она стоит). Поэтому остается 49 полей, на которые можно поставить черную ладью. Таким образом, всего есть 64 • 49 = 3136 разных способов.
Сколькими способами можно поставить на шахматную доску белого и черного королей так, чтобы получилась допустимая правилами игры позиция?
Белого короля можно поставить на любое из 64 полей. Однако количество полей, которые он при этом будет бить, зависит от его расположения. Поэтому необходимо разобрать три случая:
а) если белый король стоит в углу (углов всего 4), то он бьет 4 поля (включая то, на котором стоит), и остается 60 полей, на которые можно поставить черного короля;
б) если белый король стоит на краю доски, но не в углу (таких полей – 24), то он бьет 6 полей, и для черного короля остается 58 возможных полей;
в) если же белый король стоит не на краю доски (таких полей – 36), то он бьет 9 полей, и для черного короля остается 55 возможных полей.
Таким образом, всего есть 4 • 60 + 24 • 58 + 36 • 55 = 3612 способов расстановки королей.
Сколько существует трехзначных чисел, в записи которых цифры 1, 2, 3 встречаются ровно по одному разу?
Будем рассуждать точно так же, как при решении задач предыдущего цикла. На первое место можно поставить любую из трех цифр, на второе – любую из двух оставшихся, а на третье – последнюю оставшуюся цифру. Таким образом, всего получается 3 • 2 • 1 = 3! чисел.
Сколькими способами можно выложить в ряд красный, черный, синий и зеленый шарики?
На первое место можно положить любой из четырех шариков, на второе – любой из трех оставшихся, на третье – любой из двух оставшихся, а на четвертое – последний оставшийся шарик. Итак, ответ: 4 • 3 • 2 • 1 = 4!.
Задача 17: Слово – любая конечная последовательность букв русского алфавита. Выясните, сколько различных слов сожно составить из слов
а) Так как все буквы слова различны, то всего можно получить 6! слов.
б) В этом слове две буквы И, а все остальные буквы разные. Временно будем считать разными и буквы И, обозначив их через И1 и И2. При этом предположении получится 5! = 120 разных слов. Однако те слова, которые получаются друг из друга только перестановкой букв И1 и И2, на самом деле одинаковы. Таким образом, полученные 120 слов разбиваются на пары одинаковых. Поэтому разных слов всего 120:2 = 60.
в) Считая три буквы А этого слова различными (А1, А2, А3), получим 8! разных слов. Однако слова, отличающиеся лишь перестановкой букв А, на самом деле одинаковы. Поскольку буквы А1, А2, А3 можно переставлять 3! способами, все 8! слов разбиваются на группы по 3! одинаковых. Поэтому разных слов всего 8!/3!.
г) В этом слове три буквы С и две буквы И. Считая все буквы различными, получаем 11! слов. Отождествляя слова, отличающиеся лишь перестановкой букв И, но не С, получаем 11!/2! различных слов. Отождествляя теперь слова, отличающиеся перестановкой букв С, получаем окончательный результат 11!/(2! • 3!).
д) Ответ: 10!/(3! • 2! • 2!).
В стране 20 городов, каждые два из которых соединены авиалинией. Сколько авиалиний в этой стране?
Каждая авиалиния соединяет два города. В качестве первого города можно взять любой из 20 городов (город А), а в качестве второго – любой из 19 оставшихся (город В). Перемножив эти числа, получаем 20 • 19 = 380. Однако при этом подсчете каждая авиалиния учтена дважды (первый раз, когда в качестве первого города был выбран город А, а второго – город В, а второй раз – наоборот). Таким образом, число авиалиний равно 380:2 = 190.
Сколько диагоналей в выпуклом n-угольнике?
Бусы – это кольцо, на которое нанизаны бусины. Бусы можно поворачивать, но не переворачивать. Сколько различных бус можно сделать из 13 разноцветных бусин?
Предположим теперь, что бусы можно и переворачивать. Сколько тогда различных бус можно сделать из 13 разноцветных бусин?
Сколько существует 6-значных чисел, в записи которых есть хотя бы одна четная цифра?
Вместо того, чтобы подсчитывать количество требуемых 6-значных чисел, определим количество 6-значных чисел, не обладающих нужным свойством. Так как это в точности те числа, в записи которых встречаются только нечетные цифры, то их количество, очевидно, равно 56 = 15625. Всего 6-значных чисел 900000. Поэтому количество 6-значных чисел, обладающих указанным свойством, равно 900000 – 15625 = 884375.
В алфавите племени Бум-Бум шесть букв. Словом является любая последовательность из шести букв, в которой есть хотя бы две одинаковые буквы. Сколько слов в языке племени Бум-Бум?
В киоске «Союзпечать» продаются 5 видов конвертов и 4 вида марок. Сколькими способами можно купить конверт с маркой?
Сколькими способами можно выбрать гласную и согласную буквы из слова «КРУЖОК»?
На доске написаны 7 существительных, 5 глаголов и 2 прилагательных. Для предложения нужно выбрать по одному слову каждой из этих частей речи. Сколькими способами это можно сделать?
Ответ: 7 • 5 • 2 = 70
У двух начинающих коллекционеров по 20 марок и по 10 значков. Честным обменом называется обмен одной марки на одну марку или одного значка на один значок. Сколькими способами коллекционеры могут осуществить честный обмен?
Ответ: 20 • 20 + 10 • 10 = 500
Сколько существует 6-значных чисел, все цифры которых имеют одинаковую четность?
Ответ: 56 + 4 • 55
Надо послать 6 срочных писем. Сколькими способами это можно сделать, если для передачи писем можно использовать трех курьеров и каждое письмо можно дать любому из курьеров?
Сколькими способами из полной колоды (52 карты) можно выбрать 4 карты разных мастей и достоинств?
Ответ: 13 • 12 • 11 • 10
На полке стоят 5 книг. Сколькими способами можно выложить в стопку несколько из них (стопка может состоять и из одной книги)?
Ответ: 5 + 5 • 4 + 5 • 4 • 3 + 5 • 4 • 3 • 2 + 5 • 4 • 3 • 2 • 1 = 325
Сколькими способами можно поставить 8 ладей на шахматную доску так, чтобы они не били друг друга?
На танцплощадке собрались N юношей и N девушек. Сколькими способами они могут разбиться на пары для участия в очередном танце?
Чемпионат России по шахматам проводится в один круг. Сколько играется партий, если участвуют 18 шахматистов?
Ответ: 18 • 17/2 = 153
Сколькими способами можно поставить на шахматную доску так, чтобы они не били друг друга а) две ладьи; б) двух королей; в) двух слонов; г) двух коней; д) двух ферзей?
Ответ: a) 64 • 49/2 = 1568 б) (4 • 60 + 24 • 58 + 36 • 55)/2 = 1806 в) (28 • 56 + 20 • 54 + 12 • 52 + 4 • 50)/2 = 1736 г) (4 • 61 + 8 • 60 + 20 • 59 + 16 • 57 + 16 • 55)/2 = 1848 д) (28 • 42 + 20 • 40 + 12 • 38 + 4 • 36)/2 = 1288
У мамы два яблока, три груши и четыре апельсина. Каждый день в течение девяти дней подряд она дает сыну один из оставшихся фруктов. Сколькими способами это может быть сделано?
Сколькими способами можно поселить 7 студентов в три комнаты: одноместную, двухместную и четырехместную?
Сколькими способами можно расставить на первой горизонтали шахматной доски комплект белых фигур (король, ферзь, две ладьи, два слона и два коня)?
Сколько слов можно составить из пяти букв А и не более чем из трех букв Б?
Ответ: 1 + 6!/5!1! + 7!/5!2! + 8!/5!3! = 84
Сколько существует 10-значных чисел, в которых имеется хотя бы две одинакоые цифры?
Решение: 9 • 109 – 9 • 9!
Каких 7-значных чисел больше: тех, в записи которых есть 1, или остальных?
07. Перестановки
Рассмотрим частный случай, когда k=n. Соответствующее этому случаю размещение называется перестановкой.
Перестановками из n элементов называются такие комбинации, каждая из которых содержит все n элементов и которые отличаются друг от друга лишь порядком расположения элементов.
Поясним это на следующем примере. Из этих трёх элементов: a, b и c. можно составить шесть перестановок: abc, acb, bac, bca, cab, cba. Все приведённые перестановки отличаются друг от друга только порядком их расположения.
Число перестановок n различных элементов обозначают символом Pn и равно
Пример 5.1. Сколькими способами можно расставить девять различных книг на полке, чтобы определенные четыре книги стояли рядом?
Решение. Будем считать выделенные книги за одну книгу. Тогда уже для шести книг существует P6=6!=720 перестановок. Однако четыре определенные книги можно переставить между собой P4=4!=24 способами. По принципу умножения имеем
P6P4 = 720×24 = 17280.
Пример 5.2. Сколько различных четырехзначных чисел можно составить из цифр 0, 1, 2, 3, если каждая цифра в изображении числа встречается один раз?
Решение. Рассматриваемое число может быть представлено как некоторая перестановка из цифр 0, 1, 2, 3, в которой первая цифра отлична от нуля. Так как число перестановок из четырех цифр равно P4=4! и из них 3! перестановок начинаются с нуля, то искомое количество равно
Пример 5.3. Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом?
Решение. Естественно предположить, что как мужчины, так и женщины различимы. Предположим также, что места за столом также различимы. Пронумеруем их. Если женщины займут чётные места n! способами, то мужчины будут занимать нечётные места тоже n! способами и наоборот. По правилу умножения получаем .
Если места за столом неразличимы, то стол можно поворачивать на одно место, то при этом расположение сидящих не изменится (такая ситуация имеет место, например, на карусели). Поскольку имеется n способов расположения стола относительно сидящих, то предыдущий результат нужно разделить на n.
Вопрос. Сколькими способами можно посадить за круглый стол n супружеских пар, если супруги должны сидеть рядом?
5.1. Сколькими способами можно обить 6 стульев тканью, если имеются ткани 6 различных цветов и все стулья должны быть разного цвета.
Ответ: .
5.2. Дачник выделил на своём участке семь грядок для выращивания овощей, т. к. хочет иметь свои помидоры, огурцы, перец, лук, чеснок, салат и кабачки. Каждый вид должен иметь отдельную грядку. Сколькими способами он может расположить грядки для посадки?
Ответ: .
5.3. Пассажирский поезд состоит из трех багажных вагонов и восьми купированных. Сколькими способами можно сформировать состав, если багажные вагоны должны находиться в его начале?
Ответ: .
5.4. В первенстве края по футболу участвуют 11 команд. Сколько существует различных способов распределения мест в таблице розыгрыша, если на первое место могут претендовать только 4 определенные команды?
Ответ:
5.5. Сколькими способами можно упорядочить множество <1,2,3,…,2n>так, чтобы каждое чётное число стояло на чётном месте?
Ответ: .
5.6. Четыре мальчика и четыре девочки рассаживаются в ряд на восемь подряд расположенных мест, причем мальчики садятся на четные места, а девочки – на нечетные. Сколькими способами они могут это сделать?
Ответ: .
5.7. Сколькими способами можно посадить за круглый стол трех мужчин и трех женщин так, чтобы никакие два лица одного пола не сидели рядом?
Ответ: .
5.8. На собрании должны выступить 5 человек: А, Б, В, Г, Д. Сколькими способами можно расположить их в списке ораторов, если Б не должен выступать до того, как выступил А? Решите эту же задачу, если Б должен выступить сразу после А.
Читайте также: