Просолупов Е.В. Конспект курса: Основы дискретной математики

Подождите немного. Документ загружается.

Следствие 1.6.3 . Рассмотрим неравенство

+ x

+ · · · + x

≤ n, (∗∗)

где n — заданное число из N

. Пусть, N

≤

(n, k) — число решений этого

неравенства на неотрицательных целых числах. Тогда

≤

(n, k) =

n + k

. (17)

Доказательство. Пусть c

+ c

+ · · · + c

≤ n, c

∈ N

. Тогда, обозначим

k+1

= n − c

+ c

+ · · · + c

. {c

, c

, ..., c

, c

k+1

} — решение уравнения

+ x

+ · · · + x

+ x

k+1

= n.

Обратно, для любого решения c

, c

, ..., c

, c

k+1

уравнения x

+· · ·+

+ x

k+1

= n, очевидно, верно, что c

+ c

+ · · · + c

≤ n.

Таким образом, множеству решений неравенства (**)

взаимооднозначно соответствует множество решений уравнения

+ x

+ · · · + x

+ x

k+1

= n. Тогда по следствию 1.6.2

≤

(n, k) = N

(n, k + 1) =

n + k

1.6.2 Разбиения натуральных чисел

Определение 1.6.2 . Набор (λ

, λ

, ..., λ

), λ

∈ N, называется

разбиением числа n ∈ N, если n = λ

+λ

+· · ·+λ

, λ

≥ λ

≥ · · · ≥ λ

> 0

Пример 1.6.2 . Существует 5 различных разбиений числа n = 4:

1 + 1 + 1 + 1

2 + 1 + 1

2 + 2

3 + 1

Замечание 1.6.1 . Можно использовать и другое определение

разбиения натурального числа:

Определение 1.6.3 . Разбиением числа n ∈ N называется

представление n в виде неупорядоченной суммы натуральных чисел

чисел.

Действительно, можно считать, что разбиение {λ

, λ

, ..., λ

} —

произвольный неупорядоченный набор, такой что n = λ

+ λ

+ · · · + λ

Тогда расставив элементы λ

в другом порядке мы получим то же

самое разбиение. Чтобы получить возможность определять, имеем

ли мы дело с двумя различными разбиениями, или с одним и тем

же набором, но в с элементами следующими в другом порядке, удобно

расставить элементы λ

по убыванию. В таком случае, любому

разбиению будет соответствовать упорядоченная последовательность,

удовлетворяющая определению 1.6.2.

Обозначим p

(n) — число разбиений n на k частей.

Утверждение 1.6.4 . Пусть k, n ∈ N, k > 1 и n > k. Тогда

(n) = p

k−1

(n − 1) + p

(n − k). (18)

Доказательство. Пусть

(n) = {(λ

, λ

, ..., λ

) | n = λ

+ λ

+ · · · + λ

≥ λ

≥ · · · ≥ λ

> 0, λ

∈ N, i = 1, k},

A = {(λ

, λ

, ..., λ

) | (λ

, λ

, ..., λ

) ∈ S

(n), λ

= 1},

B = {(λ

, λ

, ..., λ

) | (λ

, λ

, ..., λ

) ∈ S

(n), λ

≥ 2}.

Тогда S

(n) = A ∪ B и A ∩ B = ∅; |S

(n)| = |A| + |B|.

|A| = |{(λ

, λ

, ..., λ

k−1

) | λ

+ λ

+ · · · + λ

k−1

= n − 1,

≥ λ

≥ · · · ≥ λ

k−1

> 0, λ

∈ N}| = |S

k−1

(n − 1)| = p

k−1

(n − 1).

|B| = |{(λ

, λ

, ..., λ

) | λ

+ λ

+ · · · + λ

= n,

≥ λ

≥ · · · ≥ λ

> 1, λ

∈ N}| =

Сделаем замену µ

= λ

− 1, i = 1, k.

= |{(µ

, µ

, ..., µ

) | µ

+ µ

+ · · · + µ

= n − k,

≥ µ

≥ · · · ≥ µ

> 0, µ

∈ N}| = |S

