Производящая функция — это функция, которая позволяет определить явный вид общего члена рассматриваемой числовой последовательности. Так, пусть имеется последовательность {an}, для главного члена a которой нужно найти общую формулу. Тогда введем функцию A(x) = ∑nanxn. Если, используя свойства рассматриваемой последовательности, удастся решить составленные для A(x) уравнения, то можно будет получить искомые элементы последовательности.
Один из примеров применения производящих функций относится к числам Фибоначчи. Они являются решением рекуррентного уравнения Fn+1 = Fn + Fn−1, где F0 = F1 = 1.
Принцип включения и исключения
Для общего представления приведем иллюстрацию для трех множеств A, B и C:
А про теоремы существования все не совсем ясно, можно прочитать тут:
http://dic.academic.ru/dic.nsf/enc_mathematics/870/%D0%92%D0%AB%D0%91%D0%9E%D0%A0%D0%90
