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...