Closed form expression for sum of first m terms of a combinatorial numberby JTHM Tags: algorithms, combinatorics 

#1
Jan713, 08:14 PM

P: 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 closedform expression for the sum of the first through mth terms of a combinatorial number. For those of you unfamiliar with combinatorial numbers, here's some useful reading: http://en.wikipedia.org/wiki/Combina..._number_system Basically, the idea is this: for any nonnegative integers k, and b, we can express the value of b as a sum of k terms of the form (r_{1} choose k)+(r_{2} choose k1)+(r_{3} choose k2)...(r_{k} choose 1). For every t and s where t and s are nonnegative integers such that t<s, it will be the case that r_{t}>r_{s} (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 closedform expression for the sum of those terms? Admittedly, I am not certain that a closedform expression even exists. If you can think of a reason why there might not be a closedform expression for the above, please share it. In the eventuality that there is no closedform expression, if you can think of a fast algorithm to find such a sumsomething faster than just adding the terms individuallythat would be helpful, too. 



#2
Jan1013, 08:41 PM

P: 972

If I correctly understand your problem and the wiki page which says in the second or third paragraph
"Indeed a greedy algorithm finds the kcombination corresponding to N: take ck maximal with (ck,k)<=n, then take ck − 1 maximal with (ck1,k1), 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. 


Register to reply 
Related Discussions  
Conversion to closedform expression with DE's  Calculus  3  
Write a closed form expression for the approximation y(nC)...  Calculus & Beyond Homework  7  
Closed form expression for this?  Precalculus Mathematics Homework  1  
ClosedForm Expression  General Math  2  
Closedform expression of an infinite sum  Calculus & Beyond Homework  3 