Производящие функции. Комбинаторика С помощью производящей функции, вывести формулу для количества k-выборок из множества X={x1,x2...xn} в которой присутствуют все элементы множества.

Предыдущий
вопрос Следующий
вопрос

Для нахождения количества k-выборок из множества X={x1, x2, ..., xn}, в которых присутствуют все элементы множества, воспользуемся производящей функцией.

Обозначим за Fi(x) производящую функцию для множества, содержащего i элементов. Тогда производящая функция для множества X будет равна произведению всех Fi(x), где i от 1 до n, так как для каждого i мы должны выбрать по одному элементу из каждого множества.

То есть производящая функция для множества X будет равна F(x) = F1(x) F2(x) ... * Fn(x).

Теперь мы можем найти формулу для количества k-выборок из множества X, в которых присутствуют все элементы. Для этого возьмем производную от производящей функции F(x) по x в точке 0 и поделим на k!: [x^k]F'(x)/k!.

Это число будет равно количеству k-выборок из множества X, в которых присутствуют все элементы.