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

Макеты страниц

Утверждение
8.1.
Число
всех отображений f
: X

Y

равно n^m.
Рассмотрим построение f
как поэтапный процесс. На первом шаге
выбираем f
(x₁),
на втором — f
(x₂),
и т. д. На каждом из m
шагов имеется n
возможностей. Таким образом, общее
количество разных последовательностей
выборов равно n^m.
Разным последовательностям выборов
соответствуют разные функции. 

Примеры.
1. Удобно представлять отображение f
: X

Y
как раскладывание m
помеченных шаров в n
различных ящиков.

2.
Пусть требуется подсчитать число
m-мерных
векторов, каждая координата которых
может принимать любое значение из
Y
= {y₁,
y₂,…,
y_n}.
Очевидно, эта задача эквивалентна
предыдущей. 3. Любую целочисленную
nn–матрицу,
все элементы которой равны 0, 1 или –1,
можно рассматривать как отображение f
: {1,2,…,n²
}

{0, 1, –1}, и, наоборот, отображение — как
матрицу. Тогда число таких матриц равно

.

4.
Пусть производится m
опытов (называемых упорядоченными
выборками с возвращениями),
состоящих в том, что из генеральной
совокупности Y
наудачу выбирается какой-нибудь элемент
y_i,
результат опыта фиксируется, а затем
элемент возвращается в генеральную
совокупность. Понятно, что, поставив
последовательности {y_i1,
y_i2,…,
y_im}
исходов этих опытов в соответствие
вектор {y_i1, y_i2,…,
y_im},
получим взаимно однозначное соответствие
между множеством различных
последовательностей исходов наших
опытов и множеством m-мерных
векторов с координатами из Y.
Таким образом, число упорядоченных
выборок с возвращениями подсчитывается
по той же схеме. Утверждение
8.5.
А.
Число сюръективных отображений f
: X*

Y

(X*
означает,
что элементы X
неразличимы)
равно

;

Б.
Число всех отображений f
: X*

Y
равно

.

А).
Так как f
— сюръективное отображение, то справедливо
| f
^–1(y₁)
| + | f
^–1(y₂)
| + | f
^–1(y₃)
| + . . . + | f
^–1(y_n)
| = m
,

где
| f^–1(y_i)
| = a_i
> 0, i
= 1, 2,…, n,
или a₁
+ a₂
+ … + a_n
= m.
Поставим в соответствие набору
(a₁, a₂,…, a_n)
двоичный вектор, в котором a_i
единиц разделяются 0

(1)

Очевидно,
что соответствие между векторами (1) и
сюръективными отображениями f
является биекцией (элементы X*
неразличимы).
Подсчет векторов (1) можно трактовать
как подсчет расстановок n
– 1 перегородок (нулей) на m
– 1 место между m
единицами (две перегородки не могут
располагаться рядом из-за сюръективности
f
).
Ясно, что это можно сделать

способами.

Б).
Если f
не являться сюръекцией, то прообразы
некоторых элементов yY
могут не существовать, т. е. | f
(y)
|^–1
=
0. Это значит, что в любой промежуток
разрешается ставить любое количество
перегородок. Подсчитаем число таких
расстановок. В (1) имеется m – n + 1
мест для 1 и перегородок. Ставим на любые
n
–1 из них перегородки, а оставшиеся
места автоматически заполняются 1. Число
способов сделать это равно

.

Примеры.
1. Число способов раскладывания m
одинаковых шаров в n
различных ящиков равно

.

2.
Допустим, мы бросаем m
одинаковых игральных костей. Тогда
можно различить

разных исходов бросания.

3.
Число векторов {y₁,
y₂,…,
y_n}
в Rⁿ
с целочисленными неотрицательными
координатами, удовлетворяющими уравнению
или y₁
+ y₂
+ … + y_n
= m,
равно

.
12.1)
. . Гамильтоновы графы. Достаточные
условия гамильтоновости графа.

