Пример 2. Число неубывающих сюръекций n  1 равно .

Число неубывающих сюръекций 3 2 равно.

Сочетания с повторениями. Сочетанием с повторением из множества {e₁ , e₂ ,  , e_n } называется линейная комбинация x₁e₁ + x₂e₂ +  +x_n e_n , состоящая из x₁ элементов e₁ , из x₂ элементов e₂ , , из x_n элементов e_n , где x_i ≥ 0 – неотрицательные целые числа. Если x₁ +  +x_n = k , то оно называется сочетанием с повторениями из n по k.

Пусть, например, имеется 3 цвета: красный, зеленый, синий. Интенсивности этих цветов равны. Сколько смесей суммарной интенсивности 10 можно получить, смешивая x₁ красных,x₂ зеленых иx₃ синих цвета?

Лемма 1. Пусть - число сочетаний с повторениями изn по k. Тогда равно числу неубывающих функций{1,2,  , n-1}  {0,1,2,  , n}

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

Рис. 2.2. Решение уравнения x₁ +  +x_n = k

Каждому решению x₁ +  +x_n = kсоответствует неубывающая последовательностьy₁ ≤y₂ ≤ _{  } ≤y_n-1 , гдеy₁=x₁, y₂ = y₁+x₂,  , y_n-1 = y_n-2 + x_n-1 .

Теорема 7. .

Доказательство.Рассмотрим график неубывающей функции

Рис. 2.3. График неубывающей функции

График задается последовательностью из 0 и 1

0 0 1 1 0 0 … 0 1 0 0 … 1 1 … 1

состоящей из n-1+kразрядов, имеющихkединиц.

Следствие 1. Равно числу неубывающих функций

{1,2,  , k}  {1,2,  , n}.

Доказательство. Первый способ: транспонировать графики. Если график, показанный на рис.2.3, отразить относительно прямойy=x, то получим график функции {1,2, , k}{1,2, , n}. Это доказывает утверждение следствия.

Второй способ: число неубывающих функций {1,2,  , k}{1,2, , n} равно==.

Получаем следующую таблицу 2.2 , содержащую числа конфигураций

Таблица 2.2

Число конфигураций

	функций mn	неубывающих функций mn
Всех	nm
Инъективных
Сюръективных	?
Биективных	n!, еслиm=n, иначе 0	1, еслиm=n, иначе 0

Здесь m= {0,1,,m-1}. Например, число неубывающих сюръективных отображений {0,1,, m-1}{0,1,, n-1} равно.

3. Формула включения и исключения Перечисление элементов объединения подмножеств. Обобщим формулу

|A₁ A₂|=|A₁ |+|A₂||A₁ A₂|. Эта формула имеет многочисленные приложения. Мы применим ее для решения задачи о встречах, задачи о счастливых билетах и для нахождения значений функции Эйлера (n).

Теорема 1. (Формула включения-исключения)

Доказательство.По индукции. Приn=1, 2 утверждение очевидно. Заметим, что имеет место соотношение. Предположим, что дляn множеств утверждение верно. Докажем ее дляn+1. Имеем по формуле включения-исключения дляnмножествA₁A_n+1,A₂A_n+1, …,A_nA_n+1 :

Поскольку формула верна при n=2, то справедливо равенство

.

Отсюда мы видим, что содержит слагаемое, равное суммеи соответствующее первому слагаемому в формуле включения-исключения дляn+1 множеств. Объединимk-е слагаемое определенное в формуле дляи (k-1)-е слагаемое в формуле включения-исключения для. В силу=, будем иметь

=

=.

В результате мы получили k-е слагаемое в формуле включения-исключения для множествA₁, …,A_n+1. Следовательно, эта формула верна дляn+1множеств. Что и требовалось доказать.

Задача о встречах. В дождливую погоду n человек пришли в театр. Они сдают зонтики в гардероб. После окончания спектакля получают зонтики обратно, в случайном порядке. Какова вероятность того, что каждый из них получит чужой зонтик?

Задача сводится к нахождению числа перестановок элементов множества {1, 2, ∙ ∙ ∙ , n}, не имеющих неподвижных точек.

Пусть S_iсостоит из перестановок, оставляющих неподвижной точкуi. Вычислим

| S₁ S₂  ∙ ∙ ∙ S_n|.

Искомая вероятность будет равна .

Получаем . Отсюда число перестановок, не имеющих неподвижных точек, равно. Искомая вероятность равна. Числоf(n) будет ближайшим к дроби целым числом. Приnвероятность стремится к .

Задача о счастливых билетах. Требуется найти число решений уравнения x₁+x₂+x₃ = y₁+y₂+y₃ , где 0  x_i , y_i  9.

Решение. Подстановкаx₄=9y₁ , x₅=9y₂ , x₆=9y₃ устанавливает биекцию между решениями этого уравнения и уравненияx₁+x₂+x₃ + x₄+x₅+x₆ = 27, где 0 x_i 9.

Найдем число разложений x₁+x₂+x₃ + x₄+x₅+x₆ = 27, где 0 x_i 9.

Пусть U₁– число разложений сx₁10,

U₂– число разложений сx₂10,

∙∙∙

U₆– число разложений сx₆10.

Тогда | U_i U_jU_k | =0 при|{i,j,k}|=3.

Вычислим число разложений, не удовлетворяющих неравенствам 0x_i9. Оно равно

| U₁ U₂U₃ U₄ U₅ U₆ | = 6|U₁|─15|U₁U₂|,

где | U₁|─ число решений уравнения(x₁─10)+x₂+x₃ + x₄+x₅+x₆ = 27─10,

а |U₁U₂|─ число решений уравнения

(x₁─10)+(x₂─10)+x₃ + x₄+x₅+x₆ = 27─10-10.

Получаем | U₁ U₂U₃ U₄ U₅ U₆ | = .

Из числа всех разложений вычитаем разложения с x_i≥10. Получаем окончательный ответ

.

Функция Эйлера. Пусть n – положительное натуральное число, (n) – количество натуральных чисел 0< d  n, взаимно простых c n (т.е. не имеющих одинаковых делителей, кроме 1). Например, при n=10, d{1, 3, 7, 9} и (10) = 4 . Функция (n) называется функцией Эйлера.