Основные правила комбинаторики

Большинство комбинаторных задач решается с помощью двух основных правил – правила суммы и правила произведения.

Правило суммы. Если некоторый объект А можно выбрать n способами, а другой объект B можно выбрать m способами, то выбор «либо A, либо B» можно осуществить n +m способами.

Правило произведения. Если объект A можно выбрать n способами, а после каждого такого выбора другой объект B можно выбрать (независимо от выбора объекта A) m способами, то пары объектов A и B можно выбрать n × m способами.

Комбинаторные соединения

Комбинаторные соединения – это такие комбинации из каких-либо элементов.

Типы соединений:

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

• Размещения

• Сочетания

ПЕРЕСТАНОВКИ

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

Формула для нахождения количества перестановок без повторений:

Рn = n(n-1)×…×1 = n!

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

формула для нахождения количества перестановок с повторениями:

Pn (m1,m2,…,mk) =

Пример. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?

Решение.

1. Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

По формуле получаем:

наборов.

2. Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.

По формуле получаем:

наборов.

Размещения

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

Размещения с повторениями – комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.

Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?

Решение.

1. Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.

По формуле получаем:

наборов.

2. Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

По формуле получаем: наборов.

Сочетания

Сочетания без повторений – комбинаторные соединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом. комбинаторика математический лейбниц

Формула для нахождения количества сочетаний без повторений:

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

Формула для нахождения количества сочетаний с повторениями:

Пример. Возьмем буквы Б, А, Р. Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы.

Решение.

1. Получатся наборы: БА (БА и АБ – один и тот же набор), АР и РБ

По формуле получаем:

наборов.

2. Получатся наборы: ББ, БА, БР, АА, АР, РР.

По формуле получаем:

наборов.

§ 4. Элементы комбинаторики. Соединения без повторений и с повторениями. Правила суммы и произведения.

Комбинаторика – теория соединений – изучает некоторые операции над конечными множествами, как упорядочение множества и разбиение множества, интересуется расположением элементов в множестве, выясняет, сколькими способами можно расположить элементы множества в том или ином порядке. Это приводит к понятиям перестановок, размещений и сочетаний. Основными задачами комбинаторики являются: 1) определение вида соединения; 2) подсчет числа соединений.

П.1 Соединения без повторений

Пусть дано множество М, состоящее из nэлементов.

Опр. 4.1.1Перестановки– всевозможные упорядоченные множества, составленные из всех элементов данного множества. Число всевозможных перестановок изnэлементов обозначают Р_nи находят по формуле

Р_n= n! (1),

где n!= 123n, 0!=1 по определению.

Пример 4.1.1.Сколько перестановок можно составить из трех букв а, в, с?

Решение:Р₃=123=6. Действительно: авс, вас, асв, сав, вса, сва.

Пример 4.1.2. Сколькими способами можно переставить буквы в слове «треугольник»?

Решение:Т.к. все буквы в данном слове разные, т.е. нет повторений, то можно воспользоваться формулой (1): Р₁₁=11!=39916800.

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

(2).

Пример 4.1.3.Сколько можно составить четырехзначных чисел, содержащих различные цифры из 5 цифр.

Решение:Четырехзначное число – это упорядоченная последовательность цифр, т.е. имеем дело с размещениями без повторений: А₅⁴=5432=120.

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

Решение:

Опр. 4.1.3Сочетаниями из n по m называются всевозможные подмножества данныхn элементов, состоящие изm элементов. Для подсчета их числа используются следующие обозначение и формула:

(3).

Пример 4.1.5.Сколькими способами можно из 7 различных открыток выбрать три?

Решение:Совокупность трех открыток является неупорядоченным подмножеством семи открыток, поэтому имеем дело с сочетаниями:

П.2 Соединения с повторениями

Опр: 4.2.1Перестановками с повторениями называются перестановки изnэлементов, в каждую из которых входитn₁элементова,n₂элементовb, …,n_kэлементовl, гдеn=n₁+n₂+…+n_k. Число перестановок с повторениями вычисляется по формуле:

