# Is there a nice formula for the following function?

Homework Helper
Gold Member
Dearly Missed

## Main Question or Discussion Point

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!

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

Last edited:

pasmith
Homework Helper
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!

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

Homework Helper
Gold Member
Dearly Missed
In general I doubt you'll do better than
$$S(k,n) = \sum_{\begin{array}{c}U \subset \{1, \dots, n\} \\ |U| = k\end{array}} \left(\prod_{u \in U} u \right)$$
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
Staff Emeritus
Gold Member
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 j2, and a sum over j3 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

Homework Helper
Gold Member
Dearly Missed
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.

Homework Helper
Gold Member
Dearly Missed
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.. 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.

Homework Helper
Gold Member
Dearly Missed
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!!!