комбинаторика в каком классе проходят

Урок по теме «Элементы комбинаторики» в 5-м классе

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

I. Разминка (устный счет). Игра «Муха»

Учитель комментирует: Муха сидит на крайней левой клетке, она прыгнула на одну клетку вправо, на две клетки вниз и т.д. Задача учащихся – сложить числа тех квадратов, на которые «прыгает» муха. Например, 1 + 2 + 8 = 11. Данное упражнение в игровой форме способствует развитию внимания, готовит учащихся к активной познавательной деятельности на уроке. У игры могут быть варианты: учитель может задать другие действия для работы с клетками (вычитание, умножение и т.д.), в клетках могут находиться десятичные дроби, отрицательные числа и т.д.

II. Проверка домашнего задания

Основной педагогический акцент на уроке делается на проговаривание и обязательное устное пояснение решения задачи.

а) Задача. Можно ли рассадить 101 кролика в 100 клеток, что можно было бы утверждать, если бы было 35 клеток и 743 кролика.

Если 101 кролика рассадить 100 клеток, то по крайней мере в одной клетке будет 2 кролика. Понятно, почему: в худшем случае, если бы в каждой клетке сидело не больше одного кролика, в 100 клетках их было бы не больше 100.
А если было бы 35 клеток и 743 кролика, то что можно было утверждать? 743 : 35 = 21 (ост. 8). Значит, в худшем случае, если бы в каждой клетке сидело по 21 кролику, и еще 8 кроликов резвилось бы на свободе. Следовательно, если рассадить в клетки всех кроликов, то по крайней мере в одной клетке будет сидеть не меньше 22 кроликов.

б) Задача. В клетки таблицы по некоторому правилу записали не сколько чисел. Определить, что это за правило и заполнить 2 последние клетки таблицы.

в) Задача. Требуется определить арифметическое действие, с помощью которого с двух крайних чисел получено среднее, вместо знака «?» вставить пропущенное число.

а) 42 (47) 5 б) 36 (25) 11 в) 6 (66) 11 г) 48 (4) 12
31 (?) 8 48 (?) 12 5 (?) 12 100 (?) 5

Ответ: а) сложение, 39; б) вычитание, 36; в) умножение, 60; г) деление, 20.

г) Задача. Требуется найти пропущенные числа:

В каждой строчке последующее число в два раза больше предыдущего.

III. Актуализация знаний

1. Доклад по теме «Основной принцип комбинаторики»

Комбинаторика – один из разделов математики, который приобрел важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной техники, кибернетике.
При изучении комбинаторики целесообразно систематически использовать понятия множества и операции над множествами.
Человеку часто приходится иметь дело с задачами, в которых нужно посчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Сколькими способами можно расположить 50 человек в очереди в кассу кино? Сколькими способами могут быть распределены золотая, серебряная и бронзовые медали на чемпионате мира по футболу? Задачи такого типа называются комбинаторными.
С комбинаторными вычислениями приходится иметь дело представителям многих специальностей: ученому-химику при рассмотрении различных возможных типов связи атомов в молекулах, биологу при изучении различных возможных последовательностей чередования аминокислот в белковых соединениях, конструктору вычислительных машин, агроному, рассматривающему различные возможные способы посевов на нескольких участках, диспетчеру при составлении графика движения. Комбинаторные соображения лежат в основе решения многих задач важного раздела современной математики, посвященного изучению случайных явлений. Усиленный интерес к комбинаторике в последнее время обусловлен развитием кибернетики, вычислительной техники.

2. Сообщение содокладчика по теме «Основное правило комбинаторики»

Если некоторый выбор А можно осуществить Х различными способами, а для каждого из этих способов некоторый другой выбор В можно осуществить У способами, то выбор А и В (в указанном порядке) можно осуществить Х * У способами.

