Kombinatorika

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

3.Сколько существует 6-значных чисел, цифры каждого из которых различны и не являются степенями 2?

4.Задача о числе размещений.

41

1.Сколько существует 6-значных чисел, цифры каждого из которых различны и произведение цифр максимальное?

2.Сколько существует 2-значных чисел с различными цифрами, не являющимися квадратами?

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

4.Задача о числе перестановок.

42

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

2.Сколько существует 4-значных чисел, цифры каждого из которых возрастают?

3.Сколько существует 2-значных чисел с различными четными цифрами?

4.Комбинаторное правило сложения.

43

1.Сколько существует 6-значных чисел с цифрами в убывающем порядке?

2.Сколько существует 5-значных чисел с различными цифрами?

3.Сколько существует 6-значных чисел, цифры каждого из которых различны и сумма цифр минимальная?

31

4. Комбинаторное правило сложения.

44

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

2.Сколько существует 2-значных чисел с различными цифрами, квадрат которых 1-значен, и идущими в убывающем порядке?

3.Сколько существует 10-значных чисел с различными цифрами?

4.Задача о числе размещений.

45

1.Сколько существует 2-значных чисел, цифры каждого из которых не являются квадратами и убывают?

2.Сколько существует 5-значных чисел, цифры каждого из которых различны и четны?

3.Сколько существует 7-значных чисел с различными цифрами?

4.Комбинаторное правило умножения.

46

1.Сколько существует 4-значных чисел с различными цифрами?

2.Сколько существует 5-значных чисел с цифрами в возрастающем порядке?

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

4.Комбинаторное правило сложения.

47

1.Сколько существует 2-значных чисел, цифры каждого из которых четны и возрастают?

32

2.Сколько существует 5-значных чисел, цифры каждого из которых различны и нечетны?

3.Сколько существует 6-значных чисел с различными цифрами?

4.Задача о числе перестановок.

48

1.Сколько существует 3-значных чисел, цифры каждого из которых не являются простыми числами и различны?

2.Сколько существует 4-значных чисел, цифры каждого из которых различны и являются степенями 2?

3.Сколько существует 2-значных чисел, цифры каждого из которых являются степенями 2 и возрастают?

4.Комбинаторное правило сложения.

49

1.Сколько существует 3-значных чисел, цифры каждого из которых различны и являются степенями 3?

2.Сколько существует 3-значных чисел с различными цифрами, являющимися квадратами?

3.Сколько существует 3-значных чисел, цифры каждого из которых не делятся на 3 и убывают?

4.Задача о числе перестановок.

50

1.Сколько существует 6-значных чисел, цифры каждого из которых различны и не делятся на 3?

2.Сколько существует 2-значных чисел с четными цифрами в возрастающем порядке?

3.Сколько существует 3-значных чисел с различными цифрами?

33

4. Задача о числе перестановок.

51

1.Сколько существует 4-значных чисел с цифрами, не являющимися степенями 3 и идущими в убывающем порядке?

2.Сколько существует 7-значных чисел, цифры каждого из которых различны и произведение цифр максимальное?

3.Сколько существует 3-значных чисел с различными цифрами, являющимися квадратами?

4.Задача о числе размещений.

52

1.Сколько существует 5-значных чисел, цифры каждого из которых различны и нечетны?

2.Сколько существует 4-значных чисел, цифры каждого из которых четны и убывают?

3.Сколько существует 5-значных чисел с различными цифрами?

4.Задача о числе перестановок.

53

1.Сколько существует 6-значных чисел, цифры каждого из которых различны и не являются степенями 2?

2.Сколько существует 5-значных чисел, цифры каждого из которых не являются простыми числами и различны?

3.Сколько существует 5-значных чисел, цифры каждого из которых не являются степенями 2 и убывают?

4.Комбинаторное правило сложения.

34

54

1.Сколько существует 5-значных чисел, цифры каждого из которых не делятся на 3 и убывают?

2.Сколько существует 7-значных чисел, цифры каждого из которых различны и не являются степенями 3?

3.Сколько существует 5-значных чисел с различными цифрами, не являющимися квадратами?

4.Задача о числе перестановок.

Перейдем теперь к рассмотрению комбинаторных моделей с повторением и начнем с наиболее простой из них – размещений с повторением.

8Размещения с повторением

Вэтой комбинаторной модели каждая комбинация определяется m

элементами базового множества B = fb1; b2; : : : ; bng, которые могут

повторяться и идут в каком-либо порядке (bi1; bi2; : : : ; bim). Такую комбинацию называют размещением с повторением n элементов на m

местах. В отличие от размещений без повторения, где обязательно m · n, в размещениях с повторениями m ничем не ограничено и может быть как меньше, так и больше n.

Задача о числе размещений с повторениями может быть сформулирована следующим образом:

Каким числом способов n элементов могут быть размещены на m местах?

