Перестановки. Размещения. Сочетания

⇐ ПредыдущаяСтр 3 из 12Следующая ⇒

Пусть есть некоторое конечное множество элементов U={a₁, a₂, ..., a_n}. Рассмотрим набор элементов , где Î U, j = 1, 2, ..., r.

Этот набор называется выборкой объема r из n элементов. Любое подмножество U является выборкой, но не всякая выборка является подмножеством U, так как в выборку один и тот же элемент может входить несколько раз (в отличие от подмножества).

Комбинаторные задачи связаны с подсчетом числа выборок объема r из n элементов, где выборки подчиняются определенным условиям, т.е. выбор производится по какому-нибудь принципу. Подсчет числа выборок основывается на двух правилах теории множеств.

Принцип суммы: если card A = m, card B = n и AÇ B = Æ , то card A È B = =m+n. На комбинаторном языке это означает: если объект A можно выбрать m способами, объект B другими n способами и их одновременный выбор невозможен, то выбор “A или B” может быть осуществлен m+n способами.

Принцип произведения: если card A=m, card B=n, то card (A´ B)=m+n. На комбинаторном языке это означает: если объект A может быть выбран m способами, при любом выборе A объект B может быть выбран n способами, то выбор “A и B” может быть осуществлен m× n способами.

Пример 1. A = 10 {различных шоколадок}, B = 5 { различных пачек печенья}. Выбор “A или B” означает, что выбирается что-то одно и способов выбора в этом случае будет 15. Выбор “A и B” означает, что выбирается 1 шоколадка и 1 пачка печенья и различных вариантов для такого выбора будет 50.

Пример 2. Бросают 2 игральные кости. Сколькими способами они могут выпасть так, что на каждой кости выпадет четное число очков либо на каждой кости выпадет нечетное число очков?

Пусть m – число возможностей для выпадения четного числа на одной кости, n – число возможностей для выпадения нечетного числа. Здесь m = n = 3. По правилу произведения количество выпадения четных чисел, как и нечетных, равно 9. По правилу суммы количество возможностей для выпадения двух четных и двух нечетных чисел будет 18.

Рассмотрим основные способы формирования выборок.

Определение. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Если порядок следования элементов несущественен, то выборка называется неупорядоченной.

Из определения следует, что две упорядоченные выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, являются различными.

Перестановки. Упорядоченные выборки, объемом n из n элементов, где все элементы различны, называются перестановками из n элементов. Число перестановок из n элементов обозначается P_n.

Теорема . P = n!

Доказательство проводится по индукции. Очевидно, если n = 1, то перестановка только одна и P₁= 1!. Пусть для n = k теорема верна и P_k = k!, покажем, что она тогда верна и для n = k+1. Рассмотрим (k+1)- й элемент, будем считать его объектом A, который можно выбрать k+1 способами. Тогда объект B – упорядоченная выборка из оставшихся k элементов по k. B соответствии с индуктивным предположением объект B можно выбрать k! способами. По принципу произведения выбор A и B можно осуществить k! (k+1) = (k+1)! способами. Совместный выбор A и B есть упорядоченная выборка из k + 1 элементов по k + 1.

Пример 3. Сколько существует способов, чтобы расположить на полке 10 различных книг? Ответ: 10!

Можно рассуждать иначе. Выбираем первый элемент, это можно сделать n способами. Затем выбираем второй элемент, это можно сделать (n - 1) способами. По правилу произведения упорядоченный выбор двух элементов можно осуществить n´ (n - 1) способами. Затем выбираем третий элемент, для его выбора останется n - 2 возможности, последний элемент можно выбрать единственным способом. Мы вновь приходим к формуле: n(n - 1)(n - r)... 1.

Размещения . Упорядоченные выборки объемом m из n элементов (m < n), где все элементы различны, называются размещениями. Число размещений из n элементов по m обозначается .

Теорема. =

Обозначим x = . Тогда оставшиеся (n – m) элементов можно упорядочить (n – m)! способами. По принципу произведения, если объект A можно выбрать x способами, объект B (n – m)! способами, то совместный выбор “A и B” можно осуществить x × (n – m)! способами, а выбор “A и B” есть перестановки и P_n = n! Отсюда x = =

Рассуждая иначе: первый элемент выбираем n способами, второй – (n – 1) способами и т.д., m–й элемент выбираем (n – m + 1) способом. По принципу произведения вновь имеем: n(n – 1)...(n – m +1), что совпадает с .