Пример 4.2.1 Сколькими способами можно переставить буквы в слове “математика”.

Решение:В слове “математика” есть повторяющиеся буквы: “м” – 2 раза, “а” – 3 раза, “т” – 2 раза, “е” – 1 раз, “и” – 1 раз, “к” – 1 раз. Порядок расположения элементов имеет значение (это очевидно, так как если переставить местами 2 буквы, то получатся разные слова) и все элементы используются, следовательно, это перестановка с повторениями.

Таким образом, в слове “математика” можно переставить буквы 151200 способами.

Опр 4.2.2Сочетания изnэлементов, в каждое из которых входитmэлементов, причем один и тот же элемент может повторяться в каждом сочетании любое число раз, но не болееm, называются сочетаниями с повторениями. Число сочетаний с повторениями вычисляется по формуле:

Пример 4.2.2на почте продаются открытки 10 сортов. Сколько вариантов существует для покупки 12 открыток.

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

.

Таким образом, из 10 открыток можно выбрать набор из12 штук 293930 способами.

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

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

Решение:Так как порядок расположения элементов важен и не все элементы используются в данном соединении, то это размещение. А так как всего 8 гнезд, а флажков 2 вида (голубой и красный), то они будут повторяться, т.е. это размещение с повторением.

Таким образом, существует 256 способов украсить здание с 8 гнездами флажками двух цветов.

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

Лекция №17-18

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

1. Кортежи и декартово произведение множеств

Определение.

Пусть даны множества . Кортежем длины n составленным из элементов этих множеств называется конечная последовательность , где для всех k () имеем . Элемент называется k-ой координатой (или k-ой координатой) кортежа .

Пример 1.

Из множеств A = {a,b,c} и B = {1,2} можно составить 6 картежей длины 2: (a,1), (a,2), (b,1), (b,2), (c,1), (c,2).

Определение.

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

Определение.

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

Пример.

Пусть даны два множества = {1,2,3} и B = {x,y}. Тогда

,

.

Этот пример показывает, что, вообще говоря, декартовы произведения и различны, хотя они содержат одинаковое число элементов. Различны и множества , и – первое состоит из троек (a,b,c), второе – из пар вида ((a,b),c), а третье – из пар вида (a,(b,c)), где во всех трех случаях , , .

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

2. Основные законы комбинаторики. Правило суммы.

Пример 2.

Если на блюде лежат 7 яблока и 4 груши, то выбрать один плод можно 7+4=11 способами. В общем виде: если элемент a можно выбрать m способами, а элемент b n способами, причем любой выбор элемента a будет отличен от выбора элемента b, то выбор a или b можно сделать m+n способами. На языке теории множеств это правило формулируется следующим образом.

Теорема I.

Если пересечение конечных множеств A и B пусто , то число элементов в их объединении равно сумме чисел элементов множеств A и B:

. (1)

Следствие.

Если конечные множества попарно не пересекаются, то есть если при , то справедливо равенство

. (2)

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

Теорема II.

Для любых конечных множеств A и B верно равенство

. (3)

Формула (3) является частным случаем более общей формулы

, (4)

которую называют формулой включений и исключений. При m = 3 имеем число элементов

. (5)

Пример 2.

В группе обучается 42 студента. Из них 16 участвуют в секции по легкой атлетике, 24 – в футбольной секции, 15 – в шахматной секции, 11 – в секции по легкой атлетике и в футбольной, 8 легкоатлетической и шахматной, 12 – в футбольной и шахматной, а 6 во всех трех секциях. Остальные студенты увлекаются только туризмом. Сколько туристов является туристами.

Решение.

Пусть V – множество всех студентов, А – число студентов в секции по легкой атлетике, В – футбольной, С – шахматной, D – туристической. По условию имеем причем .

n(V)=42, n(A)=16, n(B)=24, n(C) = 15, n() = 11, n() = 8,

n() = 12, n() = 6.

По формуле (5) получаем .