Задача: Из Киева до Чернигова можно добраться пароходом, поездом, автобусом, самолетом; из Чернигова до Новгорода-Северского – пароходом и автобусом. Сколькими способами можно осуществить путешествие по маршруту Киев – Чернигов – Новгород-Северский?
Если некоторые действия, (например, выбор пути от Киева до Чернигова) можно осуществить четырьмя различными способами, после чего другое действие (выбор пути от Чернигова до Новгорода-Северского) можно осуществить двумя способами, то два действия вместе (выбор пути от Киева до Чернигова, выбор пути от Чернигова до Новгрода-Северского) можно осуществить 4 * 2 способами.

3. Сообщение содокладчика по теме «Основное правило комбинаторики (правило умножения) в общем виде»

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

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

Решение. Первой цифрой числа может быть одна из 5 цифр 1, 2, 3, 4, 5 (0 не может быть первой цифрой потому, что в таком случае число не четырех значное); если первая цифра выбрана, то вторая может быть выбрана 5 способами, третья – 4 способами, четвертая – 3 способами. Согласно правилу умножения общее число способов равно 5 . 5 . 4 . 3 = 300.

4. Сообщение содокладчика по теме «Множества и операции над ними»

Количество элементов произвольного рода образует множество. Примеры множества:

А – все натуральные числа;
В – все четные числа;
С – все нечетные числа.

Все числа множества В находятся в множестве А и все числа множества С находятся в множестве А, тогда множества В и С называют подмножествами множества А. Говорят, А содержит В и С или В и С принадлежат множеству А и обозначаются В ‹ А, С ‹ А.

Определение: Произведение чисел от 1 до п, включая п называют «эн факториал» и обозначают п!.

Определение: Число всех а элементных подмножеств множества из п элементов равно n : а! (n – a)! (а меньше п) это число сочетаний из п элементов по а и оно равно

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

Решение: число сочетаний из 5 книг по 3 равно

С 3 ₅ = 5! : [3! (5 – 3)!] = 5! : (3! 2!) = (1 . 2 . 3 . 4 . 5) : (1 . 2 . 3 . 1 . 2) = 10

V. Самостоятельная работа

Задания для самостоятельной работы сформулированы по принципу ЕГЭ.

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

Выберите букву правильного ответа.

А) 256 Б) 31 В) 240 Г) 16

Решение: Золотую медаль может получить одна из 16 команд. После того как определен владелец золотой медали, серебряную медаль может иметь одна из 15 команд. Следовательно, общее число способов, которыми могут быть распределены золотая и серебряная медали, равно 16 . 15 = 240.

В классе 25 учащихся, сколькими способами можно выбрать старосту класса и его заместителя?

Выберите букву правильного ответа.

А) 25 Б) 600 В) 49 Г) 625

Решение: Староста класса может быть выбран 1 из 25 человек, значит существует 25 способов выбора старосты и 24 способа выбора его заместителя. Существует 25 . 24 = 600 способов выбора старосты класса и его заместителя. Ответ: Б

VI. Подведение итога урока

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

– Повторить основные понятия комбинаторики и методы решения комбинаторных задач.

Используемая литература:

1. Н.Я. Виленкин, А.Н. Виленкин, П.А. Виленкин. Комбинаторика. М., 2006.
2. В.Е. Гмурман Теория вероятностей и математическая статистика. М., 2006.
3. И.И. Ежов, А.В. Скороход, М.И. Ядренко. Элементы комбинаторики. М., 1977.
4. Д.Ж. Риордан. Введение в комбинаторный анализ. М., 1963.

Источник

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

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

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

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить 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.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

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

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Источник

Презентация к уроку

