Математическая энциклопедия - включения и исключения принцип

метод подсчета числа объектов, не обладающих ни одним из данных свойств по следующей формуле:

где означает отсутствие свойства , число всех объектов, число объектов, обладающих свойством число объектов, обладающих одновременно свойствами и , и т. д. (см., напр., [3]). Из В. и и. п. вытекает формула для подсчета числа объектов, обладающих точно тсвойствами из

где причем здесь суммирование производится по всем k-наборам таким, что

Иногда метод подсчета по формуле (2) также наз. В. и и. п.

Этот принцип , находит применение при решении комбинаторных и теоретико-числовых задач (см., напр., [1]). Так, если дано натуральное число а и Натуральные числа такие, что при , то число целых чисел kтаких, что и не делящихся на равно по (1):

При помощи В. и и. п. решается также задача о беспорядках (см. [2], [3]).

Лит.:[1] Холл М., Комбинаторика, пер. с англ., М., 1970; 12] Райзер Г. Дж., Комбинаторная математика, пер. с англ., М., 1966; [3] Риордан Д ж., Введение в комбинаторный анализ, пер., с англ., М., 1963. С. .4. Рукава.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985