Занятие 6.
Комбинаторика. Правило суммы и произведения.
Правило суммы. Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами.
Правило произведения. Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А;В) в указанном порядке можно осуществить m∙ n способами.
№ 1. Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков каждое, надо выделить по одному фехтовальщику для состязания. Сколькими способами это можно сделать?
№ 2. Из города А в город В ведут пять дорог, из В в С – три. Сколько путей, проходящих через В, ведут из А в С?
№ 3. Бросают игральную кость с шестью гранями и запускают волчок имеющий восемь граней. Сколькими способами они могут упасть?
№ 4. На ферме есть 20 овец и 24 свиньи (все разной упитанности). Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его ещё раз?
№ 5. Сколькими способами можно выбрать на шахматной доске белое и черное поля, не лежащие на одной горизонтали или вертикали?
№ 6. В корзине 12 яблок и 10 апельсинов. Ваня выбирает из неё яблоко или апельсин, после чего Надя берёт и яблоко и апельсин. В каком случае Надя имеет большую свободу выбора: если Ваня взял яблоко или он взял апельсин?
№ 7. Сколько слов, содержащих 6 букв, можно составить из 33 букв русского алфавита при условии, что любые две стоящие рядом буквы различны?
№ 8. Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу?
№ 9. Сколько можно составить из 32 различных букв шестибуквенных слов, содержащих хотя бы один раз букву «ф»?
№.10. Сколько существует четырёхзначных чисел с разными цифрами?
№ 11. Сколько существует четырёхзначных чисел, у которых хотя бы две цифры совпадают?
№ 12. Сколько существует четырёхзначных чисел, цифры которых идут в возрастающем порядке?
№ 13. Сколько чисел, меньше миллиона, можно записать с помощью цифр 8 и 9? Ас помощью цифр 0, 1, 8, 9?
Размещения и перестановки.
Перестановкой n различных элементов будем называть способ расставить все эти элементы на n местах. Количество всех перестановок находят с помощью n!
№14. Сколько существует способов рассадить 10 человек в ряд?
№ 15. Сколько существует способов рассадить 10 человек на 10-ти креслах карусели? Рассадки переходящие друг в друга при вращении карусели, считаются одинаковыми.
№ 16. Сколько способов рассадить на 10-ти креслах карусели 5 мальчиков и 5 девочек так, чтобы девочки и мальчики чередовались?
№ 17. Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы никакие две из них не били друг друга
№ 18. Сколько пятизначных чисел содержат все цифры 1,3,5,4,7,9? А сколько все цифры 0,2,4,6,8?
Размещением из n элементов по k будем называть способ разместить на к местах некоторые п элементов так, чтобы элементы не повторялись. Количество всех размещений из п элементов по к находят по формуле п! : (п – к)!
№ 19. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице – президента, учёного секретаря и казначея. Сколькими способами может быть сделан выбор, если один член общества может занимать только один пост?
№ 20. Сколькими способами можно расставить 10 различных книг на двух полках? Каждая полка способна вместить все 10 книг.
Решения и ответы к занятию 6.
№ 1.100х100=10000
№ 2. 5х3=15
№ 3. 6х8=48
№ 4. 24х20=480 способов, для второго случая 23х19=437
№ 5. Пусть выбирают сначала белое поле, затем чёрное. Белого поля существует 32 варианта, Для каждого белого поля существует (32-8) вариантов выбрать чёрное поле. 32х24=768
№ 6. Яблоко. Если Ваня возьмёт яблоко, то у Нади будет 11х10=110 способов сделать выбор. Если Ваня возьмёт апельсин, то у Нади будет 12х9=108 вариантов.
№ 7. 1 букву можно выбрать 33 способами. Вторую -32 способа, 3-ю -32, 4-ю-32, 5-32 способа, 6 -32, всего 33х32х32х32х32х32
№ 8. Для каждого числа очков (от 0 до 6) есть ровно 7 костей домино, содержащих это значение. Если две кости домино можно сложить, то сделать это можно единственным способом. Найдём количество способов выбрать две кости домино, которые можно приложить друг к другу «шестёрками». 1-ю кость можно выбрать 7 способами. Вторую 6 способами. 7х6=42 способа выбрать две такие кости в определённом порядке. Однако, нам порядок не важен, и при таком подсчёте мы дважды учли каждый интересующий нас вариант, то есть на самом деле число способов равно 42:2=21. Аналогично можно выбрать две кости, которые складываются друг с другом любым значением («пятёркой», «четвёркой», и т.д.). Всего 21х7=147 способов.
№ 9. Всего можно составить 32х32х32х32х32х32 шестибуквенных слов. Слов не содержащих среди них букву «ф» - 31х31х31х31х31х31. Значит искомых слов 32х32х32х32х32х32 - 31х31х31х31х31х31.
№ 10. 9х9х8х7=4536 способов.
№ 11. Всего 4-хзначных чисел 9х10х10х10х10=90000. Среди них чисел с различными цифрами 4536. Значит искомых чисел 90000-4536 = 4464.
№ 12. Если цифры идут в возрастающем порядке, значит они различны. При этом 0 среди них встречаться не может. Если мы выберем 4 различные цифры, то расставить их в возрастающем порядке можно единственным образом. С учётом порядка четыре различные ненулевые цифры можно выбрать 9х8х7х6=3024 способами. Четыре различные цифры можно расставить 4х3х2х1=24 способами. Значит, искомых чисел 3024:24=126.
№ 13. Числа должны быть не более чем 6-тизначные. Для первого случая: однозначных – 2, двузначных -2х2, 3-хзначных -2х2х2, и т.д. Всего 2+4+8+16+32+64=126 способов. Для второго случая: однозначных – 4, двузначных – 3х4, трёхзначных – 3х4х4 и т.д. Всего 4+12+48+192+768+3072=4096 способов.
№ 14. 10!=1х2х3х4х5х6х7х8х9х10=3628800
№ 15. Если места пронумеровать, то будет 10! Способов (различая сдвиги). Но по условию всё равно, какое место считать первым. То есть десяти различным подсчитанным выше способам соответствует один способ рассадки на карусели. Всего
10! : 10 = 9! Способов.
№ 16. Будем считать, что мальчики сидят на чётных , а девочки на – нечётных местах. Тогда всего 5!х5! вариантов, а всего 2х5!х5! вариантов. Значит, в ответе получаем 2х 5! х5! : 10 способов.
№ 17. Будем ставить все ладьи по порядку: для первой 8х8=64 варианта, для второй 7х7=49 вариантов и т.д. Всего 8х8х7х7х6х6х5х5х4х4х3х3х2х2х1х1=8!х8! вариантов. Однако нам всё равно, какая ладья является первой, какая второй и т.д. Для любых 8 клеток существует 8! Способов перенумеровать ладьи, занимающие эти клетки, поэтому каждый интересующий нас вариант мы учли 8! Раз. Таким образом, на самом деле существует 8! вариантов.
№ 18. В первом 5! вариантов. Во втором 4х4х3х2х1= 4х4! вариантов
№ 19. к=4, n=25, тогда 25! : (25 – 4)! = 25! : 21! = 22х23х24х25 = 303600
№ 20. 11!. Всего разложить книги в разном порядке можно 10! Способами. Каждому из этих способов соответствует 11 вариантов раложить книги по полкам ( на 1-ой – 0, на 2-ой -1, и т.д. Всего 10!х11=11!
