Сколькими способами можно выбрать 3 различных карандаша из имеющихся 5 карандашей разных цветов

Обновлено: 04.07.2024

Пусть – конечное множество, набор элементов ( ) из A называется –выборкой.

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

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

Неупорядоченная –выборка без повторений называется -сочетаниемили сочетанием из n элементов по k, другими словами, это k–элементное подмножество множества А.

Упорядоченная –выборка без повторений называется –размещением (перестановкой) или размещением из n элементов по k.

Неупорядоченная –выборка с повторениями называется –сочетанием с повторениями.

Упорядоченная –выборка с повторениями называется –размещением с повторениями. –размещение без повторений называется перестановкой из n элементов.

Например, рассмотрим множество . Составим сочетания из трех элементов по два: (a₁, a₂), (a₁, a₃), (a₂, a₃).

Все сочетания с повторениями из трех элементов по два представляют собой следующие (3,2)-выборки: (a₁, a₁), (a₁, a₂), (a₁, a₃), (a₂, a₂), (a₂, a₃), (a₃, a₃).

Далее выпишем все размещения из трех элементов по два без повторений: (a₁, a₂), (a₂, a₁), (a₂, a₃); (a₃, a₂), (a₁, a₃), (a₃, a₁).

Наконец, перестановки из трех элементов − это следующие упорядоченные без повторений (3,3)-выборки: (a₁,a₂,a₃), (a₁,a₃,a₂), (a₂,a₁,a₃), (a₂,a₃,a₁), (a₃,a₁,a₂), (a₃,a₂,a₁).

Число сочетаний, размещений и

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

Пусть – число всех –размещений с повторениями.

Доказательство. Пусть . Между множеством –размещений с повторениями и прямым произведением существует взаимно однозначное соответствие, т.е. они равномощны. По следствию теоремы 1 имеем , т.е. число всех размещений с повторениями из n по k равно .

Число всех –размещений обозначается через .

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

По правилу произведения получаем, что число всех –размещений равно .

Пусть – число всех перестановок из элементов.

Число всех –сочетаний обозначается через или . Эта величина называется биномиальным коэффициентом.

Доказательство. Рассмотрим –сочетание , эту неупорядоченную –выборку можно упорядочить способами ( в силу следствия теоремы 3). Если упорядочить каждое –сочетание, то получим все упорядоченные –выборки, т.е. . Отсюда получаем, что .

Задача 3. Сколько существует двоичных матриц с строками и столбцами, все строки которых различны?

Решение. Число различных двоичных упорядоченных наборов длины равно . Число всех двоичных матриц с строками совпадает с числом всех размещений из элементов по . Следовательно, по теореме3 получаем, что число матриц равно .

Задача 4. Сколькими способами из колоды в 36 карт можно вытащить 5 карт так, чтобы среди них были три карты червовой масти и две крестовой масти?

Решение. Всего в колоде имеем по 9 карт каждой из 4 мастей. Три карты червовой масти можем вытащить способами, а две карты крестовой масти можно вытащить способами. По правилу произведения получаем, что существует × способов вытащить из колоды 5 карт определенным образом.

Разбиение множества

Множества задают разбиение множества А, если объединение всех множеств равно А и все множества попарно не пересекаются, т.е. для всех .

Теорема 6. Число различных упорядоченных разбиений множества А мощности на подмножеств заданных мощностей равно .

Доказательство. Пусть ─ некоторое разбиение множества А на подмножеств, причем , , …, , для всех . Множество может быть выбрано способами, после выбора множество может быть выбрано способами и т.д. После выбора множеств множество может быть выбрано способами. Тогда по правилу произведений получаем, что общее число разбиений равно

Число называется полиномиальным коэффициентом и обозначается через .

Теорема 7. Если множества задают разбиение множества А, тогда

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

Следствие. Если множества не пересекаются, то

Это следствие представляет собой обобщенное правило суммы.

Задача 5. Дано множество U из 9 элементов. Каким числом способов в нем можно выбрать три подмножества A, B, C так, чтобы выполнялись условия: , .

Решение. Построим диаграмму Венна для искомых подмножеств A, B, C универсального множества U (см. рис.1). Введем обозначения: , , .

