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:
“Do not put yourself forward in the king’s presence or stand in the place of the great; for it is better to be told, “Come up here,” than to be put lower in the presence of a noble.”
—Bible: Hebrew, Proverbs 25:6-7.
“We Americans have always considered Hollywood, at best, a sinkhole of depraved venality. And, of course, it is. It is not a Protective Monastery of Aesthetic Truth. It is a place where everything is incredibly expensive.”
—David Mamet (b. 1947)
“Only amateurs say that they write for their own amusement. Writing is not an amusing occupation. It is a combination of ditch-digging, mountain-climbing, treadmill and childbirth. Writing may be interesting, absorbing, exhilirating, racking, relieving. But amusing? Never!”
—Edna Ferber (1887–1968)
“Our goal as a parent is to give life to our children’s learning—to instruct, to teach, to help them develop self-discipline—an ordering of the self from the inside, not imposition from the outside. Any technique that does not give life to a child’s learning and leave a child’s dignity intact cannot be called discipline—it is punishment, no matter what language it is clothed in.”
—Barbara Coloroso (20th century)