(n − k)| = p

(n − k).

(n)| = p

(n) = p

k−1

(n − 1) + p

(n − k).

Замечание 1.6.2 . Несмотря на схожесть определений вычисление

величины p

(n) оказывается гораздо более сложной, чем d

(n). Если

для числа разложений мы имеем явную формулу (15), то для числа

разбиений мы получили только рекурентное выражение (18), которое,

тем не менее, позволяет нам вычислить p

(n), пользуясь начальными

условиями: ∀n ∈ N p

(n) = 1, p

(n) = 1; если k > n , то p

(n) = 0.

Пример 1.6.3 . Заполним таблицу первых значений p

(n), пользуясь

начальными значениями и формулой (18).

n\k 1 2 3 4 5 6 7 · · ·

1 1 0 0 0 0 0 0 · · ·

2 1 1 0 0 0 0 0 · · ·

3 1 1 1 0 0 0 0 · · ·

4 1 2 1 1 0 0 0 · · ·

5 1 2 2 1 1 0 0 · · ·

6 1 3 3 2 1 1 0 · · ·

7 1 3 4 3 2 1 1 · · ·

(3) = p

(2) + p

(1) = p

(2) = 1,

(4) = p

(3) + p

(2) = 1 + 1 = 2,

(4) = p

(3) + p

(1) = p

(3) = 1,

(5) = p

(4) + p

(3) = 1 + 1 = 2,

(5) = p

(4) + p

(2) = p

(4) = 2,

(5) = p

(4) + p

(1) = p

(4) = 1,

(6) = p

(5) + p

(4) = 1 + 2 = 3,

(6) = p

(5) + p

(3) = 2 + 1 = 3,

(6) = p

(5) + p

(2) = 2,

(6) = p

(5) + p

(1) = 1,

(7) = p

(6) + p

(5) = 1 + 2 = 3,

(7) = p

(6) + p

(4) = 3 + 1 = 4,

(7) = p

(6) + p

(3) = 3,

(7) = p

(6) + p

(2) = 2,

(7) = p

(6) + p

(1) = 1.

1.7 Принцип включения-исключения

1.7.1 Принцип включения-исключения

Пусть A — заданное множество и S — множество свойств. Каждый

элемент из A может обладать некоторыми свойствами из S. Другими

словами, каждому элементу a из множества A сопоставляется некоторое

подмножество S

множества S и говорят, что элемент a обладает

свойствами из S

Пусть T ⊆ S. Обозначим

(T ) — число элементов из A, которые обладают всеми свойствами

из T и не обладают свойствами из S \ T ;

≥

(T ) — число элементов из A, которые обладают всеми свойствами

из T и возможно какими-то еще. Тогда

≥

(T ) =

T ⊆Y ⊆S

(Y ). (19)

Возможно ли, если мы знаем значение f

≥

(T ) для любых T ⊆ S, найти

функцию f

Утверждение 1.7.1 . Пусть ϕ : 2

→ R — произвольная функция,

сопоставляющая каждому подмножеству конечного множества S,

некоторое вещественное число. Пусть ψ — такая функция из 2

в R,

что

ψ(T ) =

T ⊆Y ⊆S

ϕ(Y ), ∀ T ⊆ S.

Тогда

ϕ(T ) =

T ⊆Y ⊆S

(−1)

|Y \T |

ψ(Y ), ∀ T ⊆ S .

Доказательство. Пусть T ⊆ S. Тогда

T ⊆Y ⊆S

(−1)

|Y \T |

ψ(Y ) =

T ⊆Y ⊆S

(−1)

|Y \T |

Y ⊆Z⊆S

ϕ(Z) =

T ⊆Y ⊆Z⊆S

(−1)

|Y \T |

ϕ(Z) =

T ⊆Z⊆S

ϕ(Z)

T ⊆Y ⊆Z

(−1)

|Y \T |

T ⊆Z⊆S

ϕ(Z)