Граф
называется гамильтоновым,
если в нем имеется простой цикл, содержащий
каждую вершину этого графа. Сам этот
цикл также называется гамильтоновым.
Гамильтоновой
называют и простую цепь, содержащую
каждую вершину графа. Слово «гамильтонов»
в этих определениях связано с именем
известного ирландского математика
У. Гамильтона, которым в 1859 году
предложена следующая игра «Кругосветное
путешествие». Каждой из двадцати вершин
додекаэдра приписано название одного
из крупных городов мира. Требуется,
переходя от одного города к другому по
ребрам додекаэдра, посетить каждый
город в точности один раз и вернуться
в исходный город. Эта задача, очевидно,
сводится к отысканию в графе додекаэдра
(кубического плоского графа с 12 гранями
размера 5) простого цикла, проходящего
через каждую вершину этого графа.

Н
е
все связные графы гамильтоновы хотя бы
потому, что такой граф должен быть
двусвязным. Однако пример графа,
представленный на рис. 6.3, показывает,
что для гамильтоновости графа двусвязности
недостаточно.

Любой
граф, содержащий две вершины степени
3, соединенные тремя простыми попарно
непересекающимися цепями длины не менее
двух, называется тэта-графом
(рис. 6.3).

Теорема
6.3.
Каждый
негамильтонов двусвязный граф содержит
тэта-подграф.

Несмотря
на внешнее сходство постановок, задачи
распознавания эйлеровости и гамильтоновости
графа принципиально различны. Используя
теорему 6.1, легко узнать, является ли
граф эйлеровым. В случае положительного
ответа алгоритм Флёри позволяет
достаточно быстро построить один из
эйлеровых циклов.

Что
касается гамильтоновости, то ситуация
здесь существенно иная. Ответить на
вопрос, является ли данный граф
гамильтоновым, как правило, очень трудно.

Интуитивно
ясно, что если граф содержит много ребер
и эти ребра к тому же достаточно равномерно
распределены, то граф «предрасположен»
быть гамильтоновым. В двух приводимых
ниже теоремах можно усмотреть подтверждение
этому.

Теорема
6.4.
(O. Оре, 1960 г.). Если
для любой пары и несмежных вершин графа
G
порядка n

3
выполняется неравенство deg
u
+ deg
v

n
,
то G
— гамильтонов граф.
Из этой теоремы непосредственно
вытекает следующая

Теорема
6.5.
(Г. Дирак, 1952 г.). Если
в графе G
порядка n

3
для любой вершины v
выполняется неравенство deg
v

n
/2,
то G
— гамильтонов граф.

Нетрудно
заметить, что во всяком n-вершинном
графе, удовлетворяющем условиям из
рассмотренных выше теорем, число ребер
не меньше чем n(n
– 1)/4. С другой стороны, n-вершинный
планарный граф, как мы знаем, содержит
не более 3n
– 6 ребер. Поэтому рассмотренные выше
достаточные условия заведомо неприменимы
к планарным графам.

Если
в n-вершинном
графе G
фиксировать одну вершину и обход всегда
начинать с нее, то всякому гамильтонову
циклу очевидным образом будет
соответствовать перестановка элементов
множества VG.
Тем самым найти гамильтонов цикл либо
убедиться в отсутствии такого цикла
можно путем перебора (n
– 1)! перестановок. Если граф G
гамильтонов, то проделать этот перебор
в полном объеме придется только в случае
крайнего невезения — когда нужная, т.
е. отвечающая гамильтонову циклу
перестановка встретится последней в
этом процессе. Если же G
— негамильтонов граф, то действуя
подобным образом, придется в любом
случае проверить все (n
– 1)! перестановок.

На
практике не пользуются столь бесхитростным
способом распознавания гамильтоновости,
а применяют различные алгоритмы
частичного перебора. Однако и там
наблюдается такой же эффект — т. е.
негамильтоновость установить, как
правило, труднее, чем гамильтоновость.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

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

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

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

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

f:A->B

a1	a2	…	an
bi1	bi2	…	bin

2)

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

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

…

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

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

Примеры

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

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

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

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

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) Рассмотрим все перестановки некоторого множества А. Множество перестановок обозначим S_A

(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 )

Число сюръекций