Register to reply

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

by JTHM
Tags: algorithms, combinatorics
Share this thread:
JTHM
#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
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Iranian is first woman to win 'Nobel Prize of maths' (Update)
Bill Simpson
#2
Jan10-13, 08:41 PM
P: 1,037
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