Пример 4. Группа из 15 человек выиграла 3 различных книги. Сколькими способами можно распределить эти книги среди группы?

Имеем = 15 × 14 × 13 = 2730.

Сочетания. Неупорядоченные выборки объемом m из n элементов (m < n) называются сочетаниями. Их число обозначается .

Теорема.

Доказательство. Очевидно, Действительно, объект A – неупорядоченная выборка из n элементов по m, их число . После того, как эти m элементов отобраны, их можно упорядочить m! способами (в роли объекта B выступает “порядок“ в выборке). Совместный выбор “A и B“ – упорядоченная выборка.

Пример 5 . Группа из 15 человек выиграла 3 одинаковых книги. Сколькими способами можно распределить эти книги?

Сочетания, размещения и перестановки являлись подмножествами исходного множества. Рассмотрим выборки, которые не являются подмножествами.

Размещения с повторениями. Упорядоченные выборки объемом m из n элементов, где элементы могут повторяться, называются размещениями с повторениями. Их число обозначается (n).

Теорема. (n) = n^m.

Доказательство. Первый элемент может быть выбран n способами, второй элемент также может быть выбран n способами и так далее, m -й элемент также может быть выбран n способами. По принципу произведения получаем n^m.

Пример 6 . Кодовый замок состоит из четырех разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций?

Здесь n = 10, m = 4 и ответом будет 10⁴.

Пример 7. Рассмотрим вектор длины m, каждая координата которого может принимать всего 2 значения: 0 или 1. Сколько будет таких векторов?

Это есть выборка, объемом m из двух элементов.Ответ: 2^m

Перестановки с повторениями. Пусть имеется n элементов, среди которых k₁ элементов первого типа, k₂ элементов второго типа и т.д., k_s элементов s-го типа, причем k₁+ k₂ +... + k_s = n. Упорядоченные выборки из таких n элементов по n называются перестановками с повторениями, их число обозначается C_n(k₁, k₂, ..., k_s). Числа C_n(k₁, k₂, ..., k_s) называются полиномиальными коэффициентами.

Теорема. C_n(k₁, ..., k_s)=

Доказательство проведем по индукции по s, т. е. по числу типов элементов. При s = 1 утверждение становится тривиальным: k₁ = n, все элементы одного типа и C_n(n) = 1. В качестве базы индукции возьмем s = 2, n = k₁+ k₂. В этом случаем перестановки с повторениями превращаются в сочетания из n элементов по k₁ (или k₂): выбираем k₁ место, куда помещаем элементы первого типа.

C_n(k₁, k₂) =

Пусть формула верна для s = m, т.е. n = k₁ +... + k_m и

C_n(k₁, ..., k_m)=

Докажем, что она верна для s = m + 1 (n = k₁ +... + k_m + k_m₊₁). В этом случае перестановку с повторениями можно рассматривать как совместный выбор двух объектов: объект A – выбор k _m_{+ 1}места для элементов (m + 1)-го типа; объект B – перестановка с повторениями из (n – k_m₊₁) элементов. Объект A можно выбрать способом, B – (k₁, ..., k_m) способами. По принципу произведения

и мы получили требуемую формулу.

Замечание . Числа называются биноминальными коэффициентами. Из этой формулы следует, что

Пример 8 . Сколько различных слов можно получить, переставляя буквы в слове “математика”?

Решение. Буква “а” входит 3 раза (k ₁= 3), буква “м” – 2 раза (k₂ = 2), “т” – 2 раза (k₃ = 2), буквы “е”, ”к”, ”и” входят по одному разу, отсюда k₃= k₄ = k₅ = 1.

C₁₀ (3, 2, , 2, 1, 1, 1) = =151200.

Сочетания с повторениями. Пусть имеется n типов элементов, каждый тип содержит не менее m одинаковых элементов. Неупорядоченная выборка объемом m из имеющихся элементов (их число ³ m´ n ) называется сочетанием с повторением. Число сочетаний с повторениями обозначается (n).

Теорема. (n) = .

Доказательство. Пусть в выборку вошло m₁ элементов первого типа, m₂ элементов второго типа, ...m_n – n-го типа. Причем каждое 0 £ m _i£ m и m₁+m₂+...+ m_n= =m. Сопоставим этой выборке вектор следующего вида: Очевидно, между множеством неупорядоченных выборок с повторениями и множеством векторов {b_n} существует биекция (докажите это! ). Следовательно, (n) равно числу векторов b_n. “ Длина вектора” b_n равна числу 0 и 1, или m+ +n–1. Число векторов равно числу способов, которыми m единиц можно поставить на m + n - 1 мест, а это будет .