Заметим, что (это подмножество размещено в пяти ячейках диаграммы Венна – горизонтальная штриховка), (одна ячейка диаграммы – вертикальная штриховка) и (две ячейки диаграммы), причем подмножества задают разбиение множества U. Тогда по правилу произведения получаем, что число способов выбора подмножеств A, B, C равно .

§7. Перестановки с фиксированным числом повторений

Пусть . Упорядоченную −выборку c повторениями, где встречается раз для всех , назовем перестановкой с повторениями. Число всех таких перестановок обозначим через .

Доказательство. Пусть − множество номеров мест, на которых стоит элемент в перестановке a.

Число всех перестановок с повторениями совпадает с числом всех разбиений множества на подмножества , где . По теореме 6 получаем, что число всех разбиений –элементного множества на k подмножеств равно Отсюда получаем, что , что и требовалось доказать.

Задача 7. Сколько слов длины 9 в алфавите можно составить при условии, что , где обозначает число вхождений буквы в слово.

Решение. Если , тогда , и число слов, удовлетворяющих этому условию, равно числу двоичных последовательностей длины 9.

Если , тогда , и, рассматривая всевозможные разложения числа 5 на упорядоченную сумму двух слагаемых, получаем, что число слов в этом случае равно

Наконец, если , тогда , и число слов равно .

По правилу суммы получаем, что всего можно составить слов.

1) никакие две гласные не стояли рядом;

2) не менялся порядок гласных букв;

Решение. 1) Имеется перестановок согласных. Для каждого размещения согласных имеем 5 мест для размещения четырех гласных слова, тогда число всех размещений гласных букв слова равно . По правилу произведения получаем слов.

Задача 9. Сколькими способами можно разместить n одинаковых карандашей в k различных ящиках?

Решение. Перенумеруем ящики. Обозначим через − число карандашей, попавших в −ый ящик. Каждому размещению карандашей поставим в соответствие последовательность из нулей и единиц следующим образом: сначала записываем нулей, затем записываем единицу, далее пишем нулей, снова единицу, и т.д. Заканчивается последовательность нулями. Эта последовательность имеет нулей и единиц.

Например, при размещению, при котором в первом ящике 5 карандашей, во втором – нет карандашей, в третьем ящике – 3 карандаша, а в четвертом – 2 карандаша, соответствует последовательность 0000011000100.

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

Задача 10. Сколько решений в неотрицательных целых числах имеет уравнение

Решение. Пусть решение уравнения. Этому решению поставим в соответствие двоичный набор с n нулями и единицами следующим образом:

Таким образом, между множеством двоичных наборов с n нулями и единицами и множеством решений заданного уравнения устанавливается взаимно-однозначное соответствие, откуда число решений равно .

Задачи

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

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

3. Сколько существует девятизначных чисел, которые одинаково читаются как слева направо, так и справа налево? Сколько среди них четных?

4. В скольких точках пересекаются диагонали выпуклого n-угольника, если никакие три из них не пересекаются в одной точке?

5. В комнате n лампочек. Сколькими способами можно зажечь k лампочек? Сколько существует способов освещения комнаты?

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

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

8. Имеется n черных и m белых шаров. Сколькими способами можно их выложить в ряд так, чтобы никакие два черных шара не лежали рядом?

9. Студенту необходимо сдать 4 экзамена в течение 10 дней, причем известно, что в последний день он сдает экзамен. Сколькими способами он может это сделать?

10. Сколькими способами можно рассадить n гостей за круглым столом?

11. Имеется 4 типа открыток. Сколькими способами можно выбрать 10 открыток?

12. Сколькими способами n различных (одинаковых) предметов можно разложить в k одинаковых ящиков (разных ящиков)?

13. Сколько существует чисел не больше 100, которые не делятся ни на 2, ни на 3, ни на 5?

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

15. Сколькими способами можно выбрать три различных карандаша из имеющихся пяти карандашей разных цветов?

16. В группе 5 девочек и 7 мальчиков. Сколькими способами их можно разделить на 2 группы по 6 человек? Сколькими способами это можно сделать при условии, что в каждой группе должно быть хотя бы по одной девочке?

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

18. Имеется n абонентов телефонной сети. Сколькими способами можно одновременно соединить три пары?

