Place of A Combination in The Ordering
The number associated in the combinatorial number system of degree k to a k-combination C is the number of k-combinations strictly less than C in the given ordering. This number can be computed from C = { ck, ..., c2, c1 } with ck > ... > c2 > c1 as follows. From the definition of the ordering it follows that for each k-combination S strictly less than C, there is a unique index i such that ci is absent from S, while ck, ..., ci+1 are present in S, and no other value larger than ci is. One can therefore group those k-combinations S according to the possible values 1, 2, ..., k of i, and count each group separately. For a given value of i one must include ck, ..., ci+1 in S, and the remaining i elements of S must be chosen from the ci non-negative integers strictly less than ci; moreover any such choice will result in a k-combinations S strictly less than C. The number of possible choices is, which is therefore the number of combinations in group i; the total number of k-combinations strictly less than C then is
and this is the index (starting from 0) of C in the ordered list of k-combinations. Obviously there is for every N ∈ N exactly one k-combination at index N in the list (supposing k ≥ 1, since the list is then infinite), so the above argument proves that every N can be written in exactly one way as a sum of k binomial coefficients of the given form.
Read more about this topic: Combinatorial Number System
Famous quotes containing the words place of, place, combination and/or ordering:
“Human life consists in mutual service. No grief, pain, misfortune, or “broken heart,” is excuse for cutting off one’s life while any power of service remains. But when all usefulness is over, when one is assured of an unavoidable and imminent death, it is the simplest of human rights to choose a quick and easy death in place of a slow and horrible one.”
—Charlotte Perkins Gilman (1860–1935)
“The phenomena of the year take place every day in a pond on a small scale. Every morning, generally speaking, the shallow water is being warmed more rapidly than the deep, though it may not be made so warm after all, and every evening it is being cooled more rapidly until the morning. The day is an epitome of the year. The night is the winter, the morning and evening are the spring and fall, and the noon is the summer. The cracking and booming of the ice indicate a change of temperature.”
—Henry David Thoreau (1817–1862)
“Just as we need to encourage women to test life’s many options, we need to acknowledge real limits of energy and resources. It would be pointless and cruel to prescribe role combination for every woman at each moment of her life. Life has its seasons. There are moments when a woman ought to invest emotionally in many different roles, and other moments when she may need to conserve her psychological energies.”
—Faye J. Crosby (20th century)
“Make gracious attempts at sanctifying Jenny,
Supply cosmetics for the ordering of her frame,
Think of her as Leda, as a goddess,
Emptying a smile on Redkey, Indiana.”
—Allen Tate (1899–1979)