Пример 9. В кондитерской имеется 7 видов пирожных. Покупатель берет 4 пирожных. Сколькими способами он может это сделать? (Предполагается, что пирожных каждого вида ³ 4).

Число способов будет

Пример10. Пусть V = {a, b, c}. Объем выборки m = 2. Перечислить перестановки, размещения, сочетания, размещения с повторениями, сочетания с повторениями.

1. Перестановки: {abc, bac, bca, acb, cab, cba}. P₃=3! =6.

2. Размещения: {(ab), (bc), (ac), (ba), (cb), (ca)}.

3. Сочетания: {(ab), (ac), (bc)}.

4. Размещения с повторениями: {(ab), (bc), (ac), (ba), (cb), (ca), (aa), (bb), (cc)}. (3)= 3² = 9.

5. Сочетания с повторениями: {(ab), (bc), (ca), (aa), (bb), (cc)}.

Задачи по комбинаторике

1. Расписание одного дня содержит 5 уроков. Определить количество таких расписаний при выборе из одиннадцати дисциплин.

Ответ: 55 440.

2. Комиссия состоит из председателя, его заместителя и еще пяти человек. Сколькими способами члены комиссии могут распределять между собой обязанности?

Ответ: 42.

3. Сколькими способами можно выбрать трех дежурных из группы в 20 человек?

Ответ: 1 140.

4. Сколько различных звукосочетаний можно взять на десяти выбранных клавишах рояля, если каждое звукосочетание может содержать от трех до десяти звуков?

Ответ: 968.

5. В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?

Ответ: 253.

6. Номера трамвайных маршрутов иногда обозначаются двумя цветными фонарями. Какое количество различных маршрутов можно обозначить, если использовать фонари восьми цветов?

Ответ: 64.

7. Чемпионат, в котором участвуют 16 команд, проводится в два круга (т.е. каждая команда дважды встречается с любой другой). Определить, какое количество встреч следует провести.

Ответ: 240.

8. Замок открывается только в том случае, если набран определенный трехзначный номер. Попытка состоит в том, что набирают наугад три цифры из заданных пяти цифр. Угадать номер удалось только на последней из всех возможных попыток. Сколько попыток предшествовало удачной?

Ответ: 124.

9. Из группы в 15 человек выбирают четырех участников эстафеты 800+400+200+100. Сколькими способами можно расставить спортсменов по этапам эстафеты?

Ответ: 32 760.

10. Команда из пяти человек выступает на соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколькими способами могут распределиться места, занятые членами этой команды?

Ответ: 25! /20!.

11. Сколькими способами можно расположить на шахматной доске две ладьи так, чтобы одна не могла взять другую? (Одна ладья может взять другую, если она находиться с ней на одной горизонтали или на одной вертикали шахматной доски.)

Ответ: 3 126.

12. Две ладьи различного цвета расположены на шахматной доске так, что каждая может взять другую. Сколько существует таких расположений?

Ответ: 896.

13. Порядок выступления восьми участников конкурса определяется жребием. Сколько различных исходов жеребьевки при этом возможно?

Ответ: 8!.

14. Тридцать человек разбиты на три группы по десять человек в каждой. Сколько может быть различных составов групп?

Ответ: 30! /(10! ) .

15. Сколько четырехзначных чисел, делящихся на 5, можно составить из цифр 0, 1, 3, 5, 7, если каждое число не должно содержать одинаковых цифр?

Ответ: 42.

16. Сколько различных светящихся колец можно сделать, расположив по окружности 10 разноцветных лампочек (кольца считаются одинаковыми при одинаковом порядке следования цветов)?

Ответ: 9!.

17. На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй тома не стояли рядом?

Ответ:

18. Четыре стрелка должны поразить восемь мишеней (каждый по две). Сколькими способами они могут распределить мишени между собой?

Ответ: 2 520.

19. Из группы в 12 человек ежедневно в течение 6 дней выбирают двух дежурных. Определить количество различных списков дежурных, если каждый человек дежурит один раз.

Ответ: 12! /(2! ) .

20. Сколько четырехзначных чисел, составленных из цифр 0, 1, 2, 3, 4, 5, содержат цифру 3 (цифры в числах не повторяются )?

Ответ: 204.

21. Десять групп занимаются в десяти расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы №1 и №2 находились бы в соседних аудиториях?

Ответ: 2× 9!.