|Z\T |

i=0

T ⊆Y ⊆Z,

|Y |=|T |+i

(−1)

|Y \T |

T ⊆Z⊆S

ϕ(Z)

|Z\T |

i=0

(−1)

|Z \ T |

T ⊆Z⊆S

ϕ(Z)δ

(|Z \ T |) = ϕ(T ).

Здесь δ

(n) — дельта-функция, которую мы обсуждали в замечании 1.5.1

параграфа 1.5.5.

Следствие 1.7.2 . Поскольку, f

≥

(T ) =

T ⊆Y ⊆S

(Y ), то для любого

T ⊆ S

(T ) =

T ⊆Y ⊆S

(−1)

|Y \T |

≥

(Y ). (20)

В частности,

(∅) =

∅⊆Y ⊆S

(−1)

|Y |

≥

(Y ). (21)

Этот результат помогает решить многие задачи.

1.7.2 Задача о беспорядках

Интуитивная постановка задачи о беспорядках:

Задача 1.7.1 . Пусть, в рамках чемпионата в n городах должно

пройти ровно по одному матчу. Матчи судят n судей, каждый из

которых из одного из городов, все из разных. Сколькими способами

можно распределить судей по матчам, чтобы ни один судья не судил в

своем городе?

Можно привести другую формулировку задачи, математическая идея

которой будет той же.

Задача 1.7.2 . Пусть n человек пришли в театр и сдали шляпы

в гардероб. Когда спектакль закончился и зрители получили шляпы

назад, оказалось, что каждый из n получил чужую шляпу. Сколько

существует вариантов такого события?

Формально задача ставится следующим образом.

Определение 1.7.1 . Беспорядком на множестве {1, ..., n}

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

π(i) 6= i, i = 1, n.

Задача 1.7.3 . Найти число беспорядков на множестве {1, ..., n}:

D(n) = |{π | π ∈ σ

, π(i) 6= i, i = 1, n}|.

Решим эту задачу с помощью принципа включения-исключения.

Будем говорить, что π ∈ σ

обладает свойством i, если π(i) = i.

Тогда S = {1, ..., n} — множество всех свойств, которыми может обладать

перестановка. Пусть T ⊆ S. Пусть

(T ) — число перестановок, каждая из которых обладает всеми

свойствами из T и не обладает свойствами из S \ T :

(T ) = |{π | π ∈ σ

, π(i) = i, i ∈ T ; π( j) 6= j, j ∈ S \ T }|.

≥

(T ) — число перестановок, каждая из которых обладает всеми

свойствами из T и возможно какими-то еще:

≥

(T ) = |{π | π ∈ σ

, π(i) = i, i ∈ T }|.

Следовательно верна формула (19): f

≥

(T ) =

T ⊆Y ⊆S

(Y ). Нетрудно

видеть, что f

≥

(T ) = |S \ T |! — число перестановок на множестве S \ T .

Очевидно, D(n) = f

(∅). Следующее утверждение решает задачу.

Утверждение 1.7.3 . D(n) = n!

i=0

(−1)

Доказательство. Так как f

≥

(T ) = |S \ T |!, то по формуле (21)

D(n) = f

(∅) =

Y ⊆S

(−1)

|Y |

≥

(Y ) =

Y ⊆S

(−1)

|Y |

|S \ Y |! =

i=0

Y ⊆S,

|Y |=i

(−1)

(n − i)! =

i=0

(−1)

(n − i)!

i=0

(−1)

(n − i)! n!

i! (n − i)!

= n!

i=0

(−1)

1.7.3 Мощность объединения множеств

Приведем еще одну задачу, которая решается с помощью принципа

включения-исключения, — задачу нахождения мощности объединения

пересекающихся множеств.

Задача 1.7.4 . Пусть A

, A

, ..., A

— конечные множества. Пусть

A = A

∪ A

∪ ... ∪ A

. Требуется найти мощность A, если известны

|, i = 1, k, и |

i∈I

|, I ⊆ {1, 2, ..., k}.

