Is there a nice formula for the following function?

[arildno]

Hi there!
I am seeking a nice formula for the following function S(k,n), k and n natural numbers, k<=n, where S(k,n) is the sum of all possible products (permutations not allowed) of k distinct integers, where the integer set runs from 1 to n.
Thus, for example, we have the trivial cases of S(1,n)=n(n+1)/2 and S(n,n)=n!

Thanks in advance

EDIT:
I'm not really interested in an implicit recursive method (that's fairly trivial to set up), but an explicit expression of S

 

[pasmith]

Hi there!
I am seeking a nice formula for the following function S(k,n), k and n natural numbers, k<=n, where S(k,n) is the sum of all possible products (permutations not allowed) of k distinct integers, where the integer set runs from 1 to n.
Thus, for example, we have the trivial cases of S(1,n)=n(n+1)/2 and S(n,n)=n!

Thanks in advance

In general I doubt you'll do better than
<br /> S(k,n) = \sum_{\begin{array}{c}U \subset \{1, \dots, n\} \\ |U| = k\end{array}} \left(\prod_{u \in U} u \right)<br />

 

[arildno]

In general I doubt you'll do better than
<br /> S(k,n) = \sum_{\begin{array}{c}U \subset \{1, \dots, n\} \\ |U| = k\end{array}} \left(\prod_{u \in U} u \right)<br />

Thanks!
I've thought of that as well, and it won't be any touble for me setting up a recursive scheme to calculate whatever value of S that I want.

I was hoping, though, that some mathematician had figured out a surprisingly simple formula..

 

[Office_Shredder]

You can calculate S(2,n) (partial solution given here),

S(2,n) = \sum_{j=1}^{n-1} j \sum_{r=j+1}^{n} r
\sum_{r=j+1}^{n} r = (n+j)(n-j+1)/2

So
S(2,n) = \sum_{j=1}^{n-1} j(n+j)(n-j+1)/2

You can distribute it and get a sum over j, a sum over j², and a sum over j³ all of which have known formulas. Trying to repeat this exact process (sum over j, sum over r > j, sum over s > r for S(3,n) for example) is doable but tedious. It might be able to be generalized to S(k,n) directly though with extreme cleverness

 

[arildno]

Thank you, Office Shredder!
I did think of such schemes, but didn't want to go through the calculations (I do not trust myself in gleaning a general pattern here).
It would be easier, say computerwise, to set up a plodding algorithm, but I thought that a function S(k,n) OUGHT to occur in lots of combinatorics problems, for example, so that some mathematician had done some serious thinking upon S.

 

[arildno]

Another explicit value will, obviously, be S(n-1,n), which must equal (n!)*H(n), where H(n) is the harmonic sum of the n first numbers (which DOES have a rather nice expression).
But, it is all those in-betweens I wonder about..

 

[eigenperson]

If I understand you correctly, your $S(k,n)$ is the (unsigned) Stirling number of the first kind $\left[n+1 \atop n + 1 - k\right]$. You should be able to find a lot of information about these numbers once you know that they are the Stirling numbers of the first kind.

 

[arildno]

If I understand you correctly, your $S(k,n)$ is the (unsigned) Stirling number of the first kind $\left[n+1 \atop n + 1 - k\right]$. You should be able to find a lot of information about these numbers once you know that they are the Stirling numbers of the first kind.

Hooray!
That seems to be the name of my beast!
Thanks a bundle!

 

[arildno]

As a matter of fact, my conundrum arose from seeking to calculate the coefficients of the polynomial I now have learned the name of, "the falling factorial", x*(x-1)*(x-2)*...(x-n)