Поэтому .

Ответ: туризмом занимается 12 студентов.

3. Правило произведения

Теорема 1.

Если множества A и B конечны, то число пар в их декартовом произведении равно произведению чисел элементов этих множеств.

. (6)

Доказательство.

Множество состоит из пар вида (a,b), где , . Если и , то эти пары можно записать в виде следующей таблицы:

Число этих пар равно , то есть. С помощью метода математической индукции формула обобщается на любое число множеств.

Теорема 2.

Если множества конечны, то справедливо равенство

. (7)

Пример.

Сколько номеров, состоящих из двух букв, за которыми идут 5 цифр можно составить используя 32 буквы и 10 цифр?

Решение.

Обозначим множество из 32 букв через A, а множество из 10 цифр через B. Каждый номер требуемого вида является кортежем из декартова произведения , , .

По формуле (7) .

Обобщение теоремы 2.

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

Основные формулы комбинаторики.

1. Размещения с повторениями.

Определение.

Кортежами длины k составленные из элементов m – элементного множества X называют размещениями с повторениями из m элементов по k. Число этих кортежей обозначают (буква A от французского слова arrangement – размещение. Черта сверху указывает на возможность повторения элементов).

. (8)

Пример.

Сколько пятизначных номеров можно составить из 9 цифр 1,2,3,4,5,6,7,8,9?

Решение.

Такие номера являются кортежами длины 5, составленными из элементов множества X = {1,2,3,4,5,6,7,8,9}. По формуле (8) их число равно .

2. Размещения без повторений.

Определение

Упорядоченное множество длины k составленное из элементов m – элементарного множества X называют размещениями без повторений из m элементов множества X по k и обозначают . Число размещений без повторений из m элементов по k находится по формуле

. (9)

Пример.

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

Решение.

Любой такой выбор является размещением без повторений из 40 элементов по 3.

.

3. Перестановки без повторений.

Определение.

Перестановками без повторений из m элементов называют размещения без повторений из этих элементов по m. Число перестановок из m элементов обозначают от французского слова permutation – перестановка и находятся по формуле

. (10)

4. Сочетания без повторений

Определение.

Будем строить из элементов множества X не кортежи, а подмножества. k – элементные подмножества m – элементного множества X называют сочетаниями без повторений из элементов этого множества по k. Их число обозначают . От французского слова combination – комбинация.

. (11)

Пример.

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

Решение.

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

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

Перестановкой с повторениями состава из букв называют любой кортеж длины , в который буква входит раз, …, а буква входит раз. Число таких перестановок обозначают .

. (1)

Пример.

Кортеж (a,b,a,a,c,b,b,b,c) является перестановкой с повторениями из трех букв а, четырех букв b и двух букв с. Его состав выражается кортежем (3,4,2). Мы считаем из букв a,b,c буква a – первая, b – вторая, c – третья.

6. Сочетания с повторениями

Пусть имеются предметы m видов и из них составляют набор, состоящий из k – элементов. Два таких набора считаются одинаковыми в том и только в том случае, когда они имеют одинаковый состав. Такие наборы назовем сочетаниями с повторениями из m элементов по k. Число сочетаний с повторениями из m элементов по k обозначим ,

. (2)

Пример.

Сколько наборов из семи пирожных можно составить, если в продаже имеются четыре сорта пирожных?

Решение.

Сочетания и биномиальные коэффициенты

Рассмотрим формулы

1) .

2) .

3) .

4) Можно показать, что .

Коэффициенты при каждом члене можно найти при помощи «треугольника Паскаля»

Если n – большое число, то ясно, что по треугольнику Паскаля вычислять коэффициенты правой части долго. Поэтому желательно знать общую формулу вычисления . Эта формула носит название формулы бинома Ньютона и имеет вид

, (3)

где .

Применим формулу бинома Ньютона для .

Пример.

В почтовом отделении продают открытки 10 сортов. Сколькими способами можно купить в нем: а) 12 открыток? б) 8 открыток? в) 8 различных открыток?