22. В турнире участвуют 16 шахматистов. Определить количество различных расписаний первого тура (расписания считаются различными, если отличаются участниками хотя бы одной партии; цвет фигур и номер доски не учитываются).

Ответ: 2 027 025.

23. Шесть ящиков различных материалов доставляются на пять этажей стройки. Сколькими способами можно распределить материалы по этажам? В скольких вариантах на пятый этаж доставлен какой-либо один материал?

Ответ: 5⁶; 6× 4⁵.

24. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?

Ответ: 2¹⁰.

25. Поезд метро делает 16 остановок, на которых выходят все пассажиры. Сколькими способами могут распределиться между этими остановками 100 пассажиров, вошедших в поезд на конечной остановке?

Ответ: 16¹⁰⁰.

26. Сколько трехзначных чисел, делящихся на 3, можно составить из цифр 0, 1, 2, 3, 4, 5, если каждое число не должно содержать одинаковых цифр?

Ответ: 40.

27. Собрание из 80 человек избирает председателя, секретаря и трех членов ревизионной комиссии. Сколькими способами это можно сделать?

Ответ: 80! (3! × 75! ).

28. Из 10 теннисисток и 6 теннисистов составляют 4 смешанные пары. Сколькими способами это можно сделать?

Ответ: 10! /48.

29. Три автомашины №1, 2, 3 должны доставить товар в шесть магазинов. Сколькими способами можно использовать машины, если грузоподъемность каждой из них позволяет взять товар сразу для всех магазинов и если две машины в один и тот же магазин не направляются? Сколько вариантов маршрута возможно, если решено использовать только машину №1?

Ответ: 3⁶× 6!.

30. Четверо юношей и две девушки выбирают спортивную секцию. В секцию хоккея и бокса принимают только юношей, в секцию художественной гимнастики – только девушек, а в лыжную и конькобежную секции – и юношей, и девушек. Сколькими способами могут распределиться между секциями эти шесть человек?

Ответ: 2304.

31. Из лаборатории, в которой работает 20 человек, 5 сотрудников должны уехать в командировку. Сколько может быть различных составов этой группы, если начальник лаборатории, его заместитель и главный инженер одновременно уезжать не должны?

Ответ: 15 368.

32. В фортепьянном кружке занимаются 10 человек, в кружке художественного слова –15, в вокальном кружке – 12, в фотокружке – 20 человек. Сколькими способами можно составить бригаду из четырех чтецов, трех пианистов, пяти певцов и одного фотографа?

Ответ: 15! 10/7!

33. Двадцать восемь костей домино распределены между четырьмя игроками. Сколько возможно различных распределений?

Ответ:

34. Из группы в 15 человек должны быть выделены бригадир и 4 члена бригады. Сколькими способами это можно сделать?

Ответ: 15 015.

35. Пять учеников следует распределить по трем параллельным классам. Сколькими способами это можно сделать?

Ответ: 3⁵.

36. Лифт останавливается на 10 этажах. Сколькими способами могут распределиться между этими остановками 8 пассажиров, находящихся в лифте?

Ответ: 10⁸.

37. Восемь авторов должны написать книгу из шестнадцати глав. Сколькими способами возможно распределение материала между авторами, если два человека напишут по три главы, четыре – по две, два – по одной главе книги?

Ответ: 16! /(2⁶× 3²).

38. В шахматном турнире участвуют 8 шахматистов третьего разряда, 6 – второго и 2 перворазрядника. Определить количество таких составов первого тура, чтобы шахматисты одной категории встречались между собой (цвет фигур не учитывается).

Ответ: 420.

39. Из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 составляются всевозможные пятизначные числа: не содержащие одинаковых цифр. Определить количество чисел, в которых есть цифры 2, 4 и 5 одновременно.

Ответ: 1800.

40. Семь яблок и два апельсина надо положить в два пакета так, чтобы в каждом пакете был хотя бы один апельсин и чтобы количество фруктов в них было одинаковым. Сколькими способами это можно сделать?

Ответ: 105.

41. Буквы азбуки Морзе состоят из символов (точек и тире). Сколько букв можно изобразить, если потребовать, чтобы каждая буква содержала не более пяти символов?

Ответ: 62.

42. Номер автомобильного прицепа состоит из двух букв и четырех цифр. Сколько различных номеров можно составить, используя 30 букв и 10 цифр?

Ответ: 9× 10⁶.

43. Садовник должен в течение трех дней посадить 10 деревьев. Сколькими способами он может распределить по дням работу, если будет сажать не менее одного дерева в день?

