Сумма продуктов, берущая k элементов из набора из n элементов

Question

Дан набор S с n элементами и целым числом k. Мне нужно найти сумму продуктов из всех n пар k. То есть если S = {1,2,3,4} and k = 2, то я ищу P = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 +3*4. Обратите внимание, что пары продуктов составляют набор - k отличных элементов от набора n элементов. Я могу сформулировать простую динамическую программную версию этого:

P(n,k) = a_{n}P(n-1,k-1) + P(n-1,k)

То есть, взять n-1 элементов и выбрать k-1, добавить a_{n} и пропустить a_{n}. Есть ли хорошая теория, чтобы найти решение вышеуказанной проблемы в замкнутом виде? Мне немного не хватает математики, хотя программирование меня волнует. Я смог вывести вышеупомянутое DP, но не смог перейти к закрытой форме, которая, я надеюсь, есть!

Answer 1

Я не знаю, действительно ли это полезно, но мне приходит в голову, что вы описываете элементарные симметричные полиномы .

Кроме того, кажется, что этот документ может быть вам полезен:

Вычисление элементарных симметрических полиномов с субполиномиальным числом умножений

Answer 2

Учитывая n, k, как вы их определили:

количество суммируемых продуктов # (n, k) задается как

(n, k) = C (n+ k-1, k-1), где C (a, b) - комбинаторная функция, т. е.

     a objects selected b at a time. 

Кроме того, # (n, k) = k * # (n-1,k) - (n-1) * # (n, k-1).