Topic: Permutations and combinations with unrestricted number of duplicate elements (with unlimited repetitions)

Main concepts: In the previous topics we discussed combinations and permutations without duplicate elements. We assumed that all elements of n-set were distinct. In real life, often we have to deal with cases when some elements of an n-set are indistinct (equal). The presence of duplicate elements results in a smaller number of different permutations and combinations.

For example, if we make all possible arrangements (permutations) of the letters of the word "hand", we will get 24 different permutations: hand, hadn, hnad, hnda, and so on. If we make permutations in the word "papa", then the number of different permutations is only 6: papa, paap, ppaa, apap, aapp, app.

When we talk about k-permutations and k-combinations with repetitions, we mean the following:

Given set M which is a union of disjoint subsets:
M = M₁ U M₂ U... U M_n , where M_i ∩ M_j =⌀; and M_i = {m_i1, m_i2,..., m_iq}

(1≤ i ≤ n).

Elements m_i1,..., m_iq of any subset M_i are indistinct (equal) in a given problem. We will denote any of them as m_i .

In such a case, 6-permutations:

(m_11, m_21, m_31, m_12, m_32, m₁₃) and

(m_14, m_25, m_33, m_15, m_32, m₁₄ )

of a set M are considered as indistinct (equal, same). They are denoted as (m₁ m₂ m₃ m₁ m₃ m₁).

Note: n is the number of different types of elements, that is the number of different sets, that contain "indistinct" elements.

|M| can be much greater than n, if it is not stated otherwise.

Two k-permutations with repetitions are equal if they have the same elements in the same positions.

Example: let M be a set of low-case letters typed on separate piece of paper each. Then M = {a, a,..., a} U {b, b,..., b} U... U {z, z,..., z}

M₁ M₂ M₂₄

M_i ∩ M_j = ⌀, i ¹ j. Meaning: subsets are disjoint.

Now such 4-permutations are different:

(p,a,p,a), (a, a, p, p), (m, m, b, z), (b, a, l, l), etc.

If each class M_i contains exactly 1 element, then we get to ordinary k-permutations (without repetitions).

In a similar way we define k-combinations of n elements with duplicates (with repetitions). They are unordered k-subsets of the above defined set M = M₁ U M₂ U... U M_n.

All elements of a subset M_i are assumed to be equal.

Two combinations are considered to be equal if they have the same number of elements of the same type.

Combinations with not more than 1 element of each type are called combinations without repetitions. Otherwise we have combinations with repetitions.

Ex.: Let M = {a, a,..., a} U {b, b,..., b} U... U {z, z,..., z}.

Then: {p, a, p, a}, {m, a, p, a} are different 4-combinations.

{a, a, p, p}, {p, p, a, a}, {p, a, a, p} are equal 4-combinations.

Topic: k-permutations with unlimited repetitions.

Let M = M₁ U M₂ U... U M_n and M_i ∩ M_j =⌀.

Note: |M_i| ≥ k.

In this case, each position in a k-permutation in set M can be filled by an element from any M_i, that is in n different ways.

We have such a situation:

2 6 k-permutation contains k empty positions.

n different sets with distinct elements.

Hence

Hence, by the rule of product, the member of different permutations from M is equal: = n*n*...*n = ;

k times

Note: the condition | | ≥ k allows to talk about unrestricted repetitions in permutations.

H/a. Suppose, a computer keyboard has 96 printable symbols. How many different "words" consisting of 7 symbols can be typed using this keyboard.