Дискретная математика. Ерош И.Л - 72 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

72
рею всетаки можно и можно даже выигрывать, но только в том слу
чае, когда играешь на чужие деньги, а не на свои! Этот мой вывод уже в
недавнее время подтвердили и продолжают подтверждать организато
ры различных современных лотерей типа МММ.
Кстати, попробуйте обосновать алгоритм заполнения минимально
го числа билетов лотереи «Спортлото», при котором гарантируется уга
дывание хотя бы одной комбинации из 3х номеров. А может быть, по
пробовать то же с 4 номерами?
4.1.8. Сочетания с повторениями
Пример. Требуется купить 7 пирожных. В магазине имеются пи
рожные следующих 4х видов: эклеры, песочные, слоеные и наполе
оны. Сколько вариантов покупки 7 пирожных 4х видов?
Решим задачу следующим образом. Построим код из 7 единиц, к ко
торому припишем справа три нуля: 1111111000. Будем переставлять
теперь элементы этого кода всеми возможными способами. Можем по
лучить, например, такой код: 1101111001. В соответствии с этим ко
дом сделаем такую покупку: купим эклеров столько, сколько единиц
стоит перед первым нулем, песочных купим столько, сколько единиц
стоит между первым и вторым нулем, слоеных купим столько, сколь
ко единиц стоит между вторым и третьим нулем, наполеонов купим
столько, сколько единиц стоит после третьего нуля. Таким образом,
покупка будет выглядеть так: 2 эклера, 4 песочных, ни одного слое
ного и 1 наполеон. Каждому коду можно сопоставить одну покупку и
каждой покупке 7 пирожных 4х видов однозначно можно сопоставить
перестановку из 7 единиц и 3х нулей. Таким образом, количество ва
риантов покупки равно
12
10!
7,3 120.
7!3!
P 33
Обобщим полученное решение. Если имеются предметы n разных
типов (без ограничений числа предметов каждого типа) и требуется оп
ределить, сколько комбинаций можно составить из них так, чтобы в
каждую комбинацию входило k предметов. Каждую комбинацию бу
дем шифровать с помощью 1 и 0, причем 1 будет соответствовать пред
метам, а нули будут выполнять функцию разделителей. Тогда, запи
сав k единиц и добавив n–1 нуль, получим комбинацию, при которой
выбираются k предметов первого типа и ни одного предмета остальных
типов. Переставляя всеми способами эти k единиц и n–1 нуль, мы бу
дем каждый раз получать некоторую расстановку, содержащую k пред
метов. Тогда

Страницы