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
b_{n}···b_{2}b_{1}, where
b* _{i}* = 1 if

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:

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.

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:

- Combinations in co-lexicographic order. (Pascal program ) (C program )
- Combinations in lexicographic order. (Pascal program ) (C program )
- Combinations by transpositions. (Pascal program ) (C program )
**(Offsite)**A C implementation of Chase's twiddle algorithm.**(Offsite)**Doug Moore's page on Enumerating Combinations has a link to his clever bit-twiddling C implementation of a lexicographic combination generator.

(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.

[an error occurred while processing this directive]

©Frank Ruskey, 1995-2003.