Is there a nice formula for the following function?

  • Thread starter arildno
  • Start date
  • #1
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
131

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!

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
 
Last edited:

Answers and Replies

  • #2
pasmith
Homework Helper
1,740
412
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
[tex]
S(k,n) = \sum_{\begin{array}{c}U \subset \{1, \dots, n\} \\ |U| = k\end{array}} \left(\prod_{u \in U} u \right)
[/tex]
 
  • #3
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
131
In general I doubt you'll do better than
[tex]
S(k,n) = \sum_{\begin{array}{c}U \subset \{1, \dots, n\} \\ |U| = k\end{array}} \left(\prod_{u \in U} u \right)
[/tex]
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..
 
  • #4
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
You can calculate S(2,n) (partial solution given here),

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

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

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
 
  • #5
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
131
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.
 
  • #6
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
131
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..:frown:
 
  • #7
160
21
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.
 
  • #8
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
131
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!!!
 
  • #9
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
131
As a matter of fact, my conundrum arose from seeking to calculate the coefficients of the polynomial I now have learnt the name of, "the falling factorial", x*(x-1)*(x-2)*....(x-n)
 

Related Threads on Is there a nice formula for the following function?

  • Last Post
Replies
4
Views
2K
Replies
6
Views
498
  • Last Post
Replies
1
Views
1K
Replies
12
Views
8K
Replies
4
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
16
Views
2K
Top