Combination

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

of elements from

A subset of cardinality of some given finite set of cardinality . The number of combinations of elements from is written or and is equal to

The generating function for the sequence , , , has the form

Combinations can also be considered as non-ordered samples of size from a general aggregate of elements. In combinatorial analysis, a combination is an equivalence class of arrangements of elements from (cf. Arrangement), where two arrangements of size from a given -element set are called equivalent if they consist of the same elements taken the same number of times. In the case of arrangements without repetitions, every equivalence class is determined by the set of elements of an arbitrary arrangement from this class, and can thus be considered as a combination. In the case of arrangements with repetitions, one arrives at a generalization of the concept of a combination, and then an equivalence class is called a combination with repetitions. The number of combinations with repetitions of from is equal to , and the generating function for these numbers has the form

References

 [1] V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian) [2] J. Riordan, "An introduction to combinatorial analysis" , Wiley (1958)