Ответ: 36.

44. Из вазы, где стоят 10 красных и 4 розовых гвоздики, выбирают один красный и два розовых цветка. Сколькими способами это можно сделать?

Ответ: 60.

45. Двенадцати ученикам выданы два варианта контрольной работы. Сколькими способами можно посадить учеников в два ряда, чтобы у сидящих рядом не было одинаковых вариантов, а у сидящих друг за другом был один и тот же вариант?

Ответ: 2(6! )².

46. Каждый из десяти радистов пункта А старается установить связь с каждым из двадцати радистов пункта Б. Сколько возможно различных вариантов такой связи?

Ответ: 2²⁰⁰.

47. Шесть ящиков различных материалов доставляют на восемь этажей стройки. Сколькими способами можно распределить материалы по этажам? В скольких вариантах на восьмой этаж будет доставлено не более двух материалов?

Ответ: 8⁶; 8⁶–13× 7⁵.

48. Сколькими способами можно построить в одну шеренгу игроков двух футбольных команд так, чтобы при этом два футболиста одной команды не стояли рядом?

Ответ: 2(11! )².

49. На книжной полке книги по математике и по логике – всего 20 книг. Показать, что наибольшее количество вариантов комплекта, содержащего 5 книг по математике и 5 книг по логике, возможно в том случае, когда число книг на полке по каждому предмету равно 10.

Ответ: C⁵_10–_x× C⁵₁₀₊_x(C⁵₁₀)².

50. Лифт, в котором находятся 9 пассажиров, может останавливаться на десяти этажах. Пассажиры группами выходят по два, три и четыре человека. Сколькими способами это может произойти?

Ответ: 10! /4.

51. «Ранним утром на рыбалку улыбающийся Игорь мчался босиком». Сколько различных осмысленных предложений можно составить, используя часть слов этого предложения, но не изменяя порядка их следования?

Ответ: 23.

52. В шахматной встрече двух команд по 8 человек участники партий и цвет фигур каждого участника определяются жеребьевкой. Каково число различных исходов жеребьевки?

Ответ:

53. A и B и еще 8 человек стоят в очереди. Сколькими способами можно расположить людей в очереди, чтобы A и B были отделены друг от друга тремя лицами?

Ответ: 6 × 8! × 2!.

54. Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если а) цифры не повторяются; б) цифры могут повторяться; в) используются только нечетные цифры и могут повторяться; г) должны получиться только нечетные числа и цифры могут повторяться.

Ответ: а) 5 × 5 × 4 × 3=300; б) 5 × 6 = 1080; в) 3⁴; г) 5 × 6 × 6 × 3 = 540.

55. В классе изучается 10 предметов. Сколькими способами можно составить расписание на понедельник, если в понедельник должно быть 6 уроков и все разные?

Ответ:

56. На одной прямой взято m точек, на параллельной ей прямой n точек. Сколько треугольников с вершинами в этих точках можно получить?

Ответ:

57. Сколько есть пятизначных чисел, которые читаются одинаково справа налево и слева направо, например, 67876.

Ответ: 9 × 10 × 10 = 900.

58. Сколько разных делителей (включая 1 и само число) имеет число

3⁵ × 5⁴?

Ответ: 30.

59. В прямоугольной матрице A = {a_ij} m строк и n столбцов. Каждое a_ijÎ {+1, –1}, причем произведение a_ij по любой строке или любому столбцу равно 1. Сколько таких матриц?

Ответ: 2^{(m–1)(n–1)}.

60. В комнате n лампочек. Сколько разных способов освещения комнаты,

при которых горит:

а) ровно k лампочек (k < n);

б) хотя бы одна лампочка.

Ответ: а) ; б) = 2n–1.

61. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей?

Ответ: = 126.

62. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей?

Ответ: = 210.

63. Имеется p белых и q черных шаров. Сколькими способами их можно выложить в ряд, чтобы никакие 2 черных шара не лежали рядом (q £ p + 1)?

Ответ: .

64. Имеется p разных книг в красных переплетах и q разных книг в синих переплетах (q £ p + 1). Сколькими способами их можно расставить в ряд, чтобы никакие две книги в синих переплетах не стояли рядом?

Ответ: .

65. Сколькими способами можно упорядочить {1, 2, ... n} чисел так, чтобы числа 1, 2, 3 стояли рядом в порядке возрастания?

Ответ: (n – 2)!.

66. На собрании должны выступить 4 докладчика: A, B, C и D, причем B не может выступить раньше A. Сколькими способами можно установить их очередность.

