Встретились 6 друзей

Встретились 6 друзей

Пусть множество A состоит из p элементов, а множество B состоит из q элементов. Составим новое множество A ? B , состоящее из всех упорядоченных пар ( a , b ) , где a A и b B .

Множество A ? B называется декартовым произведением множеств A и B .

Очевидно, что множество A ? B содержит pq элементов.

Правило произведения : декартово произведение множеств A и B , содержащих p и q элементов соответственно, содержит pq элементов.

Для нас будет удобна следующая формулировка правила произведения.

Пусть некоторый объект a можно выбрать p способами, а объект b – q способами. Тогда количество способов, которыми можно выбрать упорядоченную пару ( a , b ) , равно pq .

Правило произведения легко обобщается на большее число объектов.

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

Чёрную ладью можно поставить на шахматную доску p = 64 различными способами. Независимо от выбора поля чёрная ладья бьёт 15 полей, поэтому для второй ладьи остаётся 64 – 15 = 49 полей, то есть q = 49. Всего число возможных способов, по правилу произведения, равно pq = 64 • 49 = 3136.

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

Число 10 можно представить в виде суммы двух слагаемых девятью различными способами: 1 + 9, 2 + 8, . 4 + 6, 5 + 5, 6 + 4, . 9 + 1. Заметим, что решения ( a , b ) и ( b , a ) мы считаем различными, и потому нам важен порядок, в каком число 10 представлено в виде суммы. Аналогично, число 5 можно представить в виде суммы двух натуральных слагаемых четырьмя различными способами. Каждому решению ( x , y ) можно выбрать в пару четыре решения ( u , v ) . По правилу произведения, количество решений системы равно 9 • 4 = 36.

Пусть снова множество A состоит из p элементов, а множество B – из q элементов. Предположим, что множества A и B не пересекаются. В этом случае множество A B состоит из p + q элементов.

Это соображение и носит название правила суммы .

Обычно в задачах применяют оба правила вместе.

Встретились 6 друзей, и каждый пожал руку каждому. Сколько всего было рукопожатий?

Каждый пожал руку каждому, то есть каждый человек сделал 5 рукопожатий. Но общее количество рукопожатий получается по правилу суммы: n 1 + n 2 + . + n 6 = 6 ? 5 = 30 . Учтём теперь то, что каждое рукопожатие мы посчитали дважды, и получим в результате 15 рукопожатий.

Источник:
Встретились 6 друзей
Пусть множество A состоит из p элементов, а множество B состоит из q элементов. Составим новое множество A ? B , состоящее из всех упорядоченных пар ( a , b ) , где a A и b B .
http://mathematics.ru/courses/algebra/content/chapter4/section2/paragraph1/theory.html

Выбор нескольких элементов

В предыдущем параграфе все примеры и упражнения сводились к выбору одного элемента из данного множества и подсчету количества таких выборов. А если необходимо выбрать большее число элементов данного множества? Начнем со случая выбора двух элементов.

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

Решение. Рассмотрим таблицу результатов встреч размером 7×7 (рис. 4.4).

Так как никакая команда не играет сама с собой, то клетки по диагонали надо закрасить. Тогда в подсчете числа встреч будет участвовать ровно 7 2 — 7 = 7(7 — 1) = 42 клетки. В результате закрашивания таблица разделилась на две половинки, в них результаты встреч команд дублируются. Поэтому если мы разделим оставшиеся 42 клетки на две равные половины, то получим число всех проведенных игр.

Коротко решение задачи выглядит так:

Около 2500 лет тому назад древнегреческие математики находили сумму 1 + 2 + 3 + . + (п – 1) + п с помощью примерно таких же рассуждений. Сначала они рисовали клетчатую лесенку, в основании которой – полоса из п клеток, над ней полоса, в которой (п – 1) клетка, затем полоса с (п – 2) клетками, и т. д.; в предпоследней строке стояли две клетки, а наверху – одна клетка. Правее они рисовали ту же лесенку, но в перевернутом виде: внизу – одна клетка, над ней – две, затем – три клетки, . а последняя строка состоит из п клеток (рис. 4.5).

Затем, сдвинув эти лесенки вместе, получали прямоугольник из п строк и (п + 1) столбца (рис. 4.6).