19. Три студента сдают экзамен. Сколькими способами они могут сдать экзамен по пятибалльной системе? По семибалльной?

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

22. В конструкторском бюро все сотрудники знают хотя бы один из трех языков. Шестеро знают английский, шестеро – немецкий, семеро – французский. Четверо знают английский и немецкий, трое – немецкий и французский, двое – французский и английский. Один сотрудник знает все три языка.

Литература

1. Алексеев В. Е. Элементы комбинаторики. – Пособие для студентов заочного отделения, Нижний Новгород, 2001.

2. Алексеев В.Е., Киселева Л.Г., Смирнова Т.Г. Задачи по дискретной математике. – Методическая разработка, Нижний Новгород, 2003.

3. Виленкин Н. Я. Комбинаторика. – М.: Наука, 1969.

4. Гаврилов Г.Н., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1977.

5. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. – М.: Наука, 1977.

6. Киселева Л.Г. Элементы комбинаторики. – Методическая разработка, Нижний Новгород, 1990.

7. Киселева Л.Г., Смирнова Т.Г. Тождества и уравнения в алгебре множеств. – Методическая разработка, Нижний Новгород, 1999.

8. Марков А.А. Элементы комбинаторного анализа. – Методическая разработка, Горький, 1988.

9. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

СОДЕРЖАНИЕ

§1. Сочетания, размещения, перестановки 3

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

§3. Число сочетаний, размещений и размещений с повторениями 8

§4. Основные свойства биномиальных коэффициентов 11

§5. Бином Ньютона 12

§6. Разбиение множества 13

§7. Перестановки с фиксированным числом повторений 16

§8. Число сочетаний с повторениями 21

§9. Формула включений и исключений 22

Контрольные задания 32

Сочетания, размещения, перестановки

Пусть – конечное множество, набор элементов ( ) из A называется –выборкой.

Неупорядоченная –выборка с повторениями называется –сочетанием с повторениями.

Например, рассмотрим множество . Составим сочетания из трех элементов по два: (a₁, a₂), (a₁, a₃), (a₂, a₃).

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.

1. Выкидываем синий, берем зеленый. Остается 14 свободных карандашей. Сколькими способами из этих 14 можно выбрать 4 оставшихся?
2. Выкидываем зеленый, берем синий. Повторяем комбинации из п.1.
3. Выкидываем оба. Остается 13. Сколькими способами можно выбрать 5?

Есть и другой способ. Сначала считаем, сколько комбинаций можно сложить из всех карандашей. А затем вычитаем количество комбинаций, при который синий и зеленый вместе. Для этого берем оба карандаша (син и зел), считаем. сколькими способами можно выбрать 3 из оставшихся 14.

Чтобы посчитать, сколькими способами можно выбрать К карандашей из N, искользуем формулу сочетания СNK: N!/(K!*(N-K)!)

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

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

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

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

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

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

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

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

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

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

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

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

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

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

Пример 7.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k

Пример 8.

Презентация на тему: " Решение комбинаторных задач с помощью формулы сочетания." — Транскрипт:

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

2 ЦЕЛЬ: Решение комбинаторных задач с помощью формулы сочетания.

3 С ОЧЕТАНИЯ Комбинации из n элементов по k, отличающиеся друг от друга лишь составом элементов, называются сочетаниями из n элементов по k., (k n)

4 Задача : На столе лежат 5 разноцветных карандашей. Сколько существует способов для выбора 3 из них? Ответ: 10 способов

5 Задача: Из 12 учеников нужно выбрать 3 ученика на улусный новогодний бал. Сколькими способами можно сделать этот выбор? Ответ: 220 способов

6 Задача: Сколько диагоналей в выпуклом десятиугольнике? Ответ: 45 диагоналей.

7 Задача: Сколько существует способов выбора трёх ребят из 4-х желающих дежурить в столовой? Ответ: 4 способа.

8 Задача: В корзине имеются 15 груш и 7 яблок. Нужно выбрать 5 груш и 3 яблока. Сколькими способами это можно сделать? Ответ: способа. Подсчитаем способы выбора 5 груш: Подсчитаем способы выбора 3 яблок: =105105

Читайте также: