Finding The k-combination For A Given Number
The given formula allows finding the place in the lexicographic ordering of a given k-combination immediately. The reverse process of finding the k-combination at a given place N requires somewhat more work, but is straightforward nonetheless. By the definition of the lexicographic ordering, two k-combinations that differ in their largest element ck will be ordered according to the comparison of those largest elements, from which it follows that all combinations with a fixed value of their largest element are contiguous in the list. Moreover the smallest combination with ck as largest element is, and it has ci = i − 1 for all i < k (for this combination all terms in the expression except are zero). Therefore ck is the largest number such that . If k > 1 the remaining elements of the k-combination form the k − 1-combination corresponding to the number in the combinatorial number system of degree k − 1, and can therefore be found by continuing in the same way for and k − 1 instead of N and k.
Read more about this topic: Combinatorial Number System
Famous quotes containing the words finding the, finding and/or number:
“As a father I had some trouble finding the words to separate the person from the deed. Usually, when one of my sons broke the rules or a window, I was too angry to speak calmly and objectively. My own solution was to express my feelings, but in an exaggerated, humorous way: “You do that again and you will be grounded so long they will call you Rip Van Winkle II,” or “If I hear that word again, I’m going to braid your tongue.””
—David Elkind (20th century)
“We are paid for our suspicions by finding what we suspected.”
—Henry David Thoreau (1817–1862)
“It seems to me that there must be an ecological limit to the number of paper pushers the earth can sustain, and that human civilization will collapse when the number of, say, tax lawyers exceeds the world’s total population of farmers, weavers, fisherpersons, and pediatric nurses.”
—Barbara Ehrenreich (b. 1941)