3. Размещения и сочетания
Правила суммы и произведения – это общие правила решения комбинаторных задач. Кроме них в комбинаторике пользуются формулами для подсчета числа отдельных видов комбинаций, которые встречаются наиболее часто. Рассмотрим некоторые из них и прежде всего те, знание которых необходимы учителю начальных классов.
Используя цифры 7, 4 и 5, мы образовали различные двузначные числа: 77, 74, 75, 47, 44, 45, 57, 54, 55. В записи этих чисел цифры повторяются.
С теоретико–множественной точки зрения запись любого двузначного числа – это кортеж длины 2. Записывая различные двузначные числа с помощью цифр 7, 4 и 5, мы по сути дела образовывали из данных трех цифр различные кортежи длины 2 с повторяющимися элементами. В комбинаторике такие кортежи называют размещениями с повторениями из трех элементов по два элемента.
Определение. Размещением с повторениями из к элементов по т элементов – это кортеж, составленный из т элементов к – элементного множества.
Из определения следует, что два размещения из k элементов по m элементов отличаются друг от друга либо составом элементов, либо порядком их расположения.
Например, два двузначных числа из перечисленных выше (а это размещения из трех элементов по два) отличаются друг от друга либо составом элементов (74 и 75), либо порядком их расположения (74 и 47).
Относительно размещений часто возникает вопрос: «Сколько всевозможных размещений по т элементов каждое можно образовать из k элементов данного множества?». Например, сколько всевозможных двузначных чисел можно записать, используя цифры 7, 4 и 5?
Число всевозможных размещений с повторениями из к элементов по m элементов обозначают и подсчитывают по формуле. Выведем эту формулу.
Пусть в множестве Х содержится k элементов. Будем образовывать из них различные кортежи по m элементов. Такие кортежи образуют множество Х Х … Х, содержащее m множителей. По правилу произведения
n(ХХ…Х)===km
Следовательно, . Пользуясь этой формулой, легко подсчитать, сколько двузначных чисел можно записать, используя цифры 7, 4 и 5. Так как речь идет о размещениях с повторениями из трех элементов по два, то Нередко встречаются задачи, в которых требуется подсчитать число кортежей длиныm, образованных из k элементов некоторого множества, но при условии, что эти элементы не повторяются. Такие кортежи называются размещениями без повторений из k элементов по m элементов.
Определение. Размещение без повторений из k элементов по т элементов – это кортеж, состоящий из неповторяющихся элементов множества, в котором k элементов.
Число всевозможных размещений без повторений из k элементов по m элементов обозначают и подсчитывают по формуле =k (k – 1) … (k – m + 1).
Выведем эту формулу.
Пусть в множестве Х содержится k элементов. Будем образовывать из них различные размещения без повторений из m элементов. Тогда выбор первого элемента таких кортежей можно осуществить k способами; если первый элемент выбран, то выбор второго элемента можно осуществить k – 1 способом (так как после выбора первого элемента кортежа в множестве Х остается k – 1 элемент). Третий элемент размещения можно выбрать k – 2 способами и т. д., m–й элемент можно выбрать k – (m – 1) способами. На выбор упорядоченного набора из m элементов можно осуществить k( k – m– 1) …(k – m +1) способами. Значит, =.
Например, число двузначных чисел, записанных с помощью цифр 7, 4 и 5 так, что цифры в записи не повторяются, есть число размещений без повторений их трех элементов по два: = 3 (3 – 1) = 3 2 = 6.
Задача 1. Сколько всевозможных трехзначных чисел можно записать, используя цифры 7, 4 и 5, так, чтобы цифры в записи числа не повторялись?
Решение. В задаче рассматриваются размещения без повторений из трех элементов по три, и их число можно подсчитать по формуле: = 3 (3 – 1) (3 – 2) = 321 = 6.
Эти числа таковы: 745, 754, 475, 457,547,574.
Заметим, что в данном случае разные числа получаются в результате перестановки цифр. Поэтому размещения из k элементов по k элементов называют перестановкой из k элементов без повторений.
Число перестановок без повторений из k элементов обозначают Рk и подсчитывают по формуле Рk = k!, где k! = 123…k и k! читают «k факториал». Считают, что 1! = 1, 2! = 1. Например, 5! = 12345= 120; 7! =1234567 = 5040.
Из элементов множества Х = 7, 4, 5 можно образовывать не только кортежи различной длины, но и различные подмножества, например, двухэлементные. В комбинаторике их называют сочетаниями без повторений из трех элементов по два элемента.
Определение. Сочетанием без повторений из k элементов по m элементов – это m – элементов подмножество множества, содержащего k элементов.
Два сочетания из к элементов по m – элементов отличаются друг от друга хотя бы одним элементом.
Число всевозможных сочетаний без повторений из k элементов по m элементов обозначают . Как находить это число?
Обратимся сначала к примеру. Образуем различные двухэлементные подмножества из элементов множества Х = 7, 4, 5. Их будет три: 7, 4, 7, 5, 4, 5. Из элементов каждого такого подмножества можно образовать 2! Кортежей длины 2:
(7,4) (7,5) (4,5)
(4,7) (5,7) (5,4)
Все полученные кортежи являются размещениями без повторения из трех элементов по два и их число равно = 3 2 = 6. Но, с другой стороны, это число равно произведению 2! =.
Докажем справедливость этой зависимости в общем виде, т.е., что .
Пусть в множестве Х содержится k элементов. Образуем из них сочетания без повторений по m элементов. Они будут представлять собой m – элементные подмножества множества Х. Всего таких подмножеств будет .
Из элементов каждого m – элементного подмножества можно образовать m! перестановок, т.е. кортежей длины m. В итоге получаем m! кортежей длиныm, образованных из к элементов множества Х. Их число равно .
Таким образом, =m! , откуда получаем.
Конечно, применение формул облегчает подсчет числа возможных вариантов решений той или иной комбинаторной задачи. Однако, чтобы воспользоваться той или иной формулой необходимо определить вид соединений, комбинаций, о которых идет речь в задаче, что бывает сделать не очень просто.
Выясним, например, о каких комбинациях идет речь в следующих задачах:
Сколько всего двузначных чисел?
Сколько всего двузначных чисел, в записи которых цифры не повторяются?
На прямой взяли десять точек. Сколько всего получилось отрезков, концами которых являются эти точки?
В первой задаче двузначные числа образуются из 10 цифр, причем цифры в записи числа могут повторяться (в задаче нет условия о том, что цифры в записи могут не повторятся). Используя теоретико-множественную терминологию, можно сказать, что в ней речь идет об упорядоченных наборах (кортежах) из 10 элементов по 2 с повторениями. В комбинаторике такие кортежи называются размещениями с повторениями из 10–ти элементов по 2. Их число можно найти по формуле = 102= 100. Но среди этих кортежей есть такие, у которых на первом месте стоит цифра 0 и которые не могут рассматриваться как запись двузначного числа. Таких кортежей 10, их надо вычесть из 100. Таким образом, двузначных чисел всего 90.
Конечно, эту задачу можно было решить проще, применив правило произведения: первую цифру из записи двузначного числа можно выбрать девятью способами, вторую десятью, а упорядоченную пару – 9 10 = 90 способами.
Во второй задаче также рассматриваются кортежи длины 2, образованные из 10 элементов (цифр), но элементы в них не повторяются. Такие кортежи в комбинаторике называются размещением без повторений из 10–ти элементов по 2. Их число можно найти по формуле = 10 (10 – 1) = 90, но из этого числа надо вычесть кортежи, у которых на первом месте стоит цифра 0, и они не могут представлять запись двузначного числа. Таких кортежей 9. Поэтому двузначных чисел, в записи которых цифры не повторяются, 90 – 9 = 81.
Другой характер имеют комбинации, о которых идет речь в третьей задаче. Действительно, если для записи чисел в первых двух задачах важен порядок следования цифр (так, 23 и 32 – это различные числа), то в третьей задаче он роли не играет (отрезок АВ и отрезок ВА – это один и тот же отрезок). Комбинации в этой задаче являются двухэлеменными подмножествами, образованными из 10–ти данных элементов (точек). Такие подмножества в комбинаторике называются сочетаниями без повторений из 10 элементов по 2. Их число можно найти по формуле: = 45.
- Министерство образования и науки украины
- Содержание
- Пояснительная записка
- Структура курса
- Модуль 1. Множества
- Тема 1. Множества и операции над ними
- Введение
- 1. Понятие множества и элемента множества
- 2.Способы задания множества
- 3. Отношения между множествами. Подмножество
- Примеры
- 4. Круги Эйлера-Венна
- Практическая работа. Понятие множества
- Тема 2. Операции над множествами
- 1. Пересечение множеств
- 2. Объединение множеств
- 3. Законы пересечения и объединения множеств
- Определение. Для любых множеств а, в и с выполняются равенства:
- 4. Вычитание множеств. Дополнение подмножества
- Практическая работа. Операции над множествами
- Вопросы к изучению
- Основные понятия
- Обозначения
- Практическая часть
- Тема 2.1. Понятие разбиения множества на классы
- 1. Понятие разбиения множества на классы
- Практическая работа. Разбиение множества на классы
- Вопросы к изучению
- Обозначения
- Правила
- Тема 2.2. Декартово произведение множеств
- 1. Декартово произведение множеств
- 2. Свойства операции нахождения декартова произведения
- 3. Кортеж. Длина кортежа
- Практическая работа. Декартово произведение
- Вопросы к изучению
- Обозначения
- Правила
- Тема 3. Понятие соответствия Содержание
- 1. Понятие соответствия между множествами
- Рассмотрим примеры соответствий, изучаемых в начальном курсе математики.
- 2. Способы задания соответствий
- 3. Соответствие обратное данному
- 4. Взаимно однозначные соответствия
- 5. Равномощные множества
- Практическая работа. Соответствия между двумя множествами
- Тема 4. Числовые функции
- 1. Понятие функции. Способы задания функций
- 2. Прямая и обратная пропорциональности
- Основные понятия темы
- Основные выводы, замечания
- Тема 5. Отношения на множестве
- 1. Понятие отношения между элементами одного множества
- 2. Способы задания отношений
- 3. Свойства бинарных отношений
- Практическая работа. Отношения на множестве
- Тема 6. Выражение. Уравнение. Неравенство
- Выражения и их тождественные преобразования.
- 1. Выражения и их тождественные преобразования
- 3. Уравнения с одной переменной
- 4. Неравенства с одной переменной
- Практическая работа. Выражения и их преобразования. Числовые равенства и неравенства с одной переменной.
- Практическая работа. Уравнения и неравенства с одной переменной.
- Контрольная (зачетная) работа
- Модуль 2. Математические утверждения и их структура
- Тема 7. Математические понятия Содержание
- 1. Математические понятия. Объем и содержание понятия
- Пусть заданы два понятия а и b. Объемы их обозначим соответственно а и в.
- 2. Отношение рода и вида между понятиями
- 4. Требования к определению понятий
- 5. Неявные определения
- Практическая работа. Математические понятия
- Вопросы к изучению
- Представления о математических понятиях -
- Обозначения
- Тема 8. Высказывания и высказывательные формы
- 2. Конъюнкция и дизъюнкция высказываний
- 3. Конъюнкция и дизъюнкция высказывательных форм
- Практическая работа. Высказывания и высказывательные формы
- Тема 8.1. Высказывания с квантором. Отрицание высказываний и высказывательных форм
- 1. Высказывания с кванторами
- 2. Истинность высказываний с кванторами
- 3. Отрицание высказываний и высказывательных форм
- Практическая работа. Высказывания с кванторами. Отрицание высказываний и высказывательных форм
- Тема 8.2. Отношения следования и равносильности между предложениями
- 1. Отношения следования между предложениями
- 2. Отношения равносильности между предложениями
- Практическая работа. Отношения следования и равносильности между предложениями
- Вопросы к изучению
- Основные понятия темы
- Обозначения
- Тема 8.3. Структура теоремы. Виды теорем
- 1. Структура теоремы
- 2. Отличие теоремы от правила
- 3. Виды теорем
- Практическая работа. Структура теоремы. Виды теорем
- Тема 9. Математическое доказательство
- 1. Понятие умозаключения.
- 2. Дедуктивные умозаключения Умозаключения, построенные по схеме
- 3. Индуктивные умозаключения. Полная индукция
- Все s1, s2,..., Sп исчерпывают весь класс s (4) Все s есть р
- 4. Неполная индукция
- 5. Математическая индукция
- 6. Аналогия
- 7. Умозаключения «от противного»
- 8. Некоторые виды неправильных умозаключений
- 9. Логическая структура математической задачи
- 10. Закон достаточного основания и аксиоматический метод в математике
- Практическая работа. Математическое доказательство
- Теоретическая часть Вопросы к изучению
- Основные понятия темы
- Практическая часть
- Тема 10. Текстовая задача и процесс ее решения
- 1. Роль и место задач в начальном курсе математики. Функции текстовых задач
- 2. Структура процесса решения текстовой задачи
- 2. Методы и способы решения текстовых задач
- 3. Этапы решения задачи и приемы их выполнения
- 1. Анализ задачи
- 4. Поиск и составление плана решения задачи
- 5. Осуществление плана решения задачи
- 6. Проверка решения задачи
- 7. Моделирование в процессе решения текстовых задач
- Практическая работа. Текстовая задача и процесс ее решения
- Теоретическая часть Вопросы к изучению
- Основные понятия темы
- Практическая часть
- Тема 11. Комбинаторные задачи и их решение
- 1. Комбинаторика
- 2. Правила суммы и произведения
- 3. Размещения и сочетания
- Практическая работа. Комбинаторные задачи и их решение
- Вопросы для коллоквиума
- Модуль 3. Целые неотрицательные числа
- Тема 12. Аксиоматическое построение системы натуральных чисел
- 1. Из истории возникновения понятия натурального числа
- 2. Об аксиоматическом способе построения теории
- 3. Основные понятия и аксиомы. Определение натурального числа
- 4. Количественные натуральные числа. Счет
- Семинарское занятие. История возникновения понятия натурального числа Вопросы к изучению
- Вопросы для самоконтроля
- Задания для самостоятельной работы
- Тема 13. Теоретико-множественный подход к построению натурального ряда чисел. Теоретико-множественный смысл арифметических действий.
- 1. Теоретико-множественный смысл натурального числа, нуля и отношения «меньше»
- 2. Теоретико-множественный смысл суммы
- 3. Теоретико-множественный смысл разности
- 4. Теоретико-множественный смысл произведения
- 5. Теоретико-множественный смысл частного натуральных чисел
- Практическая работа. Теоретико–множественный смысл суммы, разности, произведения, частного и отношения «меньше»
- Теоретическая часть Вопросы к изучению
- Основные понятия темы
- Тема 14. Позиционные и непозиционные системы исчисления
- 1. Позиционные и непозиционные системы счисления
- 2. Запись числа в десятичной системе счисления
- Практическая работа. Запись целых неотрицательных чисел
- Теоретическая часть
- Основные понятия темы
- Тема 15. Алгоритмы действий над целыми неотрицательными числами
- 1. Алгоритм сложения
- 2. Алгоритм вычитания
- 3. Алгоритм умножения
- 4. Алгоритм деления
- Практическая работа. Алгоритмы арифметических действий
- Теоретическая часть Вопросы к изучению
- Основные понятия темы
- Тема 16. Отношение делимости и его свойства Содержание
- Признаки делимости.
- Наименьшее общее кратное и наибольший общий делитель.
- 1. Отношение делимости и его свойства
- 2. Признаки делимости
- 3. Наименьшее общее кратное и наибольший общий делитель
- 4. Простые числа
- 5. Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел
- Практическая работа. Делимость натуральных чисел
- Тема 17. О расширении множества натуральных чисел
- 1. Понятие дроби
- 2. Положительные рациональные числа
- 3. Запись положительных рациональных чисел в виде десятичных дробей
- 4. Действительные числа
- Практическая работа. Действия над положительными действительными числами
- Вопросы к коллоквиуму
- Теоретико-множественный смысл отношения «меньше», «равно»
- Теоретико-множественный смысл суммы.
- Теоретико-множественный смысл разности.
- Признаки делимости.
- Тема 18. Натуральное число как мера величины. Измерение величин
- 1. Понятие положительной скалярной величины и ее измерения
- 2. Смысл натурального числа, полученного в результате измерения величины
- 3. Смысл суммы и разности
- Практическая работа. Понятие положительной скалярной величины
- Практическая работа. Обоснование выбора действий при решении текстовых задач в начальной школе
- Теоретическая часть Вопросы к изучению
- Определения, теоремы, выводы
- Тема 19. Геометрические фигуры на плоскости и их свойства
- 1. Понятие геометрической фигуры
- 2. Углы
- 3. Параллельные и перпендикулярные прямые
- 4. Треугольники
- 5. Четырехугольники
- Параллелограммом называется четырехугольник, у которого противолежащие стороны параллельны.
- 1. Диагонали параллелограмма пересекаются и точкой пересечения делятся пополам.
- 2. У параллелограмма противолежащие стороны и противолежащие углы раны.
- 6. Многоугольники
- 7. Окружность и круг
- 8. Построение геометрических фигур на плоскости.
- 1. Построить на данной прямой отрезок со, равный данному отрезку ав.
- 2. Отложить от данной полупрямой в данную полуплоскость угол, равный данному углу.
- 3. Найти середину отрезка.
- 4. Построить биссектрису данного угла.
- 5. Через данную точку провести прямую, перпендикулярную данной прямой.
- 9. Преобразования геометрических фигур. Понятие преобразования
- 1. Симметрия относительно точки (центральная симметрия).
- 2. Симметрия относительно прямой (осевая симметрия).
- 3. Гомотетия.
- 10. Движения и равенство фигур
- Практическая работа. Решение геометрических задач
- Практическая работа. Основные задачи на построение на плоскости
- Теоретическая часть Вопросы к изучению
- Основные понятия темы
- Практическая часть
- Тема 20. Изображения пространственных фигур
- 1. Свойства параллельного проектирования
- 2. Многогранники и их изображение
- 3. Шар, цилиндр, конус и их изображение
- Практическая работа. Изображение пространственных фигур на плоскости
- Теоретическая часть Вопросы к изучению
- Основные понятия темы
- Практическая часть
- Тема 21. Геометрические величины
- 1. Длина отрезка и ее измерение
- 2. Величина угла и ее измерение
- 3. Понятие площади фигуры и ее измерение
- 4. Площадь многоугольника
- 5. Площадь произвольной плоской фигуры и ее измерение
- Практическая работа. Геометрические величины
- Теоретическая часть Вопросы к изучению
- Основные понятия темы
- Правила, замечания
- Практическая часть
- Список литературы
- Учебник для студентов высших педагогических учебных заведений специальности: «начальное обучение»
- Глузман Неля Анатольевна Кандидат педагогических наук, доцент, заведующий кафедрой методик начального и дошкольного образования рвуз «Крымский гуманитарный университет» (г. Ялта)