I am trying to solve https://www.rosecode.net/problem-550-A-specific-sum-over-all-subsets-of-a-set-askyear-2019
I shall quote the problem here.
Given two natural numbers $N$ and $M$ with $0 < N \le M$, let $I(N,M)$ be the set which contains all natural numbers between $N$ and $M$ (inclusive). For example, $I(3,6)=\{3,4,5,6\}$
We define the product of a set as the product of all elements in that set, written as $P(\{...\})$ where $\{...\}$ is a specific set. For example, $P(I(3,6))=3×4×5×6=360$
Finally, We define a function $C(N,M,K)$ as the sum of product of sets over all $I(N,M)$'s subsets which contain exactly $K$ elements.
In other words, $$C(N,M,K)=\sum_{S⊆I(N,M), \hspace{1 mm} len(S)=K}P(S)$$ You are given $C(10,20,3)=549450$
Basically we need to find the ($N+1-K)^{th}$ coefficient of the polynomial $(x+N)(x+N+1)(x+N+2)...(x+M-1)(x+M)$.
When $N=1$, $C(1,M,K)=\text{Abs}[\text{StirlingS1}[M+1, M-K]]$
Form empirical data $C(2,M,K)=\text{Abs}[\sum_{i=1}^K\text{StirlingS1}[M+1, i]]$
I have not been able to get the general expression. Any help will be appreciated.
I tried another approach. $C(N, M, K)$ can be expressed as a polynomial of degree $K$ on the variable $N$ when $M-N$ is fixed.
For example, if $M-N=10$ and $K=3$, $C(N,N+10,3)=18150+11880N+2475N^2+165N^3$. So $C(10,20,3)=18150+11880*10+2475*10^2+165*10^3=549450$
For the second example, $M-N=100$ and $K=10$. In this case $C(N,N+100,10)=1602646281287434529994530905950 + 330942341452363282536630582000 N + 30638689420308625285731305820 N^2 + 1674759115115824977847300000 N^3 + 59858937328252123105236500 N^4 + 1461809426255232338592000 N^5 + 24702922554022047128640 N^6 + 285248600159079480000 N^7 + 2154062095260698700 N^8 + 9606270632420000 N^9 + 19212541264840 N^{10}$
Assuming this idea is right, our final answer should be a polynomial of degree $50$. But to find the coefficients, we need $50$ data points. So far I have been unable to evaluate those.