Число сюръекций
По этой ссылке вы найдёте полный курс лекций по математике:
некоторые множества. Отображение называется сюръ-екциеи, если всякий элемент множества У является образом некоторого элемента множества X: Определим образ множества при заданном отображении как множество образов всех его элементов: Отображение является сюръекцией тогда и только тогда, когда Пусть — конечные множества: причем п ^ т.
Найдем число всех сюръекций f : X У.
Возможно вам будут полезны данные страницы:
Введем в рассмотрение следующие множества: — множество всех отображений из — множество всех сюръекций; Число сюръекций Легко видеть, что . Вновь находит применение формула включения-исключения! Каждое отображение / можно задать размещением (с повторениями) объема . Для отображений / А элементы указанного размещения выбираются из т-элементного множества У;для / -элементного множества для /)-элементного множества .
Формула для числа размещений с повторениями
уже известна читателю; применив ее, получим Таким образом, Итак, число сюръекций n-элементного множества в m-элементное множество равно Число сюръекций Пример, п различных шаров нужно разместить по m различным ящикам так, чтобы ни один ящик не остался пустым. Каким числом способов это можно сделать? Распределение шаров по ящикам можно рассматривать как отображение множеава шаров в множество ящиков4, отсутствие пустых ящиков соответствует тому, что указанное отображение является сюръекцией. Число сюръекций подсчитано выше.
Утверждение
8.1.
Число
всех отображений f
: X
Y
равно nm.
Рассмотрим построение f
как поэтапный процесс. На первом шаге
выбираем f
(x1),
на втором — f
(x2),
и т. д. На каждом из m
шагов имеется n
возможностей. Таким образом, общее
количество разных последовательностей
выборов равно nm.
Разным последовательностям выборов
соответствуют разные функции.
Примеры.
1. Удобно представлять отображение f
: X
Y
как раскладывание m
помеченных шаров в n
различных ящиков.
2.
Пусть требуется подсчитать число
m-мерных
векторов, каждая координата которых
может принимать любое значение из
Y
= {y1,
y2,…,
yn}.
Очевидно, эта задача эквивалентна
предыдущей. 3. Любую целочисленную
nn–матрицу,
все элементы которой равны 0, 1 или –1,
можно рассматривать как отображение f
: {1,2,…,n2
}
{0, 1, –1}, и, наоборот, отображение — как
матрицу. Тогда число таких матриц равно
.
4.
Пусть производится m
опытов (называемых упорядоченными
выборками с возвращениями),
состоящих в том, что из генеральной
совокупности Y
наудачу выбирается какой-нибудь элемент
yi,
результат опыта фиксируется, а затем
элемент возвращается в генеральную
совокупность. Понятно, что, поставив
последовательности {yi1,
yi2,…,
yim}
исходов этих опытов в соответствие
вектор {yi1, yi2,…,
yim},
получим взаимно однозначное соответствие
между множеством различных
последовательностей исходов наших
опытов и множеством m-мерных
векторов с координатами из Y.
Таким образом, число упорядоченных
выборок с возвращениями подсчитывается
по той же схеме. Утверждение
8.5.
А.
Число сюръективных отображений f
: X*
Y
(X*
означает,
что элементы X
неразличимы)
равно
;
Б.
Число всех отображений f
: X*
Y
равно
.
А).
Так как f
— сюръективное отображение, то справедливо
| f
–1(y1)
| + | f
–1(y2)
| + | f
–1(y3)
| + . . . + | f
–1(yn)
| = m
,
где
| f–1(yi)
| = ai
> 0, i
= 1, 2,…, n,
или a1
+ a2
+ … + an
= m.
Поставим в соответствие набору
(a1, a2,…, an)
двоичный вектор, в котором ai
единиц разделяются 0
(1)
Очевидно,
что соответствие между векторами (1) и
сюръективными отображениями f
является биекцией (элементы X*
неразличимы).
Подсчет векторов (1) можно трактовать
как подсчет расстановок n
– 1 перегородок (нулей) на m
– 1 место между m
единицами (две перегородки не могут
располагаться рядом из-за сюръективности
f
).
Ясно, что это можно сделать
способами.
Б).
Если f
не являться сюръекцией, то прообразы
некоторых элементов yY
могут не существовать, т. е. | f
(y)
|–1
=
0. Это значит, что в любой промежуток
разрешается ставить любое количество
перегородок. Подсчитаем число таких
расстановок. В (1) имеется m – n + 1
мест для 1 и перегородок. Ставим на любые
n
–1 из них перегородки, а оставшиеся
места автоматически заполняются 1. Число
способов сделать это равно
.
Примеры.
1. Число способов раскладывания m
одинаковых шаров в n
различных ящиков равно
.
2.
Допустим, мы бросаем m
одинаковых игральных костей. Тогда
можно различить
разных исходов бросания.
3.
Число векторов {y1,
y2,…,
yn}
в Rn
с целочисленными неотрицательными
координатами, удовлетворяющими уравнению
или y1
+ y2
+ … + yn
= 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)! перестановок.
На
практике не пользуются столь бесхитростным
способом распознавания гамильтоновости,
а применяют различные алгоритмы
частичного перебора. Однако и там
наблюдается такой же эффект — т. е.
негамильтоновость установить, как
правило, труднее, чем гамильтоновость.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
$begingroup$
It is quite easy to calculate the total number of functions from a set $X$ with $m$ elements to a set $Y$ with $n$ elements ($n^{m}$), and also the total number of injective functions ($n^{underline{m}}$, denoting the falling factorial). But I am thinking about how to calculate the total number of surjective functions $fcolon X twoheadrightarrow Y $.
The way I thought of doing this is as follows: firstly, since all $n$ elements of the codomain $Y$ need to be mapped to, you choose any $n$ elements from the $m$ elements of the set $X$ to be mapped one-to-one with the $n$ elements of $Y$. This results in $n!$ possible pairings. But the number of ways of choosing $n$ elements from $m$ elements is $frac{m!}{(m-n)!,n!}$, so the total number of ways of matching $n$ elements in $X$ to be one-to-one with the $n$ elements of $Y$ is $frac{m!}{(m-n)!,n!} times n! = frac{m!}{(m-n)!}$.
Now we have ‘covered’ the codomain $Y$ with $n$ elements from $X$, the remaining unpaired $m-n$ elements from $X$ can be mapped to any of the elements of $Y$, so there are $n^{m-n}$ ways of doing this. Therefore I think that the total number of surjective functions should be $frac{m!}{(m-n)!} , n^{m-n}$.
Is this anything like correct or have I made a major mistake here?
asked Dec 25, 2012 at 0:57
user50229user50229
2,9822 gold badges26 silver badges50 bronze badges
$endgroup$
$begingroup$
Consider $f^{-1}(y)$, $y in Y$. This set must be non-empty, regardless of $y$. What you’re asking for is the number of ways to distribute the elements of $X$ into these sets.
The number of ways to distribute m elements into n non-empty sets is given by the Stirling numbers of the second kind, $S(m,n)$. However, each element of $Y$ can be associated with any of these sets, so you pick up an extra factor of $n!$: the total number should be $S(m,n) n!$
The Stirling numbers have interesting properties. They’re worth checking out for their own sake.
answered Dec 25, 2012 at 1:37
AndrewGAndrewG
2,54018 silver badges35 bronze badges
$endgroup$
4
$begingroup$
Here is a solution that does not involve the Stirling numbers of the second kind, $S(n,m)$. The number of surjective functions from a set $X$ with $m$ elements to a set $Y$ with $n$ elements is
$$
sum_{i=0}^{n-1} (-1)^i{n choose i}(n-i)^m
$$
or more explicitly
$$
{n choose 0}n^m – {n choose 1}(n-1)^m + {n choose 2}(n-2)^m – cdots pm {n choose n-2}2^m mp {n choose n-1}1^m
$$
We begin by counting the number of functions from $X$ to $Y$, which is already mentioned to be $n^m$. Next we subtract off the number $n(n-1)^m$ (roughly the number of functions that miss one or more elements). Of course this subtraction is too large so we add back in ${n choose 2}(n-2)^m$ (roughly the number of functions that miss 2 or more elements). But again, this addition is too large, so we subtract off the next term and so on. This is a rough sketch of a proof, it could be made more formal by using induction on $n$.
Sooraj S
7,3173 gold badges40 silver badges78 bronze badges
answered Dec 21, 2013 at 21:28
AdamAdam
1571 silver badge4 bronze badges
$endgroup$
0
$begingroup$
This gives an overcount of the surjective functions, because your construction can produce the same onto function in more than one way.
Consider a simple case, $m=3$ and $n=2$. There are six nonempty proper subsets of the domain, and any of these can be the preimage of (say) the first element of the range, thereafter assigning the remaining elements of the domain to the second element of the range. In other words there are six surjective functions in this case.
But your formula gives $frac{3!}{1!} 2^{3-2} = 12$.
Added: A correct count of surjective functions is tantamount to computing Stirling numbers of the second kind. The Wikipedia section under Twelvefold way has details. For small values of $m,n$ one can use counting by inclusion/exclusion as explained in the final portion of these lecture notes.
answered Dec 25, 2012 at 1:14
hardmathhardmath
36k20 gold badges71 silver badges139 bronze badges
$endgroup$
1
You must log in to answer this question.
Not the answer you’re looking for? Browse other questions tagged
.
Not the answer you’re looking for? Browse other questions tagged
.
Ну вот, это и есть формула из предыдущего сообщения, то есть количество всех сюрьекций m-элементного множества на n-элементное. Надо заменить в той формуле 
на 
, а 
на .
А беспорядок это биекция такого множества на себя без неподвижных точек. Там знакопеременная формула с факториаламии тоже построенная по этому принципу. То есть берём количество вообще всех перестановок, вычитаем те, у которых по крайней мере одна неподвижная точка, прибавляем те, у которых по крайней мере две и так далее.
Только в Вашей формуле небольшая ошибочка с минусом в средней части.
Переведём задачу на язык отображений. При выборе каждым из 10 своего этажа, получается отображение 10-элементного множества в 4-элементное. Всего таких отображений $%4^{10}$%. Среди них надо подсчитать число сюръективных. Поделив на число всех отображений, мы получим искомую вероятность.
Если отображение не сюръективно, то его образ состоит из 1, 2 или 3 элементов. Подсчитаем эти числа по отдельности, обозначая их через $%s_1$%, $%s_2$%, $%s_3$%.
Очевидно, что $%s_1=4$%, так как все эти отображения постоянны. Для подсчёта $%s_2$% сначала загадаем то 2-элементное подмножество, образ которого мы хотим получить. Это можно сделать $%C_4^2=6$% способами. Далее находим число отображений из 10 в 2 (по мощности); оно равно $%2^{10}$%. Среди таких отображений есть два постоянных, которые нам не подходят. Их нужно вычесть. Получается $%s_2=6(2^{10}-2)$%.
Теперь так же найдём $%s_3$%. Для начала у нас есть 4 способа выбрать 3-элементное подмножество в качестве образа. Теперь надо подсчитать число сюръекций из 10 в 3. Действуя тем же методом, мы из общего числа таких отображений вычитаем те, у которых образ имеет мощность 1 или 2. Это даёт $%3^{10}-3-3(2^{10}-2)$%. Умножая на 4, получаем значение $%s_3$%.
Итого число сюръекций равно $%4^{10}-s_1-s_2-s_3=818520$%. Вероятность равна $%102315/131072approx0,78$%.
См. также здесь общую формулу для числа сюръекций на стр.8.
