# How to calculate an index into a binomial coefficient table from the underlying indexes

The following is a simple table that is bound by the binomial coefficient where N is 6 and K is 4. The total number of entries can be calculated as N! / ( K! (N - K)! ). So, 6! / (4! (6 - 4)!) = 15.

1234 1235 1236 1245 1246 1256 1345 1346 1356 1456 2345 2346 2356 2456 3456

What I was trying to figure out some time ago is if someone has published a formula or algorithm to calculate an index to a table entry based upon the underlying value in that table. So, for example, if the number is 1245, then the formula should return the value 3 because it is the 4th entry (1st index in table starts with zero) in the table above. Another example is for 1356, the formula should return 8 since it is the 9th entry in the table.

So, I came up with a fairly efficient algorithm that does this and does not use very much memory. If you are interested, you can read about it in my blog and download the source code:

http://tablizingthebinomialcoeff.wordpress.com/

My question is - am I the first to come up with technique, and has anyone ever found a better formula or algorithm for doing this?

For those wondering why anyone would be interested in doing this, the binomial coefficient provides a way to eliminate duplicate values and is thus more likely to fit a large model into memory. Finding an efficient way to access this table should be useful.

-
Briefly, Yes; read Knuth. More generally, do some web searches and ask on a CSTHeory or programming forum. Gerhard "Ask Me About System Design" Paseman, 2011.08.11 – Gerhard Paseman Aug 11 '11 at 22:37
I guess "Yes, read Knuth" is a little bit like "Yes, read Lang" or "Yes, read Bourbaki", but for computer science? :) – Federico Poloni Nov 4 '11 at 11:20
Whenever I encounter a sequence of integers I don't recognize, the first place I check is oeis.org, Neil Sloane's online Encyclopedia of Integer Sequences. Many of the entries include formulas and algorithms. It's an invaluable reference. – Dimitrije Kostic Nov 18 '11 at 5:21
Thanks for the responses. I tried looking for the algorithm and mathematical concept behind it, but did not find it in any of Knuth's texts in "The Art of Computer Programming". I have also done many web searches and could not find it. I think I am the first to publish on how to efficiently convert a k-indexes bounded by the binomial coefficent to the correct entry in a table, which is also the rank. The link to the wikopedia article below describes how to convert between the rank and the corresponding k-indexes, but does not talk about the technique that I disovered. – Robert Bryan Jan 1 '12 at 8:17