Combination - Number of Combinations With Repetition

Number of Combinations With Repetition

See also: Multiset coefficient

A k-combination with repetitions, or k-multicombination, or multiset of size k from a set S is given by a sequence of k not necessarily distinct elements of S, where order is not taken into account: two sequences of which one can be obtained from the other by permuting the terms define the same multiset. In other words, the number of ways to sample k elements from a set of n elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}). If S has n elements, the number of such k-multicombinations is also given by a binomial coefficient, namely by

(the case where both n and k are zero is special; the correct value 1 (for the empty 0-multicombination) is given by left hand side, but not by the right hand side ). This follows from a clever representation of such combinations with just two symbols (see Stars and bars (combinatorics)).

Read more about this topic:  Combination

Famous quotes containing the words number of, number, combinations and/or repetition:

    “I happen to feel that the degree of a person’s intelligence is directly reflected by the number of conflicting attitudes she can bring to bear on the same topic.”
    —Lisa Alther (b. 1944)

    “The world is so full of a number of things,
    I’m sure we should all be as happy as kings.”
    —Robert Louis Stevenson (1850–1894)

    “What is the structure of government that will best guard against the precipitate counsels and factious combinations for unjust purposes, without a sacrifice of the fundamental principle of republicanism?”
    —James Madison (1751–1836)

    “The echo is, to some extent, an original sound, and therein is the magic and charm of it. It is not merely a repetition of what was worth repeating in the bell, but partly the voice of the wood; the same trivial words and notes sung by a wood-nymph.”
    —Henry David Thoreau (1817–1862)