Решение.

а)

б)

в)

Домашнее задание.

1. У филателиста есть 8 различных марок на космическую тему и 10 различных марок на спортивную тему. Сколькими способами он сможет наклеить 3 марки одного вида и 3 марки второго вида в альбом на 6 пронумерованных мест?

2. В лаборатории работают 8 физиков и 10 химиков. Надо создать рабочие группы по трем темам. В первую группу должны войти 4 физика, во вторую 5 химиков, а третья должна состоять из 3 человека которые могут быть как физиками, так и химиками. Сколькими способами можно создать такие группы.

3. Доказать, что (правило Паскаля).

7

Методическая разработка по алгебре (6 класс) по теме: Комбинаторика,правила суммы и произведения.

Комбинаторика, правила суммы и произведения

С.Д. Бобровская, Пушкинский район,

школа № 403

Цели урока: введение понятия комбинаторики; знакомство с основными правилами комбинаторики; развитие логического мышления.

План урока:

— введение понятия комбинаторики; подготовительная задача;

— правило суммы;

— правило произведения;

— решение задач;

— подведение итогов;

— домашнее задание.

Комбинаторика – это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основные вопросы, задаваемые в комбинаторных задачах: сколькими способами? сколько вариантов? и т.п.

Подготовительная задача:

На блюде 7 яблок, 4 мандарина и 5 груш. Найдите количество способов, которыми можно взять с блюда

а) один плод;

б) грушу и мандарин;

в) яблоко и грушу;

г) яблоко и мандарин;

д) два фрукта с различными названиями.

Задачу а) учащиеся, конечно, решат без труда. Каждый понимает, что если на блюде 7 яблок, то взять любое из них можно семью различными способами. Тогда взять с блюда один плод можно 7+4+5=16 способами.

Для решения задачи б) можно изобразить «дерево возможностей»:

г

г

г

г

г

м

м

м

м

м

м

        м

м

м

м

м

м

м

м

м

м

м

м

м

м

Как видно из рисунка, грушу и мандарин можно взять с блюда 20 различными способами. Учащиеся сами сообразят, что этот результат можно получить, умножив 5 на 4. Тогда они легко самостоятельно решат задачи в) и г): в) 7∙5=35; г) 7∙4=28.

Теперь несложно решить и задачу д). Пары фруктов с разными названиями – это груша и мандарин, яблоко и груша, яблоко и мандарин. Поэтому, чтобы найти, сколькими способами можно взять с блюда два фрукта с различными названиями, нужно просто сложить результаты задач б), в) и г): 20+35+28=83.

Правило суммы: если элемент a из некоторой совокупности элементов можно выбрать m различными способами, и независимо от этого элемент b – n способами, то выбрать a или b можно n+m способами.

Правило произведения: если элемент a из некоторой совокупности элементов можно выбрать m различными способами, и независимо от этого элемент b – n способами, то выбрать a и b вместе можно n∙m способами.

Задачи:

1. Сколько существует

а) двузначных

б) трехзначных

в) n-значных натуральных чисел?

Решение:

а) 9∙10=90

б) 9∙10∙10=900

в) 9∙10∙10∙…∙10=9∙10n-1

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

Решение:

Эта задача аналогична задаче на составление семизначного числа. Отличие состоит лишь в том, что число не может начинаться с нуля, а телефонный номер – может. Поэтому семизначных номеров 107=10000000.

Ответ: десять миллионов абонентов могут обслуживаться в одной сотовой сети.

3. Каково максимальное количество абонентов могут обслужить операторы всех сотовых сетей?

Решение:

Номер сети состоит из трех знаков, причем первая цифра во всех сетях одинаковая: 9. Поэтому эта задача сводится к решению задачи на составление девятизначного числа, которое может начинаться с нуля. Поэтому все сотовые сети могут обслужить 109=1000000000 абонентов.

Ответ: один миллиард абонентов.

4. Каких чисел — полиандромов больше, семизначных или восьмизначных?