В 2003 году было принято решение о включении элементов теории вероятностей и статистики в школьный курс математики общеобразовательной школы. (Инструктивное письмо №03-93ин/13-03 от 23.09.2003 г. Министерства образования РФ «О введении элементов комбинаторики, статистики и теории вероятностей в содержание математического образования основной школы»). Включение в курс математики элементов статистики и теории вероятностей обусловлено значением и местом вероятностно-статистических понятий в общей системе знаний и представлений современного человека. Вероятностно-статистические представления стали неотъемлимой составляющей функциональной грамотности человека, они играют важную роль в самых разных областях его практической деятельности. Без соответствующей подготовки затруднены восприятие и адекватная интерпритация разнообразной социальной, экономической, политической информации. Сегодня практически все естественные и социально-экономические науки построены и развиваются на базе вероятностно-статистических законов, и без соответствующей подготовки учащихся невозможно полноценное изучение этих предметов в школе. Всё это с неизбежностью требует развития вероятностно- статистического мышления подрастающего поколения. Одновременно именно вероятностно-статистическая линия, или как её стали называть в последнее время стохастистическая линия, изучение которой невозможно без опоры на процессы, наблюдаемые в окружающем мире, на реальный жизненный опыт ребёнка, способна содействовать усилению интереса к самому предмету «математика», пропаганде его значимости и универсальности. Но изучение данного материала представляет для учителей некоторые трудности. Изложение этих тем, как правило, не носило систематического и целостного характера. Учителя не всегда обращались к этим темам и не включали их в учебный план, так как дисциплина не была включена в государственный стандарт. Теперь это произошло. Даже некоторые задачи включены в ГИА 9 класса. Необходимость в изучении этих тем стала реальной.

В стандартах второго поколения по математике 5-9 класс написано, что в предлагаемом примерном тематическом планировании элементы вероятностно-статистической линии включены в курс, начиная с 5-6 класса. В то же время начало изучения этого материала может быть отнесено и к 7-9 классам. Но, как показывает опыт преподавания всё же лучше начинать изучать эти темы с 5 класса. По стандартам на изучение отводится 20 часов. В изучение 5-6 класса включены такие темы: «Представление данных в виде таблиц и диаграмм», «Понятие о случайном опыте и событии. Достоверные и невозможные события», «Решение комбинаторных задач перебором вариантов», «Множество, элемент множества. Пустое множество. Подмножества. Объединение и пересечение множеств. Иллюстрация отношений между множествами с помощью диаграмм Эйлера-Венна».

Основы статистики и вероятности становятся сегодня равноправной составляющей нашего обязательного школьного образования. И трудности для учителей в преподавании этих тем всё же остались. Не во все учебники включены эти темы. Мы работаем в 5-6 классе по учебнику Виленкина Н. Я. Здесь есть некоторые задачи по этим темам, а теории нет. Из своего опыта работы могу сказать, что материал можно найти в других учебниках, например, очень удачно изложен данный материал в учебнике «Математика 5 и 6 класс» по редакцией Дорофеева Г. В., «Вероятность и статистика 5-9 класс» Бунилович Е. А., Былычёв В. А., пособие для общеобраз. учеб. завед., М. «Дрофа», 2002г.

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

. Хочу привести пример изучении темы «Комбинаторные задачи». В основной школе с комбинаторной точки зрения вполне достаточно развитых на разнообразных примерах навыков наивного перебора и отбора «руками» важных вариантов, умений производить различно организованный (например, в виде дерева возможных вариантов) перебор случаев, и, разумеется, осознание использования правил умножения, представленного в как можно большем числе разных комбинаций. Я иногда изучение этих тем расширяю.

Тема «Решение комбинаторные задач»(4 часа).

В приложении разработка обобщающего урока и презентация.

Литература.

Приложение 1: Урок «Комбинаторные задачи», 6 а класс

Источник

Комбинаторика. Ее изучение в школе

Дата публикации: 16.05.2018 2018-05-16

Статья просмотрена: 2071 раз

Библиографическое описание:

Сапунова, Ю. С. Комбинаторика. Ее изучение в школе / Ю. С. Сапунова. — Текст : непосредственный // Молодой ученый. — 2018. — № 20 (206). — С. 413-418. — URL: https://moluch.ru/archive/206/50320/ (дата обращения: 08.11.2021).

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

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

Такие задачи называют комбинаторными. С ними люди столкнулись в глубокой древности. Несколько тысячелетий назад в Древнем Китае увлекались составлением магических квадратов (квадраты, в которых заданные числа располагаются так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одинаковой). В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата, и т. д.