Пусть S = {1, 2, ..., k} и T ⊆ S. Будем говорить, что x ∈ A обладает

свойством i, если x ∈ A

. Обозначим

(T ) — число элементов из A, обладающих всеми свойствами из T и

не обладающих другими свойствами из S;

≥

(T ) — число элементов из A, обладающих всеми свойствами из T .

Очевидно, f

≥

(T ) = |

i∈T

|, если T не пусто и f

≥

(∅) = |A|

Тогда верна формула (19) и, следовательно, можно использовать

формулу (21).

Утверждение 1.7.4 .

∪ A

∪ ... ∪ A

| =

i=1

| −

1≤i

≤k

∩ A

1≤i

≤k

∩ A

| − · · · + (−1)

k−1

∩ A

∩ ... ∩ A

|. (22)

Доказательство. Поскольку каждый элемент из A обладает хотя бы

одним свойством из S, то f

(∅) = 0. С другой стороны из формулы (21)

получаем

0 =f

(∅) =

Y ⊆S

(−1)

|Y |

≥

(Y ) =

Y ⊆S

(−1)

|Y |

i∈Y

| =

=|A| −

i=1

| +

1≤i

≤k

∩ A

|−

−

1≤i

≤k

∩ A

| + · · · + (−1)

∩ A

∩ ... ∩ A

Перенесем все слагаемые кроме первого за знак равенства и получим

искомое утверждение.

Часто, именно формулу (22) называют принципом включения-

исключения. Тем не менее, как мы видели, с помощью принципа

включения-исключения решаются и другие задачи.

1.7.4 Число целочисленных решений системы неравенств

В подразделе 1.6.1 мы показали, что число решений уравнения x

+ x

· · ·+x

= n в неотрицательных целых числах находится по формуле (16):

(n, k) =

n + k − 1

k − 1

а число решений неравенства x

+ x

+ · · · + x

≤ n в неотрицательных

целых числах — по формуле (17):

≤

(n, k) =

n + k

Здесь мы расширим множество систем, для которых можно будет найти

число решений.

Для начала положим, что на значения переменных наложены

ограничения снизу. Пусть a

∈ N

, i = 1, k, и задана система

+ x

+ · · · + x

= n,

≤ x

, i = 1, k.

Чтобы найти число решений этой системы, достаточно сделать замену

= x

− a

. Тогда y

≥ 0 и

+ a

) + (y

+ a

) + · · · + (y

+ a

) = n,

+ y

+ · · · + y

= n − a

− a

− · · · − a

Согласно формуле (16) число целочисленных решений данной системы

n + k − 1 −

i=1

k − 1

. (23)

Аналогично, число решений системы

+ x

+ · · · + x

≤ n,

≤ x

, i = 1, k,

равно

n + k −

i=1

. (24)

Рассмотрим систему с ограничениями на переменные и сверху, и снизу.

Пусть a

, b

∈ N

, a

≤ b

, i = 1, k. Требуется найти число целочисленных

решений системы

+ x

+ · · · + x

= n, (25)

≤ x

≤ b

, i = 1, k. (26)

Пусть A — множество решений системы

+ x

+ · · · + x

= n, (*)

≤ x

, i = 1, k :

A = {(α

, α

, ..., α

) | α

+ α

+ · · · α

= n, a

≤ α

, i = 1, k}.

Согласно (23)

|A| =

n + k − 1 −

i=1

k − 1

Обозначим A

, s = 1, k, — множество решений системы (*), для

которых не выполняется ограничение x

≤ b

= {(α

, α

, ..., α

) | α

+ α

+ · · · α

= n,

≤ α

, i = 1, k, b

+ 1 ≤ x

Таким образом, все решения системы (*), которые не удовлетворяют

хотябы одной верхней границе из (26), лежат в множестве A

∪A

∪...∪A

Следовательно, число решений системы (25)-(26) равно

|A \ (A

∪ A

∪ ... ∪ A

)| = |A| − |A

∪ A

∪ ... ∪ A