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!

Closed form expression for sum of first m terms of a combinatorial number

  1. Jan 7, 2013 #1
    Dear Physics Forums denizens,

    I have a tricky problem that I hope one of you can help me with. (It's for a personal project, nothing to do with school.) I'm looking for a closed-form expression for the sum of the first through m-th terms of a combinatorial number. For those of you unfamiliar with combinatorial numbers, here's some useful reading: http://en.wikipedia.org/wiki/Combinatorial_number_system

    Basically, the idea is this: for any non-negative integers k, and b, we can express the value of b as a sum of k terms of the form (r1 choose k)+(r2 choose k-1)+(r3 choose k-2)...(rk choose 1). For every t and s where t and s are non-negative integers such that t<s, it will be the case that rt>rs (this is just true by the definition of a combinatorial number).

    For example, for k=5, we can express the number 36 as (7 choose 5)+(6 choose 4)+(2 choose 3)+(1 choose 2)+(0 choose 1).

    Now, the sum of all five of these terms will be 36. But suppose I just want, say, the sum of the first two terms, four terms, or any arbitrary number of terms, and I don't want to exhaustively find every term and add all of them up. The question, then is this: given k, b, and m, where k is the total number of terms in the combinatorial number, b is the value of the combinatorial number, and m is the number of terms (starting with the first term) that we want to sum, what is the closed-form expression for the sum of those terms?

    Admittedly, I am not certain that a closed-form expression even exists. If you can think of a reason why there might not be a closed-form expression for the above, please share it. In the eventuality that there is no closed-form expression, if you can think of a fast algorithm to find such a sum--something faster than just adding the terms individually--that would be helpful, too.
    Last edited: Jan 7, 2013
  2. jcsd
  3. Jan 10, 2013 #2
    If I correctly understand your problem and the wiki page which says in the second or third paragraph

    "Indeed a greedy algorithm finds the k-combination corresponding to N: take ck maximal with (ck,k)<=n, then take ck − 1 maximal with (ck-1,k-1), and so forth."

    (with my apologies for mashing the notation into ascii)

    When a mathematician is reduced to writing the word "algorithm" I always assume that means there is no known explicit equation giving the result.

    If you can find a closed form solution giving the first term or, even better, giving the first n of k terms then there might be a chance that this could be used to find the closed form for the sum of those terms.

    But personally I wouldn't hold out much hope.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook