ТГиК-2019-Лекция-09.09.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Биекция (взаимно однозначное отображение)

Рассмотрим взаимно однозначное отображение \( f: A \longrightarrow B, |A|=n,|B|=m\)

Множество таких отображений (или функций) описывается так\[\left \{f: A \longrightarrow B\right \}\]

Тогда количество таких отображений описывается следующими символами\[ |\left \{f: A \longrightarrow B\right \}|\]

Как найти количество отображений f?

1) Запишем отображение элементов в виде таблицы

f:A->B
a1 a2 ... an
bi1 bi2 ... bin

2)

  • Если взять 1 элемент из А, то ему будут соответствовать m функций
  • Если взять 2 элемента из А, то им будут соответствовать m2 функций

...

  • Если взять n элементов из А, то есть всё множество А, то им будут соответствовать mn функций

3) Следовательно, \( |\left \{f: A \longrightarrow B\right \}| = m^n\)

Примеры

Рассмотрим бинарные векторы различной длины. Например, бинарный вектор длины 2 определяется так\[\left \{ <x,y> \mid x,y \in \left \{0,1 \right \} \right \} \]

1) Бинарный вектор длины 4, например, может выглядеть так: <0,1,0,0>

Сколько таких векторов может быть? Используя формулу, выведенную выше, получим 24

2) Сколько бинарных векторов длины n? По формуле: 2n

3) Усложним задачу. Пусть вектор будет в виде <a,b,c>, причем

\(a \in \left \{a,..., z \right \}\)

\(b \in \left \{0,...,9 \right \}\)

\(c \in \left \{0,1 \right \}^3\)

Сколько таких векторов можно получить? \(26*10*2^3\)

Перестановки

Способ 1. Применение правила сложения

1) Рассмотрим все перестановки некоторого множества А. Множество перестановок обозначим SA

\(S_A<= \left \{ <a_1, ..., a_n>, ..., <a_n, ..., a_1> \right \}\)


2) Запишем \( S_{A^{(i)}} \) через \( S_{A}: \)

\( S_{A} = \bigcup^{n}_{i=1} {S_{A^{(i)}}}\) где \(S_{A^{(i)}}\) - все перестановки, у которых первый элемент - \(a_{i}\)


3) Тогда \( \left | S_{A} \right | = \left | \bigcup^{n}_{i=1} { S_{A \backslash {a_{i}} }} \right | = \sum^{n}_{i=1} \left | {S_{A^{(i)}} } \right | = n * \left | S_{A^{(i)}} \right | = \left | S_{A \backslash {a_{i}}} \right | \)

4) Получим\[ \left | S_{A} \right | = n*(n-1)*...*1=n!\]

Способ 2. Применение правила умножения


1) Алгоритм по таблице. Рассмотрим для n=4

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

1) Пусть на первое место в перестановке мы поставили двойку (в 1 столбце она выделена жирным шрифтом). Выбрав элемент, зачеркиваем всю строку, где находится данный элемент. Это обозначение того, что, выбрав двойку, мы не можем выбрать её еще раз.

2) Переходим ко 2 столбцу. Выбираем следующий элемент из тех, которые не вычеркнуты. Пусть это будет тройка (во 2 столбце она выделена жирным шрифтом). Аналогично первому шагу зачеркиваем всю строку. И так далее.

Получим некоторое соответствие:

2 3 1 4
2 2 1 1

Выбор двойки. Она стояла на втором месте из всех незачеркнутых элементов: 2->2

Выбор тройки. Она стояла на втором месте из всех незачеркнутых элементов: 3->2

Выбор единицы. Она стояла на первом месте из всех незачеркнутых элементов: 1->1

Выбор четверки. Она стояла на первом месте из всех незачеркнутых элементов: 4->1

2) По правилу умножения получим\[ \left | S_{n} \right | = \left | A_{n} × A_{n-1} × ... × A_{1} \right | = \left | A_{n} \right | * ... * \left | A_{1} \right | = n*(n-1)*...*1 = n!\]

Простейшие комбинаторные величины

Пусть из n объектов нам нужно выбрать k штук. Критериев выбора два:

  1. Упорядоченность
  2. Наличие повторений

Случай 1. Упорядоченность и без повторений

k
n 1 1 1 ... 1
2 2 2 ... 2
3 3 3 ... 3
... ... ... ... ...
n n n ... n

Из таблицы следует\[n*(n-1)*...*(n-k+1)=\frac{n!}{(n-k)!} = A^k_n \]

Число \(A^k_n \) называется числом размещений из n по k

Случай 2. Неупорядоченность и без повторений

1) Пусть у нас есть k чисел. Их можно упорядочить k! способами

2) Число размещений из n по k в k! раз больше в силу того, что в размещениях учитывается порядок расположения элементов. Тогда\[ C^k_n = \frac{A^k_n}{k!} = \frac{n!}{(n-k)!*k!}\]

Число \( C^k_n\) называется числом сочетаний из n по k

Cлучай 3. Упорядоченность и наличие повторений

\(\bar{A}^k_n = n^k\)

Число \(\bar{A}^k_n\) называется числом размещений с повторениями из n по k

Случай 4. Неупорядоченность и наличие повторений

1) Рассмотрим множество \(A = \left \{ a_1, a_2, ..., a_n \right \}\)

2) Создадим множество \( С = \left \{ c_1, c_2, ..., c_n \right \}\) такое, что \( c_i\) - это количество вхождений в набор из k штук элемента \( a_i\)

3) Отметим, что \( \sum^\infty_{i=1} {c_i} = k,\) \( {c_i}\in \left \{ 0,...,k \right \}\)

4) Запишем С в виде последовательности нулей и единиц\[\underbrace {11...1}_{С_1} \mbox{ }0 \mbox{ } \underbrace {11...1}_{С_2} \mbox{ } 0 \mbox{ } \underbrace {11...1}_{С_3} \mbox{ } 0...\]

В первой группе \(С_1\) единиц, потом идёт 0, потом \(С_2\) единиц, потом 0 и так далее.

5) Получим, что у нас k единиц и n-1 нулей.

6) \( \bar{C}^k_n = C^{n-1}_{k+n-1}\)

Число \( \bar{C}^k_n \) называется числом сочетаний с повторениями из n по k

Таблица для запоминания

Упорядоченность Неупорядоченность
Без повторений \( A^k_n \) \( C^k_n\)
С повторениями \( \bar{A}^k_n\) \( \bar{C}^k_n \)