[Information Index] [Generation Index] [COS homepage]

Information on Combinations of a Set

A set is a collection of objects, and a subset is a sub-collection of those objects. For example if the collection consists of the three letter A, B, and C, written as {A,B,C}, then the possible subcollections are {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, and {A,B,C}. A k-combination of an n-set is a subset with k elements chosen from an set with n elements. For example, the 2-combinations of the 4-set {A,B,C,D} are {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}.

In the Object Server, the set from which subsets are made is always the set [n] of the first n positive integers (i.e., [n] = {1,2,...,n}). If bitstring output is selected, then each combination S is listed as a bitstring bn···b2b1, where bi = 1 if i is in S and bi = 0 if i is not in S. If subset output is selected, then each subset S (say of size k) is output as an ordered list {s1,s2,...,sk} of its elements.

The number of k-combinations an n-set is the binomial coefficient C(n,k) = n!/[k!(n-k)!]. The arrangement of binomial coefficients shown below is known as Pascal's triangle, but in fact, this same arrangement can be found in ancient Chinese manuscripts that predate Pascal. Each number is the sum of the two numbers above it.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

This triangle mirrors the classic recurrence relation for binomial coefficients:

C(n,k) = C(n-1,k) + C(n-1,k-1)

In the table the rows correspond to n (starting from row 0), and the number of positions from the left (counting from 0) corresponds to the value of k. For example, C(4,2) = 6.

Particular columns of this table give rise to well-known sequences of numbers. The triangular numbers are those in column k=2. For n=1,2,...,10 they are 1, 3, 6, 10, 15, 21, 28, 36, 45, 55 with explicit expression C(n+1,2) = n(n+1)/2. This is sequence A000217(M2535) in Neil J. Sloane's database of integer sequences. The tetrahedral numbers are those in column k=3. For n=1,2,...,8 they are 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, with explicit expression C(n+2,3) = n(n+1)(n+2)/6. They are special type of pyramidal number, where the base of the pyramid is triangular. This is sequence A000292(M3382) in Neil J. Sloane's database of integer sequences.

Gray Codes for Combinations

The COS options "Combinations by transpositions" and "Combinations by adjacent transpositions" options are examples of combinatorial Gray codes. In both cases the transpositions refer to the bitstring representation. A 0 and a 1 are transposed to get the next combination.

In the (non-adjacent) transposition case, successive subsets differ by exactly one element; one element leaves the combination and one elements enters the combination. For this reason algorithms generating such Gray codes are said to be revolving-door algorithms. There are several such Gray codes.

If combinations are generated by adjacent transpositions, then if element k leaves the combination, then element k ± 1 enters the combination. These lists are possible if and only if n is even and k is odd. The adjacent transposition Gray code was defined in the paper: P. Eades, M. Hickey, and R.C. Read, Some Hamilton Paths and a Minimal Change Algorithm, Journal of ACM, 31 (1984) 19-29. Our implementation is from the paper: T. Hough and F. Ruskey, An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm, J. Combinatorial Math. and Combinatorial Computing, 4 (1988) 79-86.


Programs available: [CAT]


[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:13 PDT.
There have been 20314 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.