Комбинаторные задачи формировались и во время партий в такие игры, как шашки, шахматы, домино, карты, кости и т. д. (Например, задача об обходе всех полей доски шахматным конем и т. д.)

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

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

Эти древние игры не подвергались математическому исследованию довольно долго.

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

Например, при бросании двух костей сумма 6 получается из сочетаний (1, 5), (2, 4), (3, 3), а сумма 7 — из сочетаний (1, 0), (2, 5), (3, 4). Так как три сочетания были различны в обоих случаях, то напрашивался ошибочный вывод о том, что суммы очков 6, 7 и 8 (также получаемая из трех сочетаний костей) должны выпадать одинаково часто. Но согласно опыту 7 очков выпадает чаще. Сочетание (3, 3) при бросании двух костей может быть получено единственным способом, а сочетание (3, 4) — двумя способами. Именно благодаря этому, сумма 7 выпадает наиболее часто. Таким образом, оказалось, что надо учитывать не только сочетание очков, но и их порядок.

Комбинаторика становится наукой лишь в XVII в. — в период, возникновения теории вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчиненных каким-либо условиям. После первых работ, выполненных в XVI в. итальянскими учеными Дж. Кардано, Н. Тартальей и Г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма. Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 г. работу «Об искусстве комбинаторики», в которой впервые употребляется термин «комбинаторный». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Сейчас комбинаторика находит место во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т. д.

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

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

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

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

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

Если имеются n + 1 птицы, которых необходимо разместить в n гнездах, то при любом способе размещения хотя бы в одном гнезде окажется не менее двух птиц.

Задача. В мешке лежат шарики двух разных цветов — черного и белого. Какое наименьшее количество шариков нужно вынуть из мешка, чтобы среди них точно два шарика оказались одного цвета?

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

Множество , состоящее из всевозможных пар , где элемент принадлежит множеству , а элемент принадлежит множеству , содержит элементов

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

Решение. В данной задаче рассматриваются трехзначные числа, так как цифры в записи этих чисел могут повторяться, то цифру сотен, цифру десятков и цифру единиц можно выбрать тремя способами каждую. Поскольку запись трехзначного числа представляет собой упорядоченный набор из трех элементов, то, согласно правилу произведения, его выбор можно осуществить 27 способами, так как 3 • 3 • 3 = 27.

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

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

А = 3•(3–1)•(3–2) = 3•2•1= 6.

Эти числа таковы: 123, 132, 213, 231, 312, 321.

Заметим, что в данном случае разные числа получаются в результате перестановки цифр.

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

Задача. На тарелке лежат 5 груш и 4 персика. Сколькими способами можно выбрать один плод?

Решение. По условию задачи грушу можно выбрать пятью способами, персик — четырьмя. Так как в задаче речь идет о выборе «либо груши, либо персика», то его, согласно правилу суммы, можно осуществить 5 + 4 = 9 способами.

Если все элементы x₁,x_2,…,x_k кортежа (x₁,x_2,…,x_k) принадлежат одному и тому же множеству Х, то говорят о кортеже из элементов множества Х.

Пусть множество Х состоит из n элементов.

Кортеж длины k, составленный из элементов множества Х, называется размещением с повторениями из n элементов по k (в кортеже (x₁,x_2,…,x_k) его элементы могут повторяться).

Задача. Сколько трёхзначных чисел может быть составлено из нечётных цифр?

Трёхзначное число — это кортеж (x₁,x₂,x₃) длины 3, составленный из элементов множества X, причем цифры в числе могут повторяться. Значит, этих чисел будет столько, сколько существует размещений с повторениями из 5 элементов по 3:

Пусть множество Х состоит из n элементов.

Определение. Кортеж длины k, в котором все элементы различны, составленный из элементов множества Х, называется размещением без повторений из n элементов по k (в кортеже (x₁,x_2,…,x_k) элементы не повторяются!).

Так как повторения в кортеже не допускаются, то теперь k должно быть не больше n.

Найдём A k _n — число всех размещений без повторений из n элементов по k.

