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:

    “He is the greatest artist who has embodied, in the sum of his works, the greatest number of the greatest ideas.”
    —John Ruskin (1819–1900)

    “After mature deliberation of counsel, the good Queen to establish a rule and imitable example unto all posterity, for the moderation and required modesty in a lawful marriage, ordained the number of six times a day as a lawful, necessary and competent limit.”
    —Michel de Montaigne (1533–1592)

    “The more elevated a culture, the richer its language. The number of words and their combinations depends directly on a sum of conceptions and ideas; without the latter there can be no understandings, no definitions, and, as a result, no reason to enrich a language.”
    —Anton Pavlovich Chekhov (1860–1904)

    “When sins are dear to us we are too prone to slide into them again. The act of repentance itself is often sweetened with the thought that it clears our account for a repetition of the same sin.”
    —Thomas Jefferson (1743–1826)