Элементы дискретной математики - 19 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

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

Рубрика: 

19
Первый способ. Существует
3
11
C треугольников с вершинами в отмеченных точках,
4
11
C
– четырехугольников,
5
11
C – пятиугольников, … ,
11
11
C – одиннадцатиугольников. Таким
образом, по правилу суммы всего многоугольников
3
11
C +
4
11
C +
5
11
C +…+
11
11
C . Из
четвертого свойства следует, что это выражение равно 2
11
-
1
11
C -
2
11
C =1 982.
Второй способ. Любая из одиннадцати точек либо является вершиной
рассматриваемого многоугольника, либо не является. Всего вариантов 2
11
. Но одна или
две точки не могут составлять многоугольник. Остается 2
11
-
1
11
C -
2
11
C вариантов
многоугольников с вершинами в отмеченных точках.
Сочетания с повторениями.
Задача.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры,
песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Эта задача не является задачей на размещения с повторениями, так как порядок, в
котором укладывают пирожные в коробку, несуществен. Поэтому она ближе к задачам на
сочетания. Но от задач на сочетания она отличается тем
, что в комбинации могут быть
повторяющиеся элементы. Такие задачи называют задачами на
сочетания с повторениями.
Чтобы решить задачу, поступим следующим образом. Зашифруем каждую покупку
с помощью нулей и единиц. Сначала напишем столько единиц, сколько куплено наполеонов.
Потом, чтобы отделить наполеоны от эклеров, напишем нуль, затем – столько единиц,
сколько куплено эклеров, и т. д. Например, если куплено 3 наполеона, 1 эклер, 2 песочных и
1 слоеное пирожное, то получим
такую запись: 1110101101. Ясно, что разным покупкам
соответствуют разные комбинации из 7 единиц и 3 нулей. Обратно, каждой комбинации 7
единиц и 3 нулей соответствует какая-то покупка.
Таким образом, число различных покупок равно числу перестановок с
повторениями, которые можно составить из 7 единиц и 3 нулей. А это число равно
P(7,3)=120.
К тому же самому результату
можно было прийти и другим путем, а именно:
расположим в каждой покупке пирожные в таком порядке: наполеоны, эклеры, песочные и
слоеные, а потом перенумеруем их. Но при нумерации будем к номерам эклеров прибавлять
1, к номерам песочных – 2, к номерам слоеных – 3. К номерам наполеонов ничего
прибавлять не будем. Например, пусть куплено 2 наполеона, 3
эклера, 1 песочное пирожное

Страницы