Для выбора элемента x₁ имеется n возможностей. После выбора элемента x₁, элемент x₂ можно выбрать (n-1)-м способом и так далее. Тогда

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

Трёхзначное число — это кортеж (x₁,x₂,x₃) длины 3 без повторений, составленный из элементов множества X. Значит, этих чисел будет столько, сколько существует размещений без повторений из 5 элементов по 3:

Всякое k-членное подмножество n-членного множества называется сочетанием из n элементов по k.

Число различных сочетаний из n элементов по k обозначается .

Числа являются коэффициентами в разложении бинома Ньютона:

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

Решение. Очевидно, команда из 6 человек является 6-членным подмножеством 10-членного множества, т. е. сочетанием из 10 элементов по 6. Следовательно, искомое число способов равно

Сейчас комбинаторика изучается в школе. Ученики среднего и старшего звена обязательно сталкиваются на уроках математики/алгебры с комбинаторными задачами. Рассмотрим примеры таких задач.

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

Решение. Решим задачу, используя формулу включений и исключений. Найдем сначала, при скольких способах распределения данные k конвертов оказываются пустыми (а остальные могут быть как пустыми, так и содержать фотографии). В этом случае фотографии кладутся без ограничений в (5-k) конвертов, число таких распределений равно . Но k конвертов можно выбрать из пяти способами. Отсюда, применяя формулу включений и исключений, выводим, что число распределений, при которых ни один конверт не оказывается пустым, равно

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

Решение. Предположим, что Олега назначили дежурить на третьем этаже. Тогда на втором этаже может дежурить Вова или Коля, а на первом — Коля или Вова. Получаем два способа (две комбинации) распределения дежурства (мальчики обозначены первыми буквами их имен).

Пусть теперь дежурным на третьем этаже назначили Вова. Тогда на втором этаже может дежурить Олег или Коля, а на первом — соответственно Коля или Олег. Получаем еще два способа распределения дежурства.

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

Таким образом, получилось шесть способов распределения дежурства.

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

Например, решение задачи о распределении дежурства можно проиллюстрировать с помощью такой схемы:

Эта схема позволяет записать шесть комбинаций, каждая из которых соответствует одному варианту распределения дежурства: ОВК, ОКВ, ВОК, ВКО, КВО, КОВ.

Данная схема напоминает перевернутое дерево. Поэтому ее называют деревом возможных вариантов.

Задача. Сколько углов изображено на рисунке?

Решение. Обозначение любого угла, изображенного на рис. 6, состоит из трех букв, второй из которых обязательно является буква O, а две другие выбираются из букв A, B, C, D. Поэтому количество углов равно количеству способов выбрать из букв A, B, C, D две буквы.

При записи всех возможных вариантов необходимо учесть, что комбинации AB и BA соответствуют одному и тому же углу AOB. Вначале перечислим все пары букв с первой A: AB, AC, AD. Теперь перечислим пары, у которых первая буква B, а вторая не является буквой A: BC, BD. Осталось перечислить пары, у которых первая буква C, а второй не является ни A, ни B: CD.

Таким образом, получили шесть комбинаций: AB, AC, AD, BC, BD, CD. Следовательно, на первом рисунке изображено шесть углов.

При решении этой задачи можно воспользоваться такой наглядной схемой. Рассмотрим четыре точки, обозначенные буквами A, B, C, D.

Тогда количество отрезков, соединяющих каждые две точки, равно количеству углов, изображенных на рис. 6. Например, отрезку AC на рис. 7 соответствует угол AOC на рис. 6, отрезку BC — угол BOC. И наоборот, каждому углу на втором рисунке соответствует определенный отрезок на втором рисунке. На втором рисунке можно провести всего шесть отрезков. Следовательно, искомое количество углов равно шести.

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

Решение. Будем рассматривать русский язык и литературу как один предмет, тогда всего предметов будет пять. Число способов, которыми можно составить расписание из пяти предметов, равно Р₅=5!. Но в каждой из этих перестановок русский язык и литература могут меняться местами. Поэтому искомое число расписаний вдвое больше. Оно равно 5!*2=240.

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

