Математика и информатика. Власов В.А - 20 стр.

UptoLike

ВУЗ: 

ТГПУ | Томск

Составители: 

Рубрика: 

20
Комбинаторика занимается задачами размещения объектов в
соответствии со специальными правилами и нахождения числа способов,
которыми это размещение может быть сделано. Если способы размещения
достаточно простые, то комбинаторика дает ответ на вопрос о количестве
возможных размещений. В более сложных задачах ставится вопрос о
существовании заданного размещения. Мы будем изучать основные понятия
комбинаторики, к которым относятся перестановки, размещения и сочетания.
Правила суммы и произведения. Дерево всевозможных вариантов.
Начнем рассмотрение этого материала с задач:
Задача 1. В магазине есть 5 различных видов коробок конфет и 4 коробки
печенья. Сколькими способами можно составить набор, состоящий из коробки
конфет и печенья?
Для ответа на эти вопросы обратимся к правилу произведения.
Правило произведения: Пусть x принимает одно из n значений x ∈ {a
1
,
a
2
, …, a
n
} , y принимает одно из m значений y∈ {b
1
, b
2
, …, b
m
}. Тогда для
построения упорядоченной пары существует
m × n способов.
Так как всего в таблице
m × n клеточек, ответ очевиден.
Таблица 2
x
y
a
1
a
2
a
3
… a
n
b
1
(a
1
,b
1
) (a
2
,b
1
) (a
3
,b
1
) … (a
n
,b
1
)
b
2
(a
1
,b
2
) (a
2
,b
2
) (a
3
,b
2
) … (a
n
,b
2
)
b
3
(a
1
,b
3
) (a
2
,b
3
) (a
3
,b
3
) … (a
n
,b
3
)
… … … … … …
b
m
(a
1
,b
m
) (a
2
,b
m
) (a
3
,b
m
) … (a
n
,b
m
)
Решение (задача 1): Одну коробку конфет можно выбрать 5-ю способами,
а печенье – 4-мя. Применяя правило произведения, получим: 4
⋅5=20.
Правило произведения для двух независимых испытаний удобно
показывать, используя прямоугольники, разбитые на квадратики, или
прямоугольные таблицы. Но если проводятся три испытания, то для
иллюстрации надо использовать и длину и ширину, и высоту, и на картинке
получится прямоугольный параллелепипед, разбитый на кубики. Когда мы
имеем дело с четырьмя испытаниями, то для рисунка нам просто не хватит
измерений. (Окружающее нас пространство трехмерно).
Оказывается, правило умножения для трех, четырех и т.д. испытаний
можно объяснить, не выходя за рамки плоскости, с помощью геометрической
модели, которую называют
деревом всевозможных вариантов. Она, во-
первых, наглядна как всякая картинка, и, во-вторых, позволяет все учесть,
ничего не упустив.
Рассмотрим
Задачу 2: Несколько стран в качестве символа своего
государства решили использовать флаг в виде трех горизонтальных полос

Страницы