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

1.

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

2.

Научными исследованиями по
комбинаторике занимались
• Дж. Кардано (1501 – 1576),
• Н. Тарталья (около 1499 – 1577),
• Г. Галилей (1564 – 1642),
• Б. Паскаль (1623 – 1662),
• П. Ферма (1601 – 1665),
• Г.Лейбниц (1646 – 1716),
• Л.Эйлер ( 1707 – 1783).

3.

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

4.

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

5.

Задача 1. Сколько различных
двузначных чисел можно записать с
помощью цифр 0, 2, 4, 6, 8?
•В качестве первой цифры числа может быть
выбрана любая из цифр 2, 4, 6, 8
(n = 4).
Второй цифрой может служить любая из
данных цифр 0, 2, 4, 6, 8 (m = 5). Согласно
правилу произведения число всевозможных
двузначных чисел, составленных из
предложенных цифр, равно n m = 4 5 = 20.

6.

Соединением называется каждое
конкретное подмножество,
составленное из элементов
данного множества
Виды соединений
• Размещения
• Перестановки
• Сочетания

7.

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

8.

Задача 1. Сколько различных двузначных
чисел можно записать с помощью цифр
1, 2, 3, 4 при условии, что в каждом из них
нет одинаковых цифр?
Перебором убедимся в том, что из четырёх цифр
1, 2, 3, 4 можно составить 12 двузначных чисел,
удовлетворяющих условию задачи:
12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43.
По правилу произведения таких двузначных чисел 12.
На первом месте может стоять любая из данных
четырёх цифр, а на втором месте – любая из трёх
оставшихся.

9.

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

10.

Задача. Сколькими способами можно обозначить
вершины данного треугольника, используя
буквы A, B, C, D, E, F?
Решение задачи сводится к
нахождению числа размещений из 6
элементов по 3 элемента в каждом.
По формуле для нахождения числа
размещений без повторений
находим
то есть вершины можно обозначить
120 способами.

11.

Задача на размещения
• Задача 1. Сколькими способами можно
выбрать из класса, насчитывающего
21 ученика, мэра, казначея и физорга?
• Решение.

12.

Вычислить:

13.

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

14.

Задача
На странице альбома 6 свободных мест для
фотографий.
Сколькими способами можно вложить в
свободные места 6 фотографий?
Решение: