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


by JTHM
Tags: algorithms, combinatorics
JTHM
JTHM is offline
#1
Jan7-13, 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 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/Combina..._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.
Phys.Org News Partner Mathematics news on Phys.org
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Bill Simpson
Bill Simpson is offline
#2
Jan10-13, 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 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.


Register to reply

Related Discussions
Conversion to closed-form 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
Closed-Form Expression General Math 2
Closed-form expression of an infinite sum Calculus & Beyond Homework 3