Ответ: 12 = 3! + 2× 2 +2.

67. Сколькими способами m + n + s предметов можно распределить на 3 группы, чтобы в одной группе было m предметов, в другой – n, в третьей – s предметов.

Ответ:

68. Сколько целых неотрицательных решений имеет уравнение x1+ x2+... + xm= n.

Ответ: .

69. Найти число векторов Z = (a1a2... an), координаты которых удовлетворяют условиям:

1) aiÎ {0, 1};

2) aiÎ {0, 1, ... k – 1};

3) aiÎ {0, 1, ... ki– 1};

4) aiÎ {0, 1} и a1+ a2+... + an= r.

Ответ: 1) 2n; 2) kn; 3) k1k2... kn; 4) .

70. Каково число матриц {aij}, где aijÎ {0, 1} и в которой m строк и n столбцов? 1) строки могут повторяться; 2) строки попарно различны.

Ответ: 1) 2m× n; 2) .

71. Дано m предметов одного сорта и n другого. Найти число выборок, составленных из r элементов одного сорта и s другого.

Ответ: .

72. Сколькими способами число n можно представить в виде суммы k натуральных слагаемых (представления, различающиеся лишь порядком слагаемых считаются разными).

Ответ: .

73. Бросаются 10 одинаковых игральных костей. Сколькими способами они могут упасть так, что:

1) ни на одной кости не выпадет 6 очков;

2) хотя бы на одной кости выпадет 6 очков;

3) ровно на 3-х костях выпадет 6 очков;

4) ровно на 3-х костях выпадет 6 очков, на 2-х других выпадет 5 очков.

Ответ: 5¹⁰, 6¹⁰-5¹⁰, 24´ 5⁸, 630´ 4⁶

74. Считая, что телефонные номера состоят из 7 цифр, причем могут начинаться и с 0 тоже, найти число телефонных номеров, таких что:

1) 4 последние цифры одинаковы и не встречаются среди первых 3-х (первые 3 цифры различны.);

2) все цифры различны;

3) номер начинается с цифры 5;

4) номер содержит три цифры 5, две цифры 1 и две цифры 2.

Ответ: 5040, , 10⁶, 210.

75. 10 человек, среди которых Иванов и Петров, размещаются в гостинице в двух 3-х местных и в одном 4-х местном номерах. Сколькими способами они могут быть размещены? Сколькими способами их можно разместить, если Иванов и Петров помещены в 4-х местный номер?

Ответ: 4200, 560.

76. 52 карты раздаются 4-м игрокам, каждому по 13 карт. Сколькими способами их можно раздать, если

1) каждый игрок получит туза;

2) один из игроков получит все 13 карт единой масти;

3) все тузы попадут к одному из игроков;

4) 2 определенных игрока не получат ни одного туза.

Ответ: , , , .

77. Регистр калькулятора содержит 8 разрядов. Сколько будет 8-ми значных чисел, если

1) регистр содержит ровно 2 одинаковые цифры;

2) регистр содержит ровно 2 пары одинаковых цифр;

3) регистр содержит ровно 3 одинаковые цифры;

4) регистр содержит не более 3-х различных цифр.

Ответ: , , , .

78. Сколькими способами можно выстроить 9 человек:

1) в колонну по одному;

2) в колонну по 3, если в каждой шеренге люди выстраиваются по росту и нет людей одинакового роста?

Ответ: 9!, .

79. Из n букв, среди которых a встречается α раз, буква b встречается β раз, а остальные буквы попарно различны, составляются слова. Сколько среди них будет различных r-буквенных слов, содержащих h раз букву a и k раз букву b?

Ответ: .

80. Имеется колода из 4n (n³ 5) карт, которая содержит карты 4-х мастей по n карт каждой масти, занумерованных числами 1, 2…n. Подсчитать, сколькими способами можно выбрать 5 карт так, что среди них окажутся:

1) 5 последовательных карт одной масти;

2) 4 карты из 5-ти с одинаковыми номерами;

3) 3 карты с одним номером и 2 карты с другим;

4) 5 карт одной масти;

5) 5 последовательно занумерованных карт;

6) 3 карты из 5-ти с одним и тем же номером;

7) не более 2-х карт каждой масти.

Ответ: 4(n–4), 4n(n–1), 12n(n–1), , 4⁵(n–4), , .

81. Сколькими способами можно расставить n нулей и k единиц так, чтобы между любыми 2-мя единицами находилось не менее m нулей?

Ответ: .

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