| Сколькими способами можно расположить их в ряду так, чтобы ни для какого i (1 i n) карточка с номером i не занимала бы i-ого места Решение. Число всевозможных расположений (перестановок) n карточек в ряд равно Pn=n!=N(0). Обозначим через ai свойство: “i-ая карточка занимает место с номером i (i = 1, 2, …, n)”. Тогда N(ai) = N(1) = Pn – 1 = (n – 1)! – число перестановок всех карточек в ряду, кроме i-ой,которая остаётся на i-ом месте; N(ai, aj) = N(2) = Pn – 2 = (n – 2)! – число перестановок всех карточек в ряду, кроме двух карточек с номерами i и j, остающихся на месте, т. е. на i-ом и j-ом местах, и т. д. N(ai1, ai2, …, aik) = N(k) = Pn-k = (n – k)! – число расположений, при которых карточка с номером is занимает “своё”,1 k место is (s = ). По формуле (10) получаем, что искомое число N равно n n n n! k k k k kn CN P 11 n!! n kn k k 00 nk k !! k 0 k! Заметим, что полученное число способов располагаться любой i-ой карточки не на i-ом месте согласуется с формулой «числа беспорядков» (см. (8) на стр. 41). ЗАДАЧИ И УПРАЖНЕНИЯ 1. При обследовании читательских вкусов студентов оказалось, что 60% студентов читает журнал А, 50% — журнал В, 50% — журнал С, 30% — журналы А и В, 20% — журналы В и С, 40% — журналы А и С, 10% — журналы А, В и С. Какой процент студентов: а) не читает ни одного из этих журналов б) читает в точности два журнала в) читает только один журнал В Задачу решить двумя способами (с помощью формулы (9) и кругов Эйлера). Ответ: а) 20%; б) 60%. 2. При опросе 13 человек, каждый из которых знает по крайней мере один иностранный язык, выяснилось, что 10 человек знают английский язык, 7 -немецкий, 6 — испанский, 5 — английский и немецкий, 4 — английский и испанский, 3 — немецкий и испанский. Сколько человек знают: а) все три языка б) ровно два языка в) только английский язык Ответ: 2, 6, 3. 3. На экскурсию поехало 92 человека. Бутерброды с колбасой взяли человек, с сыром — 38 человек, с ветчиной — 42 человека; и с сыром и с колбасой — 28 человек, и с колбасой и с ветчиной – 31 человек, и с сыром и с ветчиной — 26 человек. Все три вида бутербродов взяли 25 человек. Несколько человек вместо бутербродов взяли пирожки. Сколько человек взяли с собой пирожки Ответ: 25 человек. 4. Найти количество натуральных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 3, 5 и 7 Ответ: 457. 5. Найти количество натуральных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 6, 15и10 Ответ: 734. 6. Показать, что если п=30т, то количество натуральных чисел, не превосходящих п и не делящихся ни на одно из чисел 6, 10 и 15, равно 22m. 7. Сколько неотрицательных целых чисел, меньших миллиона, состоит только из цифр 1, 2, 3, 4 2.4 Задачи с ограничениями Рассмотрим в данном параграфе комбинаторные задачи сначала с ограничениями на порядок элементов, когда на порядок элементов накладываются некоторые дополнительные условия. В таких задачах удобно применять метод – объединение нескольких одинаковых элементов в блоки. Далее рассмотрим задачи на разбиения, где требуется разделить элементы на две или более групп в соответствии с некоторыми условиями, и требуется найти число всевозможных различных способов раздела. При этом необходимо учитывать, существенен ли порядок элементов в группах, различаем ли мы элементы, входящие в группы, и сами группы и т. д. При решении этих задач обычно элементы располагают в ряд и применяют так называемый метод введения перегородок. Пример 16. Имеются предметы k сортов : n1 предметов одного сорта, n2 предметов другого сорта, …, nk предметов k-ого сорта, где все предметы одного сорта всё же различны друг от друга. Найти число перестановок этих предметов, в которых все предметы одного и того же сорта стоят рядом. Решение. Из данных k сортов (блоков) можно сделать Pk=k! перестановок. Но ещё можно переставлять предметы внутри блоков n1!, n2!, …, nk! способами. Далее по правилу произведения имеем n1!n2!… nk!k! перестановок. Пример 17. Сколькими способами можно переставить буквы слова “перемет” так, чтобы три буквы “е” не шли подряд Решение. Объединим все буквы “е” в блок “еее”. Число перестановок, в которых все три буквы “е” идут подряд, равно числу перестановок из 5-ти объектов : “еее”, “п”, “м”, “р”, “т”, т. е. P5=5! Всего же перестановок с повторениями из букв данного слова можно составить P(3,1,1,1,1)=840. Значит, искомое число перестановок, где три буквы “е” не идут рядом равно N = 840 — 120 = 720 (способов). Пример 18. Сколькими способами можно расставить m нулей и k единиц так, чтобы никакие две единицы не стояли рядом Решение. Выпишем сначала m нулей. Для единиц получается (m+1) место (одно впереди, (m-1) в промежутках между нулями и одно сзади). На любые из этих (m+1) мест можно поставить одну из k единиц. Это можно k Cm+осуществить способами, причём k m+1. Пример 19. На полке стоят 12 книг. Сколькими способами можно выбрать из них 5 книг так, чтобы никакие две из них не стояли рядом Решение. Зашифруем каждый выбор книг последовательностью из нулей и единиц следующим образом : каждой оставленной книге сопоставим 0, а каждой взятой – 1. В результате получим последовательность из единиц и 7 нулей, причём в последовательности не будет двух подряд идущих единиц (так как нельзяпо условию брать две рядом стоящие книги). Имеем неупорядоченную 5-выборку из 8 (см. пример 18). СледоваC тельно, всего будет = 56 (способов). Пример 20. Найти число способов разбиения n одинаковых предметов по m урнам. Решение. Перенумеруем урны, расположив их в ряд. Между ними будет (m-1) промежуток. Поставим в соответствие каждому разбиению предметов по урнам последовательность из нулей и единиц следующим образом : сначала последовательность имеет группу из нулей, число которых равно числу предметов в первой урне, затем ставим 1 (перегородку); далее – столько нулей, сколько предметов во второй урне и опять ставим 1; затем столько нулей, сколько в третьей урне и т. д. Заканчивается последовательность группой нулей; их столько, сколько предметов в последней урне. Следовательно, в последовательности будет n нулей и (m-1) единиц, Cm-1-+mn всего (n+m-1) цифр. Тогда всего способов разбиения будет равно. n Cm-1-+mn 1 H Заметим, что = (уметь доказать). m Пример 21. Комиссия состоит из 9 человек. Документы хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их распределить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся вместе не менее 6 человек комиссии Решение. Какие бы 5 членов комиссии не собрались, должен найтись замок, который они не могут открыть, но ключ от этого замка имеется у каждого из 4 остальных членов комиссии (появление кого-нибудь из которых даёт возможность открыть сейф). Следовательно, число замков равно 5 C9 =126; число ключей равно C9 4=504. m-Cn Замечание. В общем случае число замков равно ; число ключей m-Cn, где n – число членов комиссии, m – к этим замкам равно (n-m+1) наименьшее число членов, при которых возможен доступ к сейфу, при ус ловии m n + 1. Пример 22. Сколькими способами можно расставить в шеренгу львов и 4 тигра так, чтобы никакие два тигра не шли друг за другом Решение. Расставим сначала всех львов, оставив между каждыми двумя львами промежуток. Это можно сделать P5 способами. Теперь для расстановки тигров имеется 6 мест (либо одно впереди всех львов, либо одно после них, либо между ними – четыре). Так как порядок тигров сущеAственен (все тигры разные), то число способов их расстановки равно. Общее число способов расстановки хищников получим по правилу произ A ведения P5 =43200. Замечание. Если бы в задаче было n львов и m тигров, то общее чисm An+1 при условии, что m n+1 – иначе два тило способов было равно Pn гра обязательно окажутся рядом. 2.5 Разные задачи 1. Сколькими способами можно указать на шахматной доске два квадрата – белый и чёрный А если нет ограничения на цвет квадратов Ответ: 1042; 4032. 2. Сколькими способами можно выбрать на шахматной доске белый и чёрный квадраты, не лежащие на одной горизонтали и вертикали Ответ: 32 24. 3. Имеется три волчка с 6, 8 и 10 гранями соответственно. Сколькими различными способами они могут упасть А если известно, что по крайней мере два волчка упали на сторону, помеченную цифрой “1” Ответ: 480. 4. Сколькими способами можно выбрать из полной колоды карт (52 карты) по одной карте каждой масти Ответ: 134. 5. В магазине лежат 6 экземпляров романа И. С. Тургенева “Рудин”, экземпляра его же романа “Дворянское гнездо” и 4 экземпляра романа “Отцы и дети”. Кроме того, есть 5 томов, содержащих романы “Рудин” и “Дворянское гнездо”, и 7 томов, содержащих романы “Дворянское гнездо” и “Отцы и дети”. Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов Та же задача, если, кроме того, в магазине есть 3 тома, в которые входят романы “Рудин” и “Отцы и дети”. An -6. Возможно ли равенство Pn = 36 и если да, то при каких n Ответ: Да, при n 6. 7. Сколькими способами могут 4 человека разместиться в четырёхместном купе железнодорожного вагона Ответ: 24. 8. Найти число простых чисел, не превосходящих 250. 9. У одного человека есть 7 книг, у другого 9.Сколькими способами они могут обменять книгу одного на книгу другого, если все книги различны Та же задача, но меняются две книги одного на две книги другого. 10. Автомобильные номера состоят из одной, двух или трех букв и четырех цифр. Найти число таких номеров, если используются 27 букв русского алфавита. Ответ: 33820 104. 11. Сколькими способами можно составить список из 7 студентов Ответ: 5040. 12. Из спортклуба, насчитывающего 30 человек, надо выбрать команду из человек для участия в беге на 1000 м. Сколькими способами можно это сделать А если нужно выбрать команду из четырех человек для участия в эстафете 100+200+400+800 Ответ: 27405; 657720. 13. Сколько различных четырехзначных чисел можно составить из семи цифр 0, 1, 2. 6, если каждая из них может повторяться несколько раз Ответ: 2058. 14. Сколько пятизначных чисел можно составить из цифр 1,2,4,6,7,8, если никакую цифру не использовать более одного раза Ответ: 6!. 15. На танцевальном вечере присутствуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них четыре пары для танцев Ответ: 17417400. 16. Из цифр 1,2,3,4,5 составляются всевозможные числа, каждое из которых содержит не менее трех цифр. Сколько таких чисел можно составить, если повторение цифр в числах запрещено 4 Ответ: AP ++ A5 = 300. 17. Сколькими способами можно выбрать 6 одинаковых или разных пирожных в кондитерской, где продаются 11 разных сортов пирожных Ответ: H11. 18. Сколько всего костей домино, если используется для их образования цифр 0,1,2,3,4,5,6. Ответ обосновать. Ответ: 28, так как кости домино можно рассматривать как неупорядоченные 2-выборки из 7-и цифр 0, 1, 2, 3, 4, 5, 6 с повторениями; 19. В группе 35 учащихся. Из них 20 посещают математический кружок,- физический;10 учащихся не посещают ни одного из этих кружков. Сколько учащихся посещают оба кружка Сколько учащихся посещают только математический кружок Ответ: 6; 14. 20. Изучаются 10 учебных предметов. В понедельник надо поставить уроков, причем все разные. Сколькими способами можно составить расписание на понедельник Ответ: 151200. 21. Сколькими способами читатель может выбрать 3 разные книги из пяти Ответ: 10. 22. Сколькими способами можно переставить буквы в слове «тик-так» чтобы одинаковые буквы не шли друг за другом То же самое для слова «тартар». 23. Сколько целых чисел от 0 до 999,которые не делятся ни на 2,ни на 3, ни на 5, ни на 7 Ответ: 228. 24. Сколькими способами можно переставить числа 12341234 так, чтобы ни какие две одинаковые цифры не шли друг за другом Ответ: 864. 25. Сколькими способами можно переставить числа 12345254 так, чтобы ни какие две одинаковые цифры не шли друг за другом. 26. Сколько разных слов можно составить, переставляя буквы в слове «мама» Напишите эти слова. 27. В комнате n лампочек. Сколько всего разных способов освещения ком наты, при которых горит ровно k лампочек Сколько всего может быть различных способов освещения данной комнаты 28. Сколькими способами можно разместить на полке 4 разные книги Ответ: 24. 29. Сколько можно составить перестановок из n элементов, в которых данные два элемента не стоят рядом ( Ответ: — )(nn -12 )! Решение: Данные два элемента, например «a» и «b», будем считать за один элемент «ab». Тогда имеем (n — 1) элементов, которые можно переставить (n — )!1 способами. Если же имеем элемент «ba», то имеем так (n (n же — )!1 способов перестановки -1) элементов. Следовательно, (n. число перестановок, в которых «a» и «b» стоят рядом, равно -12 )! n! Всего перестановок. Тогда искомое число перестановок равно -2! (nn -1)!. 30. Сколькими способами можно рассадить 4 учащихся на 25 мест Ответ: 303600. 31. Студенту надо сдать 4 зачёта за 8 дней. Сколькими способами можно это сделать А если последний зачёт обязательно сдавать на восьмой день Ответ: 1680; 840. 32. Сколькими способами можно рассадить n гостей за круглый стол 33. На собрании должны выступать 4 человека А,В,С,Д. Сколькими способами их можно разместить в списке ораторов, если В не может выступать до того момента, пока не выступит А Ответ: 3 3!. 34. Определить число всех плохих дней, если 12 дней шел дождь, 8 дней дул ветер, 4 дня было холодно, причем 5 дней были и дождливы и ветрены, 3 дня дождливы и холодны, 2 дня ветреных и холодных, 1 день дождливый, ветреный и холодный, а хороших дней не было за данный период. 35. Сколько натуральных чисел в n-ой системе счисления можно записать k знаками k -k Ответ: ( 1)- nn, так как имеем упорядоченные -выборки с поn вторениями из элементов множества = <,0 1, 2. nA -1>. 36. Сколько неудачных попыток может быть сделано человеком, не знающим секретного кода, составленного из 5 цифр и подбирающего его наудачу Ответ: A10 -1, так как имеем упорядоченную 5-выборку с повторениями из 10-ти элементов, из них одна 5-выборка удачная, ограничений нет. 37. Сколько имеется пятизначных чисел, которые делятся на 5 Ответ: 1800. 38. Сколько пятизначных чисел, у которых все цифры нечетные Ответ: 55. 39. Сколькими способами можно сфотографировать 4 танкистов, 4 летчиков и 2 артиллеристов, поставив их в один ряд так, чтобы представители одного рода войск стояли рядом Ответ: 6912. 40. Сколько различных слов получится в результате перестановки букв в слове а) «математика», б) «комбинаторика» Ответ: P(,2 3,2,1,1,1) = 151200. 41. Сколько слов можно составить из 12 букв : четырех букв «а», четырех букв «б», двух букв «в» и двух букв «г» Ответ: P(,4 2,4,2)= 207900. 42. Сколькими способами можно распределить n предметов среди k лиц Ответ: nk k k Решение: Перенумеруем все предметов. Имеем упорядоченную n выборку из множества < aa. an>, так как всего лиц, среди которых распределяются предметы. 43. Из цифр 1,2,3,4 составить неупорядоченные 2-выборки с повторениями. Сколько всего их Перечислите. 44. Имеется 3 курицы, 4 утки и 2 гуся. Сколько имеется комбинаций для выбора нескольких птиц так, чтобы среди выбранных были и куры,и гуси, и утки Ответ: 315. 45. Сколькими способами можно сервировать стол на четверых человек, если имеется 6 разных тарелок,8 разных вилок и 7 разных ножей 46. Сколько существует всего двузначных чисел, составленных из цифр 0,1,2. 9 Ответ: 90. 47. Сколько неотрицательных целых чисел, меньших миллиона, состоит только из цифр 1,2,3,4 m m-Ответ: — CCn n-2. 48. Сколько существует сочетаний из элементов 1,2. n по m (2 Pages: | 1 | . | 3 | 4 | | | • Главная | • Контакты | | | | 