Число клеток в этом прямоугольнике равно п(п + 1). Значит, в каждой из двух равных между собой лесенок находится п(п + 1) ровно клеток.

Получилась замечательная формула для суммы первых п натуральных чисел:

Замечание. С помощью этой формулы можно несколько по иному найти сумму первых п членов арифметической прогрессии:

.

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

Пример 11. Встретились 6 друзей и каждый пожал руку каждому своему другу. Сколько было рукопожатий?

Первый способ. Можно, как и в примере 1, составить таблицу рукопожатий 6 друзей. Затем, рассуждая аналогично, получим, что общее число рукопожатий равно .

Второй способ. Условно перенумеруем друзей. Первый поздоровался со вторым, третьим, . шестым. Всего 5 рукопожатий. Для второго неучтенными остались рукопожатия с третьим, четвертым, пятым, шестым. Всего 4 рукопожатия, и т. д. (рис. 4.7). Получаем, что рукопожатий было всего 5 + 4 + + 3 + 2 + 1 = 15. Ответ: 15.

Подведем промежуточный итог, оформив его в виде теоремы.

ТЕОРЕМА (о выборках двух элементов). Если множество состоит из п элементов, то у него имеется подмножеств, состоящих из двух элементов.

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

Пример 12. В классе 27 учеников. К доске нужно вызвать двоих. Сколькими способами это можно сделать, если: а) первый ученик должен решить задачу по алгебре, а второй – по геометрии; б) они должны быстро стереть с доски?

Решение. Для стирания с доски порядок вызова учеников не важен, т. е., к примеру, вызов Коли и затем Кати ничем не отличается от вызова Кати и затем Коли. А вот в первом случае порядок существенен (по крайней мере, для Кати и Коли). Тут применимо правило умножения. Учитель сначала вызывает решать алгебраическую задачу одного из 27 учеников, а затем независимым образом вызывает одного из оставшихся 26 учеников решать задачу по геометрии. Получается 27 • 26 = 702 способа вызова.

Если во втором случае начать считать, как и в первом, то любую пару учеников мы посчитаем дважды. Например, сначала Коля, потом Катя, или сначала Катя, потом Коля. Значит, количество вызовов без учета порядка будет ровно в два раза меньше, чем количество вызовов с учетом порядка. Ответ: а) 702; 6) 351.

Это рассуждение верно и в общем случае выбора двух элементов из п данных. Оказывается, что всегда количество выборок двух элементов без учета порядка будет ровно в два раза меньше, чем количество выборок с учетом порядка. На рисунке представлена соответствующая схема (рис. 4.8).

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

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

.

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

или .

Символы и читаются в русской транскрипции так: «а из эн по эм» и «цэ из эн по эм» соответственно.

Пример 13. В классе 27 учеников, из которых нужно выбрать троих. Сколькими способами это можно сделать, если: а) первый ученик должен решить задачу, второй – сходить за мелом, третий – пойти дежурить в столовую; б) им следует спеть хором?

Решение. Рассуждаем, как в примере 3. В первом случае важен порядок вызова учеников и применимо правило умножения. Один из 27 учеников идет решать задачу. Один из оставшихся 26 учеников идет за мелом, а один ученик из оставшихся 25 будет дежурным в столовой. Получается: 27 • 26 • 25 = 17550 способов вызова.

Во втором случае начнем действовать, вызывая учеников по порядку. Можно сначала вызвать Пашу, затем Вову и потом — Асю. Обозначим этот вариант (ПВА). Можно вызывать этих же ребят в другом порядке. Например, сначала Асю, затем Пашу и потом — Вову (АПВ). Буквы А, П, В можно расставить по порядку ровно Р3 = 3! способами. Во всех этих случаях состав хора будет одним и тем же. Значит, каждый состав хора при подсчете, учитывающем порядок вызова учеников, мы возьмем 3! раз. Поэтому количество различных составов хора в 3! раз меньше количества всех вызовов по порядку.

Итак, число способов, при которых порядок выбора трех элементов из 27 не важен, в 3! раз меньше числа способов, при которых порядок выбора трех элементов из 27 важен. Остается лишь учесть, что 3! = 3 • 2 • 1 = 6, и получить ответ: = 2925 способов.

Ответ: а) 17550; б) 2925.

