1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is there a nice formula for the following function?

  1. Sep 18, 2013 #1

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    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: Sep 18, 2013
  2. jcsd
  3. Sep 18, 2013 #2

    pasmith

    User Avatar
    Homework Helper

    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]
     
  4. Sep 18, 2013 #3

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    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..
     
  5. Sep 18, 2013 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  6. Sep 18, 2013 #5

    arildno

    User Avatar
    Science Advisor
    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.
     
  7. Sep 18, 2013 #6

    arildno

    User Avatar
    Science Advisor
    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..:frown:
     
  8. Sep 18, 2013 #7
    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.
     
  9. Sep 18, 2013 #8

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Hooray!
    That seems to be the name of my beast!
    Thanks a bundle!!!
     
  10. Sep 18, 2013 #9

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Is there a nice formula for the following function?
Loading...