Решение:

Полиандромы – это такие числа, которые читаются одинаково слева направо и справа налево. У семизначного числа – полиандрома на первой позиции может стоять любая из девяти цифр, на второй, третьей и четвертой позициях – любая из десяти. А вот на пятой,  шестой и седьмой позициях цифры уже зафиксированы. Таким образом, по правилу произведения семизначных чисел – полиандромов 9∙10∙10∙10∙1∙1∙1=9000. Восьмизначных чисел – полиандромов 9∙10∙10∙10∙1∙1∙1∙1=9000. Так что семизначных и восьмизначных чисел – полиандромов поровну.

Ответ: поровну.

5. Сколько существует всевозможных четырехзначных чисел, состоящих из цифр 0, 1, 2, 3, 4, 5,  7 и содержащих ровно одну тройку?

Решение:

Цифра «3» может занимать любую из четырех позиций. В силу того, что для записи используются всего лишь семь цифр, то на первой позиции, если там не тройка, может находиться любая из пяти цифр, так как нуль не может стоять на первой позиции, а тройка зафиксирована. На остальных позициях, где нет тройки, может находиться любая из шести цифр. Изобразим схему заполнения позиций:

3   6   6   6

5   3   6   6

5   6   3   6

5   6   6   3

В таком случае, по правилу произведения четырехзначных чисел, начинающихся с тройки, 63, а с тройкой во второй, третьей и четвертой позициях 5∙62. Таким образом, всего четырехзначных чисел, составленных из данных цифр и содержащих ровно одну тройку по правилу сложения 63+5∙62∙3=36∙(6+15)=36∙21=756.

Ответ: 756.

6. Сколько существует четырехзначных чисел, кратных пяти и состоящих из цифр 0, 2, 5, 7, 9, если каждое число состоит из различных цифр?

Решение:

Числа, кратные пяти, оканчиваются на «0» или «5». На первой позиции может находиться любая из предложенных пяти цифр, кроме нуля и зафиксированной последней цифры. Изобразим схему заполнения позиций:

4   3   2   0

3   3   2   5

Таким образом, чисел, составленных из предложенных цифр и оканчивающихся на «0» по правилу произведения 4∙3∙2=24, а оканчивающихся на «5» 3∙3∙2=18. Всего чисел, кратных пяти, по правилу сложения 24+18=42.

Ответ: 42.

7. Сколько существует шестизначных чисел, в записи которых присутствует хотя бы одна четная цифра?

Решение:

По правилу произведения всего шестизначных чисел 9∙105=900000. Для составления чисел, в которых нет ни одной четной цифры, используются пять цифр, поэтому таких чисел 56=15625. Таким образом, чтобы найти количество шестизначных чисел, в которых присутствует хотя бы одна четная цифра, нужно из числа всех возможных вариантов вычесть число неблагоприятных:  900000-15625=884375.

Ответ: 884375.

Домашнее задание:

Домашняя самостоятельная работа:

Сколько можно составить трехсимвольных сочетаний из 33 букв русского алфавита, если

а) в каждой тройке буквы различны;

б) буквы не обязаны различаться;

в) никакие две одинаковые буквы не идут подряд;

г) первая и третья буквы – согласные, вторая – гласная;

д) ровно одна из трех букв – гласная?

КОМБИНАТОРИКА ПРАВИЛО СУММЫ И ПРАВИЛО ПРОИЗВЕДЕНИЯ Основной

КОМБИНАТОРИКА

ПРАВИЛО СУММЫ И ПРАВИЛО ПРОИЗВЕДЕНИЯ Основной вопрос заключается в подсчете выборок (комбинаторных объектов) с определенными свойствами Правило умножения. Если элемент А можно выбрать из некоторого множества m способами и если после каждого такого выбора элемент B можно выбрать n способами, то пара элементов (А, В) в указанном порядке может быть выбрана (m×n) способами. Пример 1. Из пункта А в пункт В ведут 3 дороги, а из пункта В в пункт С – 4 дороги. Сколькими способами можно совершить поездку из А в С через В?

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