Пример 14. «Проказница Мартышка, Осел, Козел и косолапый Мишка затеяли сыграть квартет». Мишке поручили принести со склада 8 каких-нибудь попавшихся под лапы музыкальных инструментов из имеющихся 13 инструментов. Сколько способов выбора есть у Мишки?

Решение. По условию порядок выбора не важен. Значит, нам требуется найти количество всех выборок 8 элементов из 13 данных без учета порядка, то есть число сочетаний из 13 элементов по 8:

.

Теперь посмотрим на число . С одной стороны, это количество выборок одного элемента из п данных, т. е., несомненно, = п. С другой стороны, по определению, . Значит, и здесь имеется полное соответствие. А теперь посмотрим на число . По определению это количество выборок п элементов из п данных. Но такой выбор единственен, то есть =1. Если попытаться применить формулу из определения, то получим .

Возникает вопрос: что же такое «ноль факториал»? Математики поступили просто. Чтобы сохранить красивую и очень удобную формулу для чисел при любых целочисленных значениях k (0

185.212.148.159 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Источник:
Выбор нескольких элементов
В предыдущем параграфе все примеры и упражнения сводились к выбору одного элемента из данного множества и подсчету количества таких выборов. А если необходимо выбрать б о льшее число элементов
http://studopedia.ru/3_40258_vibor-neskolkih-elementov-razmeshcheniya-sochetaniya.html

Подготовка к олимпиадам по информатике

Блог содержит уроки для подготовки школьников к олимпиадам по информатике

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

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

Пример. Всевозможные размещения с повторениями из трех элементов a, b, c по 2:

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

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

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

3. Расписание одного дня состоит из 5 уроков. Определить число вариантов расписания при выборе из 11 дисциплин.

4. Шифр сейфа состоит только из 6 цифр, которые должны набираться последовательно и могут повторяться. Чему в этом случае равно общее число всех возможных комбинаций шифра?

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

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

7. Сколькими способами из колоды в 36 карт можно выбрать 3 карты?

9. Сколько существует четырёхзначных пин-кодов?

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

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

Условие «выбрать 2-х человек одного пола» подразумевает, что необходимо выбрать двух мальчиков или двух девочек:

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

Обозначим данное число тремя звёздочками: ***
Комбинации будем считать по разрядам – слева направо:
В разряд сотен можно записать любую из цифр (1, 2, 3, 4, 5, 6, 7, 8 или 9). Ноль не годится, так как в этом случае число перестаёт быть трёхзначным.
В разряд десятков («посерединке») можно выбрать любую из 10-ти цифр: .

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

7. Сколько различных трёхзначных чисел можно составить при помощи цифр 4, 7, 9? (Цифры в записи числа не повторяются).
Сколько различных трёхзначных чисел можно составить с помощью цифр 1, 3, 7? (Цифры могут повторяться).

Источник:
Подготовка к олимпиадам по информатике
сочетания повторения размещения комбинаторика
http://pinskolimp.blogspot.com/p/blog-page_29.html

Презентация на тему: Комбинаторика

Решение задач тема:»Комбинаторика»

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

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

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

Решение Различными будем считать те делегации, которые отличаются хотя бы одним членом. Таким образом, нужно вычислитьОтвет:455 способов

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

Решение В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.Ответ: 15504 варианта

Встретились 6 друзей, и каждый пожал руку каждому. Сколько всего было рукопожатий?

Решение Каждый пожал руку каждому, то есть каждый человек сделал 5 рукопожатий. Но общее количество рукопожатий, получается по правилу суммы: n1 + n2 + . + n6 = 6 ? 5 = 30. Учтём теперь то, что каждое рукопожатие мы посчитали дважды, и получим в результате 15 рукопожатий

У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

Решение Так как надо порядок следования книг не имеет значения, то выбор 2 книг — сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2 книги. Значит всего по правилу произведения возможно 21*36=756 вариантов

Источник:
Презентация на тему: Комбинаторика
Решение задач тема:»Комбинаторика» Сколькими способами можно распределить уроки в шести классах между тремя учителями, если каждый учитель будет преподавать в двух классах? Решение Первый
http://ppt4web.ru/matematika/kombinatorika2.html

Примеры решений задач по комбинаторике

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

Просмотр содержимого документа
«Примеры решений задач по комбинаторике»

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

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

Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары А и В можно осуществить

Задача 1. В магазине «Все для чая» есть 6 разных чашек и 4 разных блюдца. Сколько вариантов чашки и блюдца можно купить?

Чашку мы можем выбрать 6-ю способами, а блюдце 4-я способами. Так как нам надо купить пару чашку и блюдце, то это можно сделать 6 · 4 = 24 способами (по правилу произведения).

Задача 2. При встрече каждый из друзей пожал другому руку. Сколько всего было рукопожатий, если встретились 6 друзей?

O формуле для числа сочетаний.
Как известно, деление может быть обозначено разными символами:
__, /, :
Косую черту и двоеточие удобно использовать для записи формулы в одну строку, что здесь и сделано для экономии места в таблице. Горизонтальную черту используют для записи дроби. Если формулу для числа сочетаний записать дробью, то хорошо видно, как она сокращается.

В одном рукопожатии равноправно участвуют два человека. 6 друзей объединялись в группы по 2 без учёта порядка следования. Такие группировки (выборки) называются сочетаниями. Число сочетаний определяем по формуле
С6 2 = 6!/2!/(6 — 2)! = 6!/2!/4! = 5·6/2 = 15.

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

Рассмотрим решение нескольких задач на разные виды соединений без повторений.

Задача 3. Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе повторяться не могут.

Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок учитывается и не все элементы одновременно выбираются. Значит, это соединение – размещение из 7 элементов по 3. Воспользуемся формулой для числа размещений: A73 = 7(7 – 1)(7 – 2) = 7 · 6 · 5 = 210 чисел.

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

На первый взгляд эта задача такая же, как и предыдущая, но сложность в том, что надо не учитывать те соединения, которые начинаются с нуля. Значит необходимо из существующих 10-ти цифр составить все семизначные номера телефонов, а потом от полученного числа отнять количество номеров, начинающихся с нуля. Формула будет иметь вид:

A107 – A96 = 10 · 9 · 8 · 7 · 6 · 5 · 4 – 9 · 8 · 7 · 6 · 5 · 4 = 544 320.

Задача 5. Сколькими способами можно расставить на полке 12 книг, из которых 5 книг – это сборники стихотворений, так, чтобы сборники стояли рядом?

Сначала примем 5 сборников условно за одну книгу, потому что они должны стоять рядом. Так как в соединении существенным есть порядок, и все элементы используются, значит это перестановки из 8 элементов (7 книг + условная 1 книга). Их количество Р8. Далее будем переставлять между собой только сборники стихотворений. Это можно сделать Р5 способами. Поскольку нам нужно расставить и сборники, и другие книги, то воспользуемся правилом произведения. Следовательно, Р8 · Р5 = 8! · 5!. Число способов будет большим, поэтому ответ можно оставить в виде произведения факториалов.

Задача 6. В классе 16 мальчиков и 12 девочек. Для уборки территории возле школы нужно 4 мальчика и 3 девочки. Сколькими способами можно их выбрать со всех учеников класса?

Сначала отдельно выберем 4 мальчика из 16 и 3 девочки из 12. Так как порядок размещения не учитывается, то соответственные соединения – сочетания без повторений. Учитывая необходимость одновременного выбора и мальчиков, и девочек, используем правило произведения. В результате число способов будет вычисляться таким образом:

С164 · С123 = (16!/(4! · 12!)) · (12!/(3! · 9!)) = ((13 · 14 · 15 · 16) / (2 · 3 · 4)) ·((10 · 11 · 12) / (2 · 3)) = 400 400.

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

На пьедестале почёта находятся 3 команды из 10, и для них очень существенно, кто какое место занял, т.е. порядок следования. Составление групп с учетом порядка следования — размещения. Число размещений определяем по формуле
А10 3 = 10!/(10 — 3)! = 10!/7! = 8·9·10 = 720.
Другой способ решения с использованием И-правила, как в задаче 2б. Однако, чем больше выборка, тем удобнее сразу применять готовую формулу.

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

Источник:
Примеры решений задач по комбинаторике
Большинство комбинаторных задач решается с помощью двух основных правил – правила суммы и правила произведения.
http://multiurok.ru/files/primiery-rieshienii-zadach-po-kombinatorikie.html

COMMENTS