Решение. Выбираем 2 учащихся из 7, порядок выбора не имеет значения (оба выбранных пойдут на олимпиаду как полностью равноправные); количество способов выбора равно числу сочетаний из 7 по 2: способ.

Задача. В одной комнате живут три девушки Оля, Вика и Катя. У них есть 6 флаконов духов, 8 губных помад и 10 лаков для ногтей (все отличаются друг от друга). Сколькими способами девушки могут распределить косметику между собой (так, что каждая получит духи, помаду и лак)?

Решение. Для Оли набор можно набрать 6*8*10=480 способами, для Вики — 5*7*9=315, для Кати — 4*6*8=192. По правилу умножения получаем 480*315*192=29030400 способами.

Задача. Сколькими способами можно рассадить 5 школьников за столом в столовой?

Решение: используем формулу количества перестановок:

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

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

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

Задача. Сколько можно составить разных башенок из семи разноцветных кубиков (только башенки высотой семь кубиков)?

Решение. Всего из 7 разных кубиков можно составить 7*6*. *2*1 = 7! = 5040 упорядоченных последовательностей. Поскольку мы не различаем башенки, отличающиеся друг от друга только поворотом, то это число нужно поделить на 7; кроме того, мы считаем одинаковыми и симметричные башенки, поэтому оставшееся число нужно разделить еще на 2. В итоге получаем 5040 / 14 = 360 разных башенок.

Задача. Даны 2 слова: «абстракционизм» и «многогранность». Коля посчитал, сколько получается слов из слова «многогранность», если вычеркнуть в нем 2 произвольные буквы (получившиеся слова не обязательно осмысленные). Вера сделала то же самое для слова «многогранность». У кого слов получилось больше?

Решение. В данных словах одинаковое количество букв (по 14), поэтому вычеркнуть две буквы из каждого из них можно одинаковым количеством способов. Заметим, что при вычеркивании двух букв из слова «абстракционизм» все полученные слова будут различны, а при вычеркивании букв (мн)ОГ(ог) и (ог)ОГ(ра) из слова «многогранность» получается одно и то же слово «многранность». Поэтому, у Коли получится на одно слово больше. Количество способов выбрать 2 буквы из 14 — это , именно столько слов будет у Коли, а у Веры будет слов. Больше слов у Коли.

Задача. Сколькими способами могут быть распределены первое и второе место по итогам поэтического конкурса, если приняло участие в конкурсе 12 человек.

Решение: На первое место претендуют 12 человек, на второе 11 человек. (один займет первое место). По правилу произведения получаем 12 * 11 = 132 способа.

Задача. Выпуклый многоугольник имеет 90 диагоналей. Сколько у него сторон?

Решение: обозначим количество сторон многоугольника через n, вершин у него тоже будет n. Соединим вершины попарно отрезками, которых будет . Среди этих отрезков будет n сторон, остальные — диагонали. Составим уравнение по условию задачи: . Отсюда получается квадратное уравнение: , корни которого n₁=15, n₂= — 12. По смыслу задачи подходит . Ответ: 15 сторон.

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

Решение. Сначала найдем количество однозначных номеров, отличных от 8. Ясно, что таких номеров девять: 0,1,3,4,5,6,7,8,9. А теперь найдем все двузначные номера, не содержащие двоек. Их можно составить так: взять любой из найденных однозначных номеров и написать после него любую из девяти допустимых цифр. В результате из каждого однозначного номера получится 9 двузначных. А так как двузначных номеров было 9, то получится 9·9 = 92 двузначных номеров.

Итак, существует 92 = 81 двузначный номер без цифры 2. Теперь к каждому из этих номеров можно приписать справа любую из цифр 0,1,3,4,5,6,7,8,9 и получить трехзначный номер, не содержащий цифру 2. При этом получаются все трехзначные номера, удовлетворяющие условию. Итого, 92·9 = 93 = 729 трехзначных номеров без двоек.

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

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

Источник