Правило сложения. Если элемент А можно выбрать из некоторого множества m способами, а другой элемент B – n способами, причём выборы А и В таковы, что взаимно исключают друга и не могут быть выбраны одновременно, то выбор какого-либо одного из этих элементов (либо А, либо В) можно осуществить (m+n) способами. Пример 1. Пусть из города A в город B можно добраться одним авиамаршрутом, двумя железнодорожными маршрутами и тремя автобусными маршрутами. Сколькими способами можно добраться из города A в город B?

Пример 2. В магазине электроники продаются три марки телевизоров и два видеомагнитофонов. У покупателя есть возможности приобрести либо телевизор, либо видеомагнитофон. Сколько способами он может совершить одну покупку? Пример 3. В урне содержится 3 синих, 5 красных и 2 белых шара. Сколькими способами можно вытащить из урны либо два белых шара, либо два цветных шара, из которых один синий, а другой – красный? Пример 3. Имеется 6 различных конвертов без марок, 4 различные марки и 3 различных конверта с марками. Сколькими способами можно выбрать конверт с маркой для отправки письма?

Пример 1. В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить 4 различных фотографии. Сколькими способами это можно сделать, если ни одна страница газеты не должна содержать более одной фотографии? Пример 2. Сколькими способами можно составить трехцветный полосатый флаг, если имеются ткани пяти различных цветов? Решите эту же задачу при условии, что одна полоса должна быть красной. Пример 3. Сколькими способами 10 человек можно поставить парами в ряд? Пример 4. В цехе работают 8 токарей. Сколькими способами можно поручить трем из них изготовление различных видов деталей (по одному виду на каждого).

Пример 5. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост? Пример 6. Из 10 книг выбирают 4 для рассылки по разным адресам. Сколькими способами это можно сделать? Пример 7. Сколькими способами можно опустить 5 писем в 11 почтовых ящиков, если в каждый ящик опускают не более одного письма? Пример 8. Студенту необходимо сдать 5 экзаменов в течение 12 дней. Сколькими способами можно составить расписание экзаменов, если в течение дня он может сдать не более одного экзамена?

Пример 1. Сколькими способами можно обить 6 стульев тканью, если имеются ткани 6 различных цветов и все стулья должны быть разного цвета. Пример 2. Дачник выделил на своём участке семь грядок для выращивания овощей, т. к. хочет иметь свои помидоры, огурцы, перец, лук, чеснок, салат и кабачки. Каждый вид должен иметь отдельную грядку. Сколькими способами он может расположить грядки для посадки? Пример 3. Пассажирский поезд состоит из трех багажных вагонов и восьми купированных. Сколькими способами можно сформировать состав, если багажные вагоны должны находиться в его начале? Пример 4. В первенстве края по футболу участвуют 11 команд. Сколько существует различных способов распределения мест в таблице розыгрыша, если на первое место могут претендовать только 4 определенные

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

Пример 1. Сколькими способами можно составить комиссию в составе из трех человек из имеющихся 9 человек, 4 женщин и 5 мужчин, если: а) не важен пол членов комиссии; б) комиссия должна состоять из двух женщин и одного мужчины. Пример 2. Сколькими различных правильных дробей можно составить из чисел 1, 2, 3, 5, 7, 11, 13, берущихся попарно? Пример 3. Сколькими способами можно выбрать 5 делегатов из состава конференции, на которой присутствуют 15 человек? Пример 4. Компания из 15 человек разделяется на две группы, одна из которых состоит из 6 человек, а другая – из 9 человек. Сколькими способами это можно сделать?

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

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

Пример 1. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус? Пример 2. У мамы было 2 одинаковых яблока, 3 одинаковых груши и 4 одинаковых апельсина. Каждый день она давала ребенку по одному фрукту. Сколькими способами она могла это сделать? Пример 3. Сколькими способами можно расположить в ряд две зелёные и четыре красные лампочки?

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