Topic: Combinations with unrestricted repetitions

k-combinations are made of elements of the set M.

M = U U... U ; ∩ = ⌀; | | ≥ k.

A combination may contain any number of elements of the same type: from 0 to k (including).

Let denote the number of such combinations. Let {a₁, a₂,...,a_k} be some k-combination with repetitions from the set M.

For convenience, each element from M₁ is denoted by 1, each element from M₂ by 2, and so on.

The sequence of elements in a combination is irrelevant. We can put them in any convenient order. Let us order elements of { a₁, a₂,..., a_k} in ascending order so that: 1≤ a₁ ≤ a₂ ≤... ≤ a_k ≤ n.

Let us link a k-combination {a₁, a₂,...,a_k} with repetitions from M and a k-combination {a₁, a₂+1, a₃+2, a₃+2, a₄+3,..., a_k+k-1} without repetitions from the set B.

When we do the same thing for all k-combinations from the set M, we will obtain a one-to-one correspondence between k-combinations with unrestricted repetitions from M and k-combinations without repetitions from B. The number of these combinations is equal. So = ;

The idea of this proof belongs to L.Euler.

H/a. In a sports shop there are 4 types of skis: Fisher, Suomi, Tissa, Estonia. In how many ways it is possible to buy 8 pairs of skies? Note: there are at least 100 pairs available in each type of skis.

Subtopic: n-permutations of n-set with a given specification.

A set M is called a set with a given specification (of element types) if:

M=M₁ U M₂ U... U M_i U... U M_k;

M_i ∩ M_j = ⌀;

|M| = n; |M_i| = n_i, (i=1,2,..., k), n₁ + n₂ +... + n_k = n;

Elements of M_i are indistinct (m_j). Elements of different subsets M_i and M_j are distinct (m_i ≠ m_j).

If all elements of n-set M were distinct (no types) then the total number of n-permutations would be equal to n!

But some elements in M are indistinct, the number of different n-permutations becomes smaller.

Ex: Consider such n-permutation:

m₁ m₁... m₁ m₂ m₂... m₂..... m_k m_k... m_k (1)

n₁ n₂ n_k

n₁! indistinct permutations

The elements of the first type (m₁) can be permuted (rearranged in a different order) in n₁! sequences. All of these permutations are indistinct. In the same manner nothing is changed by n₂! permutations of the elements of m₂ type, and so on n_k! permutations of m_k elements also do not change the initial sequence.

For example, in the permutation "ppaa", the exchange of the 1st and 2nd letters, exchange of the 3rd and 4th letters change nothing in the sequence "ppaa".

Permutations of elements of the 1st type, of the 2nd type and so on, can be made independently in each type. So, by the rule of product, the elements of the permutation (1) n₁! * n₂! *... * n_k! ways, so that the permutation (1) remains unchanged. The same is true about any other sequence of elements from (1).

For example:

m₁ m₁... m₁ m₂ m₂... m₂..... m_k m_k... m_k (2)

n₁ n₂-1 n_k

We can permute elements within their types in n₁! * n₂! *... *n_k! ways without changing the sequence (2).

That is why the set of all n! permutations is partitioned (divided) into subsets. Each subset contains n₁! * n₂! *... *n_k! indistinct permutations.

Conclusion: the number of different permutations with repetitions which can be made of the ser with a specification (n₁, n₂,..., n_k), is equal to:

P(n₁, n₂,..., n_k) = = ;

H/a: How many 18-permutations can be made of the letters in the word "обороноспособность"?