Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 53
Текст из файла (страница 53)
Тогда имен~тел: девять перестановок с повторениями --. аа, а6, ас, Ьа, ЬЬ, Ьс, са, сЬ, сс; шесть перестановок без повторений аЬ, ас, Ьа, Ьс, са, сЬ; шесть сочетаний с повторениями аа, а6, ас, ЬЬ, Ьс, сс; три сочетания без повторений аЬ, ас, Ьс. 254 Гл. 7П1. Элементы комбинаторики Произведение п(п — 1)... 1т~ — т + 1), где п действительное, а т целое положительное, будет обозначаться через 1т1), По определению положим 1ие) = 1. Если п натуральное, то 1п)„обозначается символом и! и называется и-факториалом. При и = О полагаем О! = 1. Для любого действительного и и целого неотрицательного т величина — ' называется биномиальным коэффициентом и обознача1н),.
ется символом ) ~ ~. Пусть тю тз, ..., тя -- целые неотрицательные ?и'1 ~т~' п! числа и т з + тз +... + ть = п. Величина называется па- тП тИ т„! линомиальным коэффициентом и обозначается через ( ~ть тм ..., тяу ' При подсчете числа различных комбинаций используются следующие два правила. Правило произведения. Если объект А может быть выбран п способами и после каждого из таких выборов объект В в свою очередь может быть выбран и способами, то выбор «А и В» в указанном порядке может быть осуществлен т .
и способами. Правило суммы. Если объект А может быть выбран т способами, а объект В другими и способами при условии, что одновременный выбор А и В невозможен, то выбор «А или В» можно осуществить т + п, способами. Пример 2. Бросают две игральные кости 1с шестью гранями каждая). Сколькими способами они могут упасть так, что либо на каждой грани выпадет четное число очков, либо на каждой грани выпадет нечетное число очков? Решение. Пусть А число способов выпадения на каждой кости четного числа очков,  — число способов выпадения на каждой кости нечетного числа очков.
Тогда по правилу суммы искомое число равно А + В. Пусть С число способов выпадения четного числа очков на первой кости, а Р число способов выпадения четного числа очков на второй кости. Ясно, что С = Р = 3, а по правилу произведения А = С Р = 9. Аналогично, В = 9, а искомое число равно 18. П р имер 3. Доказать,что число 1п, т)-перестановок без повторений равно (п~)„. Решение.
Индукция по т. При т = 1 число способов выбора одного элемента из и равно и = (п)м Пусть для некоторого г > 1 выполнено равенство Р? п., т) = 1п) „. Докажем аналогичное равенство для т + 1. Всякая совокупность, состоящая из т + 1 элементов, может быть составлена путем предварительного выбора элементов, составляющих 1п, т)-перестановку, и последующего присоединения к ней от+1)-го элемента. Если т элементов выбраны, то 1т+ 1)-й может быть *) В литературе встречаются также обозначения С,",, иС„, 1н, т).
? Д Переегаановни и сочетания 255 выбран и — г способами. В силу правила произведения получаем, что Р(п, г + 1) = Р(л, г) . (и — г). С использованием предположения инцукции получаем отсюда, что Р(и, г + 1) = (п)„(и — г) = (п)„~.ы Большое число комбинаторных задач сводится к подсчету числа двоичных векторов. Пример 4. Сколькими способами можно представить число и в видо суммы и неотрицатсльных слагаомых? (Представления, отличающиеся лишь порядком слагаемых, считаются различными.) Решение. Каждому разбиению числа и на а. целых неотрицательных слагаемых сопоставим вектор длины п+ Й вЂ” 1 с п единицами и Й вЂ” 1 нулями, в котором число единиц, стоящих перед первым нулем, равно первому слагаемому, число единиц, расположенных между первым и вторым нулями, .равно второму слагаемому и т.д.
Соответствие взаимно однозначно. Заметим, что каждому двоичному вектору с п+ Й вЂ” ! координатами и и единицами в свою очередь можно сопоставить и-алиментное подмножество А множества Г = (аы аз, ..., а„е е) следующим образом: 1-я координата вектора равна 1 тогда и только тогда, когда и, Е А (1 = 1, 2,..., и+ а — 1). Но число таких подмножеств ость С(п -1- й -~- 1, п). 1.1.
Сколькими способами можно распределить три билета среди 20 студентов, если: 1) распределяются билеты в разные театры, а каждый студонт может получить не более одного билета; 2) распределяются билеты в разные театры и на разные дни, а каждый студент может получить любое (не превышающее трех) число билотов; 3) распределяются равноценные билеты на вечер н каждый студент может получить не более одного билета? 1.2.
Выяснить, сколькими способами можно выстроить девять че- ЛОВОК; 1) в колонну по одному; 2) в колонну по три, если в каждой шеренге люди выстраиваются по росту и нет людей одинакового роста? 1.3. Показать, что: 1)Р(п,г)=п"; 2)С(п,г)=( ): 3)С(п,г)=( ). 1А. Найти число векторов а = (аы ..., аа), координаты которых удовлетворяют условиям; 1) а; е (О, 1....., к — 1) (1 = 1, ..., п):, 2)а,5(0,1,...,к,— Ц (в=1,...,.п); 3) а, й (О, 1) (1 = 1, ..., и) и а1 +... + аа = г. 1.5. Ц Каково число матриц из п строк и гп столбцов с элементами из множества (О, 1)? 2) То жс при условии, что строки матрицы попарно различны? 256 Гл.
гП1, Элементы комбинаторики 1.6. Нано т предметов одного сорта и и другого. Найти число выборок, составленных из г предметов одного сорта и з предметов другого сорта. 1.7. Из п букв, среди которых а встречается о раз, буква 5 встречается ?1 раз,. а остальные буквы попарно различны, составляются слова. Сколько среди них будет различных г-буквенных слов, содержащих 6 раз букву и и ь' раз букву Ь? 1.8.
Имеется колода из 4п ?п > 5) карт, которая содержит карты четырех мастей по п карт каждой масти, занумерованных числами 1, 2, ..., п. Подсчитать, сколькими способами можно выбрать пять карт так, что среди них окажутся: 1) пять последовательных карт одной масти: 2) четыре карты из пяти с одинаковыми номерами; 3) три карты с одним номером и две карты с другим: 4) пять карт какой-нибудь одной масти; 5) пять последовательно занумерованных карт; 6) в точности три карты из пяти с одним и тем же номером; 7) не более двух карт каждой масти.
1.9. Применяя правило суммы и правило произведения, решить следукещие задачи. 1) Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу (т, е, чтобы некоторое одинаковое число очков встретилось на обеих костях)? 2) Бросают три игральные кости. Сколькими способами они могут упасть так,что все оказавшиеся сверху грани либо одинаковы, либо попарно различны? 3) У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если ему дадут не более трех имен, а общее число имен равно 300? 1.10.
1) Сколькими способами можно число п представить в виде суммы й натуральных слагаемых? (Представления, различающиеся лишь порядком слагаемых, считаются разными.) 2) Сколькими способами число 7" можно представить в виде трех сомножителей? (Представления, различающиеся лишь порядком сомножителей, считаются разными.) 3) Решить задачу 2), если представления, различающиеся лишь порядками, разными не считаются и и ~ Зеь 1.11.
1) Сколькими способами можно расставить п нулей и к. единиц так, чтобы между любыми двумя единицами находилось не менее ш нулей? 2) Сколько существует неотрицательных целых чисел, не превышающих 10", цифры которых расположены в неубывающем порядке? 3) Карта города имеет вид прямоугольника, разделенного улицами на квадраты. Таких квадратов в направлении с севера на юг ровно и, а в направлении с востока на запад ровно к. Сколько имеется кратчайших маршрутов от северо-восточного конца города до юго-западного? 257 7" 1. Переавлноени и сочетания 1.12. Пусть и = ро'...р„" разложение числа и в произведение простых попарно различных чисел.
Найти: 1) число всех натУРальных делителей числа 1н)я; 2) число всех делителей, не делящихся на квадрат никакого целого числа, отличного от 1; 3) сумму делителей числа н. 1.13. Доказать следующие свойства биномиальных коэффициен- ' (".) =(-"-.) ' ©(.") =("'.")(".) 3)( )=( )+( 1); 4) ~й/ /и — гз г =-О й (и -~- 1'1 1.14. Доказать, что: 1) (я ) возрастает по и при фиксированном /е; /и1 /и — г'г 2) ) ) убывает по с при фиксированных и и к; 3) если п фиксировано, то („") возрастает по а при а < ~ — ! и ~23 убывает при й > 1 — ~; 1 2 1' 4) щах (')=(,' ); иг ие /и,1 5) минимальное значение суммы ( ! + ( ) +... + ( ') при /о ~11 Ги1 Условии ,'г и; = п Равно 1е — г)(~ ) +г) ~ в ), где и = ~ — ~, г = (г/ ( Й )' е г=л =п — е~ — ~; 6) максимальное значение суммы ( ) + („) +...
+ ( ) при условии О</ез «...Йг <и 11<е<п+Ц равно у ( ); (у/ и — е п-'-г — </<— 2 2 7) при простом р и любом р > /е > 1 число ( ) кратно р; /р1 17 Г. П. Гаврилов, А. А. Сапоженяо 258 Гп. $7Ы Элементы комбинаторики 8) П р, < ( „), где произведение берется по всем простым /2пй п<т<зп числам р, (и < р, < 2п). 1.15. Ц Пусть т . целое неотрицательное число, а п = Гг(ггг) минимальное целое число такое, что т < и.'. Показать, что можно (и притом единственным способом) сопоставить числу т такой вектор а(т) = (аг, аз, ..., а, 7), что т, = аг 1! +аз 2.
'+... ... + а„г(77 — 1)!, 0 < а, < 7 (Г = 1....., п — Ц. 2) Пусть р(а) число такое, что а = а(р(а)). Найти вектор а(т) для т=4,15,37. 3) По вектору а найти р(а), где: а) а = (О, 2, О, 4); б) а = (О, 2, 1): в) а = (1, 2, 3, 2). 4) Подстановкой на множестве з„= (1, 2, ..., п) называется произвольное отображение з„на себя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
