Теорема 3. ,n 0 .
Доказательство.Множество разбиенийX={1,2,,
n+1} состоит из
классов, зависящих от блокаAсодержащегоn+1.
Для такихAбудет
справедливо включениеX\A
{1,
2,,
n}. Отсюда каждое
разбиение можно получить, выбрав блок An+1 и разбиение(X\A).
Выбор блокаAс |A|=k+1,
будет осуществляться выбором
подмножества из {1,2,,n}, состоящего изkэлементов. Следовательно,
.
2.5. Упражнения
Размещения
Сколькими способами можно составить трехцветный флаг (рис. 2.4) из материа-
Рис. 2.4. Пример флага
лов семи цветов. Одна из полос должна быть красной.
Ответ: 7363.
Скольким способами можно раскрасить 4 полосы флага в 7 цветов, так, чтобы по крайней мере две полосы имели одинаковый цвет?
Ответ:
.
Скольким способами можно раскрасить 4 полосы флага в 7 цветов, так, чтобы рядом находящиеся полосы имели различные цвета?
Ответ: 7∙ 63.
Сколько перестановок : {1,2, ∙∙∙, 5}{1,2, ∙∙∙, 5} удовлетворяют условию(1)2 ?
В соревновании принимают участие 8 спортсменов. Сколькими способами могут быть разделены медали (золотые, серебряные и бронзовые?)
Найти число функций {1,2,3}{1,2,3,4,5}.
Найти число инъекций {1,2,3}{1,2,3,4,5}.
Сколько чисел между 1000 и 10000 состоят из различных цифр?
Сколько семизначных чисел (не начинающихся с 0) состоят из различных цифр?
Сочетания
Доказать тождества непосредственно из определения числа
(1)
,
(2)
,
(3)
.
Из содержащей 52 карты колоды вынимают 10 карт. Какова вероятность, что среди них окажется
(1) хотя бы один
туз? Ответ:
(2) ровно один
туз? Ответ:
(3) не менее двух
тузов? Ответ:
(4) ровно два
туза? Ответ:
Из содержащей 52 карты колоды вынимают 10 карт. Какова вероятность, что среди них окажется
(1) 4 туза, 2 короля, 3 дамы;
(2) 2 туза, 2 короля, 2дамы;
(3) 1 туз, 1 королm, 2 дамы, 3 десятки;
(4) 4 туза, 4короля,2дамы;
(5) 2туза,3короля,1дама, 1 десятка;
(6) 3 туза, 2 короля, 4 дамы;
Разложением числа mназывается конечная последовательность (x1, x2, , xn) неотрицательных целых чисел, таких чтоx1+ x2+ + xn=m. Сколько разложений числа 19 состоит лишь из чисел 2 и 3 ?
Указание. Если в разложении pдвоек иqтроек, то 2p+ 3q= 19. Отсюда получаем следующие варианты разложения, приведенные в таблице 2.4.
Таблица 2.4
Варианты разложения
-
p=2
q=5
число разложений
p=5
q=3
число разложений
p=8
q=1
число разложений
Ответ:
.
Сколько разложений числа 12 состоит из чисел 2 и 3 ?
Ответ:
= 12.
Сколькими способами можно разложить число 1024 в произведение трех натуральных чисел, каждое из которых больше 1 ?
Указание. Это число решений уравнения x1+ x2,+ x3= 10, гдеxi>0.
Ответ:
= 36.
Сколько существует на плоскости непрерывных путей из точки (0,0) в точку (n,n)NN, состоящих из направленных отрезков, вектора которых равны (1,0) или (0,1) ?
Найти число непрерывных путей в декартовой плоскости, соединяющих точку (0,0) с точкой (m,n) NN, проходящих через точку (p,q) и состоящих из направленных отрезков, вектора которых равны (1,0) или (0,1) ?
Найти число решений уравнения x1+ x2+ x3+ x4 + x5= 20 , гдеxi > 0.
Найти число решений уравнения x1+ x2+ x3+ x4 + x5= 15 , гдеxi 0.
Найти число возрастающих функций {1,2,3,4,5}{1,2,3,4,5,6,7}.
Найти число неубывающих сюръекций {1,2,3,4,5,6,7}{1,2,3,4,5}.
Найти число неубывающих функций {1,2,3,4,5}{1,2,3,4,5}.
Найти количество десятичных неотрицательных целых чисел, состоящих из не более чем nцифр, расположенных в неубывающем порядке (цифра 0 не допускается первой для ненулевых чисел). Например, приn=2, такие числа будут равны
0
1, 2, 3, 4, 5, 6, 7, 8, 9,
11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, ∙ ∙ ∙ , 89, 99.
Ответ:
= 36.
Найти количество десятичных неотрицательных целых чисел, состоящих цифр, расположенных в возрастающем порядке.
Ответ:
Найти число неотрицательных целых чисел, десятичная запись которых состоит из nразрядов и содержит все цифры, расположенные в невозрастающем порядке.
Ответ:
.
Какое количество mn–матриц можно составить из неотрицательных целых чиселaij 0, таких что aij = k.
Ответ:
.