Простейшие комбинаторные задачи: правило умножения и дерево вариантов, перестановки.
Пример: Начальник написал 10 писем и поручил своему помощнику надписать 10 конвертов с нужными адресами. Тот так и сделал, но дальнейшее перепоручил секретарше. Она выполнила это ответственное задание формально, то есть разложила письма по конвертам, не обращая внимания на адреса. Какова вероятность того, что ни одно письмо не попало в нужный конверт?
Оказывается, что вероятность такой масштабной ошибки превышает 36%.
Все мы довольно часто говорим «это невероятно», «более вероятно, что…», «это маловероятно», «можно утверждать со стопроцентной вероятностью, что…», когда пытаемся спрогнозировать наступление того или иного события. При этом обычно опираемся на интуицию, жизненный опыт, здравый смысл и т.п. Но очень часто такие приблизительные оценки оказываются недостаточными: бывает важно знать, на сколько или во сколько раз совершение одного случайного события вероятнее другого. Иными словами, нужны точные количественные оценки, надо уметь численно характеризировать возможность наступления того или иного события. Раздел математики, посвященный исследованию количественных оценок случайных событий, называется теорией вероятности.
На практике часто приходится выбирать из некоторого множества объектов подмножества элементов, обладающих теми или иными свойствами, расположение элементов одного или нескольких множеств в определённом порядке.
|
|
|
Так как речь идёт о комбинациях объектов – задачи называются комбинаторными, а область математики – комбинаторикой.
Её основателями считают Пьера Ферма и Блеза Паскаля. Эти французские учёные XVII века первыми нашли ключ к составлению количественной оценки вероятности события. Они использовали метод, который позже был назван комбинаторным анализом или комбинаторикой.
Знакомство с новым для вас понятием начнём с двух простых задач, одну из которых решаем вместе, а другую самостоятельно.
Пример 1. Сколько чётных двузначных чисел можно составить из цифр 0, 1, 2, 4, 5, 9.
Решение. Составим таблицу: слева от первого столбца поместим первые цифры искомых чисел, а выше первой строки – вторые цифры этих чисел. Так как в двузначном числе впереди может стоять любая цифра, кроме 0, то строки будут отмечены цифрами 1, 2, 4, 5, 9. Значит, в нашей таблице будет 5 строк. На втором месте в искомом числе должна стоять чётная цифра. Значит, столбцы будут отмечены цифрами 0, 2, 4. Всего в таблице будет 3 столбца.
| 0 | 2 | 4 | |
| 1 | 10 | 12 | 14 |
| 2 | 20 | 22 | 24 |
| 4 | 40 | 42 | 44 |
| 5 | 50 | 52 | 54 |
| 9 | 90 | 92 | 94 |
Клетки таблицы заполнятся следующим образом: первая цифра числа равна метке строки, а вторая цифра – метке столбца, поэтому каждое из интересующих нас чисел попадёт в определённую клетку таблицы. По строкам и столбцам мы перечислим все возможные варианты, значит, искомых чисел будет столько же, сколько клеток в таблице, то есть 5*3=15.
|
|
|
Ответ: 15.
Здесь был осуществлён полный перебор всех возможных вариантов, или, как обычно говорят в таких случаях, всех возможных комбинаций.
Поэтому подобные задачи называют комбинаторными.
Пример 2. На завтрак Илья может выбрать плюшку, бутерброд, пряник или кекс, а запить их он может кофе, соком или кефиром. Из скольких вариантов завтрака Илья может выбирать? (самостоятельно).
Решение. Соберём все варианты в такой таблице:
| Плюшка | Бутерброд | Пряник | Кекс | |
| Кофе | Кофе, плюшка | Кофе, бутерброд | Кофе, пряник | Кофе, кекс |
| Сок | Сок, плюшка | Сок, бутерброд | Сок, пряник | Сок, кекс |
| Кефир | Кефир, плюшка | Кефир, бутерброд | Кефир, пряник | Кефир, кекс |
В ней 3 строки и 4 столбца, они образуют 12 клеток. Так как выбор еды и напитка происходит независимо, то в каждой клетке будет стоять один из возможных вариантов завтрака и, наоборот, любой вариант завтрака будет записан в одной из клеток. Значит, всего вариантов столько же, сколько клеток в таблице.
|
|
|
Ответ: 12.
Видно, что, хотя примеры 1 и 2 очень разные, их решения совершенно одинаковые. Основаны они на общем правиле умножения.
Задачи:
1. Сколько двузначных чисел можно составить из цифр 1, 3, 5, 7, 9?
2. Сколько среди них чисел, кратных 5?
3. Сколько среди них чисел, кратных 11?
4. Сколько среди них чисел, кратных 3?
Дата добавления: 2019-07-15; просмотров: 268; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!