Размещение с повторениями так же, как и размещение без повторений, является кортежем (вектором), у которого каждый элемент базового множества может быть любым элементом базового множества в отличие от размещений без повторения, которые не могут повторяться. Поэтому каждое размещение с повторением является элементом пря-

мого произведения Bm (базового множества на себя m раз). Отсюда следует число размещений с повторениями Amn 6 из n элементов на m

6 Так мы будем обозначать число размещений с повторениями.

35

местах как число элементов прямого произведения Bm:

Amn = jBmj = nm:

Пример 8. Сколько существует 9-значных чисел, у которых более 7 цифр являются простыми числами?

Решение. Цифры, которые являются простыми числами (имеют ровно 2 различных делителя: 1 и само число), это 2, 3, 5 и 7. Поэтому не более чем 1 цифра берется из множества Bn = f0; 1; 4; 6; 8; 9g, а остальные цифры берутся из множества Bp = f2; 3; 5; 7g. Примерами заданных условием задачи чисел являются 232057372, 575757575,...

Для того чтобы сделать рассматриваемое множество A чисел однородным, разобьем его на 2 подмножества:

²A0 – состоящее только из цифр, являющихся простыми числами;

²A1 – содержащее ровно 1 цифру, не являющуюся простым числом.

Так как A0 \ A1 = ; и A0 [ A1 = A, то jAj = jA0j + jA1j, то есть можно воспользоваться правилом сложения.

Найдем jA0j. Каждая цифра числа из A0 принадлежит множеству Bp и может повторяться. Поэтому здесь нужно выбрать комбинаторную модель с повторением элементов. Числа, состоящие из одних и тех же цифр, различны, если одинаковые цифры стоят в разных разрядах 9-значного числа. Поэтому комбинаторную модель следует искать среди моделей с порядком элементов в комбинации. Количество повторений той или иной цифры в числе не фиксировано, значит это не модель перестановок с повторениями. Попытаемся использовать комбинаторную модель размещений с повторениями (по признакам годится только она). Пусть C – множество размещений с повторениями элементов из множества Bp на 9 местах. Рассмотрим функцию f, ставящую каждой комбинации c 2 C число, цифры которого являются элементами c, идущими в том же порядке: f((5; 7; 5; 7; 5; 7; 5; 7; 5)) = 5757575. Она всюду определена на C, разным комбинациям ставит в соответствие различные числа (а потому обратное соответствие есть функция f¡1, которая числу из A0 ставит в соответствие комбинацию из C), и множество значений f есть все множество A0 (функция f¡1 всюду определена). Поэтому f осуществляет 1-1с между множествами C и

36

A0. По теореме об 1-1с конечных множеств

jA0j = jCj = 49:

Теперь будем определять размер множества A1. Поскольку числа из A1 имеют 1 цифру из множества Bn и если эта цифра 0, то она может быть любым разрядом числа кроме 1-го, а если она не 0, то может быть любым разрядом числа, включая и 1-й. Это осложняет выбор простой комбинаторной модели, и потому мы вновь разобьем множество A1 на

2подмножества:

²A10 – включающее 1 цифру 0 и остальные из Bp;

²A11 – включающее 1 цифру из Bn n f0g и остальные из Bp.

Так как A10 \ A11 = ; и A10 [ A11 = A, то jA1j = jA10j + jA11j, то есть можно воспользоваться правилом сложения.

Для определения jA10j построим генерацию этих чисел:

1.Выбор места для цифры 0 (любой из разрядов кроме 1-го) – 8 способов.

2.Размещение на остальных разрядах (их 8) цифр из Bp (их 4) – это размещение с повторением (обоснование аналогично рассмотренному),

апотому число таких размещений равно 48.

Так как действия независимы (выбираются цифры разных разрядов на 1-м и 2-м шагах), а также число размещений на шаге 2 не зависит от выбора разряда на шаге 1, то

jA10j = 8 ¢ 48 = 2 ¢ 49:

Для определения jA11j построим генерацию этих чисел:

1.Выбор цифры из Bn n f0g – 5 способов.

2.Выбор разряда для этой цифры – 9 способов.

3.Размещение на остальных разрядах (их 8) цифр из Bp (их 4) – это размещение с повторением (обоснование аналогично рассмотренному),

апотому число таких размещений равно 48.

Так как действия независимы (выбираются цифры разных разрядов на 2-м и 3-м шагах, а также независимы выбор разряда на 2-м шаге и выбор цифры на 1-м шаге), и число размещений на шаге 3 не зависит

37

от выбора разряда на шаге 1 и цифры на шаге 2, то воспользуемся правилом умножения:

jA11j = 5 ¢ 9 ¢ 48 = 45 ¢ 48:

Выполняя сложение полученных размеров множеств, получим:

jAj = jA0j + jA10j + jA11j = 49 + 2 ¢ 49 + 45 ¢ 48 = 48(4 + 8 + 45) = 57 ¢ 48:

Ответ: существует 57¢48 9-значных чисел, у которых более 7 цифр являются простыми числами.

9Перестановки с повторениями

Базовое множество B этой модели содержит k типов элементов комбинации B = fb1; b2; : : : ; bkg. Каждая комбинация модели является кортежем (вектором) из n элементов базового множества (n ¸ k) и при этом задано количество элементов в комбинации каждого типа:

ni (i 2 1; k) элементов типа bi. Причем n = Pki=1 ni. Комбинации отличаются расположением элементов и называются перестановками с

повторением. Следует заметить, что если переставить 2 элемента одного типа, то мы не получим новой перестановки.

Задача о числе перестановок с повторениями формулируется следующим образом:

Каким числом способов можно переставить последовательность из n элементов, содержащих ni (i = 1; : : : ; k) элементов каждого типа, которые неразличимы между собой?

Обозначим через Pn;n1;:::;nk множество перестановок из n элементов k типов с числами n1; : : : ; nk элементов соответствующих типов

(n = Pki=1 ni). Для вывода формулы этой задачи определим следующую последовательность действий для генерации каждой комбинации:

1.Выбор множества из n1 мест для элементов 1-го типа (b1) – Cnn1 способов.

2.Выбор множества из n2 мест для элементов 2-го типа (b2) – Cnn¡2 n1 способов.

......................................................................

38

k-1. Выбор множества из nk¡1 мест для элементов (k-1)-го типа (bk¡1)

k.Выбор множества из nk мест для элементов k-го типа (bk)

– Cnn¡k n1¡¢¢¢¡nk¡1 = Cnnkk = 1 способ.

Каждая генерация строит перестановку с повторением из множества

Pn;n1;:::;nk . Любая перестановка из множества Pn;n1;:::;nk может быть получена генерацией. Действия генерации независимы, так как опреде-

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

Отметим, что при k = 2 получается формула числа сочетаний, так как n2 = n ¡ n1. Это объяснимо следующим образом: при выборе n1 мест для элементов 1-го типа мы автоматически выбираем оставшиеся n ¡ n1 мест для элементов 2-го типа.

Пример 9. Каким числом способов можно разбить n-элементное множество на k непересекающихся подмножеств с числом элементов этих подмножеств n1 : : : nk, где n = Pki=1 ni?

Решение. Каждому разбиению n-элементного множества на k непересекающихся подмножеств с числом их элементов n1; : : : ; nk, где n = Pki=1 ni, отнесем вектор из натуральных чисел от 1 до k, в котором число i (i = 1; : : : ; k) повторяется ni раз и определяет места элементов исходного множества, на котором стоят элементы i-го подмножества. Эта функция f всюду определена на множестве R разбиений на подмножества. Соответствие f¡1 между множеством V таких векторов и множеством R разбиений на подмножества также всюду определено на

7 Так мы будем обозначать число перестановок с повторением из n элементов k типов с числами

n1; : : : ; nk элементов соответствующих типов (n = Pk ni).

i=1

39

V и функционально (по вектору v 2 V однозначно определяется разбиение на подмножества, удовлетворяющее условиям задачи), а потому является 1-1с. Но число векторов множества V определяется формулой

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

10 Сочетания с повторениями

Базовое множество B этой модели содержит n типов элементов комбинации B = fb1; b2; : : : ; bng. В этой комбинаторной модели каждая комбинация определяется множеством из m элементов базового множества B, которые могут повторяться в комбинации (bi1; bi2; : : : ; bim). Такую комбинацию называют сочетанием с повторением m из n элементов. В отличие от сочетаний без повторения, где обязательно m · n, в сочетаниях с повторениями m ничем не ограничено и может быть как меньше или равно, так и больше n.

Задача о числе сочетаний с повторениями формулируется следующим образом:

Каким числом способов можно выбрать множество m элементов из n элементов базового множества B = fb1; b2; : : : ; bng, которые могут повторяться в комбинации?

Приведем пример. Пусть базовое множество состоит из 3 элементов B = fa; b; cg. Тогда все сочетания по 2 из базового множества выглядят следующим образом:

fa; bg; fa; cg; fb; cg; fa; ag; fb; bg; fc; cg;

а все сочетания по 4 элемента представляют собой следующие множества:

fa; a; b; cg; fa; b; b; cg; fa; b; c; cg; fa; a; b; bg; fa; a; c; cg; fb; b; c; cg; fa; a; a; bg; fa; a; a; cg; fb; b; b; ag; fb; b; b; cg; fc; c; c; ag; fc; c; c; bg; fa; a; a; ag; fb; b; b; bg; fc; c; c; cg:

Для решения задачи мы любым способом определим порядок элементов базового множества и каждому сочетанию m элементов из n

40