Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 60
Текст из файла (страница 60)
Сколько существует перестановок букв а,с,7', т,р,г,1 и х, если а) нет никаких ограничений? б) между а и с должны стоять две или три буквы? в) буквы а и с не должны быть разделены двумя или тремя буквами? г) первые четыре буквы должны быть выбраны из а,с, г" и т? д) буквы а, с, 7' и т должны стоять рядом? 11. Сколько существует способов рассадить за круглым столом пятерых мужчин и пятерых женщин, если двое мужчин не должны сидеть рядом? 12.
Сколько существует способов выбрать комитет из 5 человек в клубе, насчитывающем 25 членов? 342 ГПАВА 8. комбинаторика и вероятность 13. Сколько существует способов составить комитет из 6 мужчин и 7 женшин, если организация состоит из 15 мужчин и 20 женщин? 14. Сколько существует 8-битовых строк, содержащих 3 нуля и 5 единиц? 15. Сколько существует способов вытащить 13 карт из стандартной колоды, содержащей 52 карты? 16. Сколько существует способов вытащить из колоды 13 карт, содержащих 6 карт одной масти? 17.
Сколько существует способов вытащить из колоды 13 карт, содержащих 7 карт одной масти? 18. Сколько существует способов вытащить из колоды 13 карт, содержащих 8 карт одной масти? 19. Сколько существует способов вытащить из колоды 13 карт, содержащих 9 карт одной масти? 20. Сколько существует способов получить в 5-карточной раздаче ровно две пары (две карты одного ранга и две карты другого ранга, например, два туза и два короля)? 21.
Сколько существует способов получить в 5-карточной раздаче три карты одного ранга (например, три десятки)? 22. Сколько существует способов получить в 5-карточной раздаче пять карт одной масти (флеш)? 23. Сколько существует способов разделить 10 человек на две команды по 5 человек для игры в баскетбол? 24. Пусть А = (а, Ь,с, Н,е,~,д, Ь).
Сколько существует а) трехэлементных подмножеств множества А? б) пятиэлементных подмножеств множества А, содержащих Ь? в) пятиэлементных подмножеств множества А, не содержащих Ь? г) пятиэлементных подмножеств множества А, содержащих с, но не содержащих Н и е? д) подмножеств множества А, содержащих хотя бы три элемента? е) подмножеств множества А, содержащих не более шести элементов? 25. Если монета подброшена 10 раз, то сколько существует способов выпадения четырех "решек" и шести "орлов"? Сколько существует способов выпадения не менее трех "решек"? 26.
В зоомагазине продаются 5 черепах, 7 ящериц и 12 мышей. Сколько существует способов выбрать себе 2 черепахи, 3 ящерицы и 5 мышей? 27. Известно, что ответ на тест, состоящий из 30 вопросов, содержит 20 утвердительных ответов и 10 отрицательных. К сожалению, больше ничего не известно. Сколько существует вариантов ответа на тест, содержащих 20 утвердительных ответов на вопросы? 28. Если многоугольник имеет п сторон, то сколько у него диагоналей? 29. В команде из 20 человек каждый игрок одинаково хорошо играет на всех позициях. Сколько существует способов выбрать для начала игры команду из 9 человек? 30.
Сколькими способами можно расставить игроков в предыдущей задаче? 31. Найдите разложение (а+ Ь)з, используя треугольник Паскаля. РАЗДЕЛ 8,4. Формирование перестановок и сочетаний 343 32. В разложении (2х+ Зу)'о найдите коэффициент при хву4. 33. В разложении (Зх — 4у)'з найдите коэффициент при хауз. 34. В разложении (х+ 2уз)'з найдите коэффициент при хзу'в. 35. В разложении (хз — Зуз)1о найдите коэффициент при хэу14. 36. Попытайтесь найти числа Фибоначчи в треугольнике Паскаля и описать их местоположение. Указание: посмотрите на второй элемент второго ряда и первый элемент третьего ряда; затем посмотрите на второй элемент третьего ряда и первый элемент четвертого ряда. Наконец, посмотрите на третий элемент третьего ряда вместе со вторым элементом четвертого ряда и первым элементом пятого ряда.
8.4. ФОРМИРОВАНИЕ ПЕРЕСТАНОВОК И СОЧЕТАНИЙ Пусть множество Я, содержащее п элементов, линейно упорядочено, например, как целые числа или буквы алфавита, и требуется найти все перестановки данного множества. Это означает, что нас интересует множество строк, которые включают каждый элемент множества Я, причем, только один раз. Для начала введем понятие лексикографического порядка. Лексикографическим порядок называется потому, что он лежит в основе упорядочения слов в словаре.
Например, слово аЫе в английском словаре стоит перед словом дгау, так как в алфавите буква а стоит перед буквой д. Слово доозе стоит перед словом дгау, потому что, хотя первые буквы совпадают, вторая буква слова доозе стоит в алфавите перед второй буквой слова дгау. Слово зесопаеа предшествует слову зесопИз, потому что, хотя первые шесть букв совпадают, седьмая буква слова зесопаеа стоит в алфавите перед седьмой буквой слова зеозпаз. Точно так же число 12346 предшествует числу 12349. ОПРЕДЕЛЕНИЕ 8.46.
Для заданного линейно упорядоченного множества 5 лексикографический порядок с на строках элементов множества Я опреде- ляется следующим образом: а -с Ь, если а = а1азаз...а, Ь = 616зЬз...Ь„, и выполнено одно из условий: а) а|<Ь1, б) а, =6, для всех 1<1<6 и аь+1<Ььег, в) а, = Ь, для всех 1 < 1 < т и т < и. Теперь будем формировать множество всех перестановок элементов линейно упорядоченного множества. Для простоты рассмотрим только перестановки первых и целых чисел, отметив, что метод справедлив и для прочих случаев. Пусть строка а1азаз...а„ обозначает перестановку а1 аз аз ... а„ 344 ГЛАВА 8. Комбинетороке о вероятность Таким образом, 51342 представляет перестановку 1 2 3 4 5 Для нахождения всех перестановок необходимо иметь возможность сформировать перестановку, следующую за данной согласно лексикографическому порядку.
Поскольку нас интересуют лишь строки одной длины, пункт (в) определения лексикографического порядка можно опустить. При лексикографическом порядке увеличение второй цифры изменит расположение строки в большей мере, чем изменение в пятой цифре. Аналогично, увеличение первой цифры изменит расположение строки в большей степени, чем изменения в седьмой цифре. Например, если начать со слова г1аге, то слово геаг1 находится от него дальше, чем слово г1еаг. Поэтому для формирования следующей строки необходимо менять те символы, которые ближе всего к концу. Предположим, что а, > а,ч.1 для т < см < и. Если бы это условие выполнялось для всех неотрицательных т, то мы имели бы лексикографически наибольшую строку, что означало бы завершение процесса.
Поэтому допустим, что существует такое гп, что а, > а;~г для гп < 1 < и, но а < а„,еы Если переупорядочить все а„где г > гп, то мы создадим строку, которая будет лексикографически меньше. Например, любая перестановка последних четырех цифр в строке 12348765 создаст лексикографически меньшее число.
Таким образом, следует увеличивать цифру а, не меняя при этом никакое а„где г < гп, т.е. нужно увеличивать а, оставляя без изменения все а;, где 1 < т. Поэтому выберем наименьшее число а, такое, что г > тп и а < а;. Меняем местами а„, и а,. Затем переставляем в возрастающем порядке все аг, следующие за новым а . Так мы получим наименьшее из чисел, больших исходного числа. Например, рассмотрим число 12348765. Для получения следующего числа меняем местами 4 и 5, получая 12358764.
Затем переставляем 8, 7, 6 и 4 в возрастающем порядке и получаем 12354678. Пусть задано число 1437652, Для нахождения следующего числа меняем местами 3 и 5, получая 1457632. Теперь переставляем 7, 6, 3, 2 в возрастающем порядке, получая 1452367. Обратите внимание, что перестановка последних цифр свелась к записи их в обратном порядке, поскольку до этого они находились в убывающем порядке. Таким образом, приходим к следующей процедуре: Процедура Формирование перестановки (ад,..., а ) Найти гп такое, что сч > а,ег для гп < а; < п, но а < а„,~г', Выбрать наименьшую цифру ам такую что 1 > т и ат < аи Поменять местами а и а;; Переупорядочить все а,, стоящие после нового а в возрастающем порядке; Конец процедуры.
Теперь рассмотрим метод формирования всевозможных сочетаний из и элементов множества Я. Мы не будем использовать лексикографический порядок элементов множества 5, а воспользуемся лексикографическим порядком на строках бинарных чисел. Напомним, что любому сочетанию элементов из п элементов соответствует бинарная строка длины п. Если множество Я задано в виде РАЗДЕЛ В.4. Формироевние перестановок и сочетвний 345 (а,, аз, аз,..., а„), то единица на месте к-го бита в бинарной строке показывает, что ак присутствует в выбранном подмножестве, в то время как 0 в том же месте бинарной строки показывает, что аь не включено в выбранное подмножество. НапРимеР, если множество о пРедставлЯет собой 1аы аз, аз, аа, аз), то 10110 соответствует выбору подмножества (аыаз,а4), а 10001 — выбору подмножества (ам аз).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
