LINUX.ORG.RU

Ответ на: комментарий от anonymous

вот у меня то же самое получилось, но в ответе другое выражение

seiken ★★★★★
() автор топика
Ответ на: комментарий от selezian

|A x B| = m*n, A x B конечно. f можно представить как f: (A x B) -> {0, 1}, тогда A x B x {0, 1} надмножество всевозможных f и оно тоже конечно, значит множество f тем более конечно.

seiken ★★★★★
() автор топика
Ответ на: комментарий от cvs-255

n
_____________
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
m |_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|

В каждом столбце находится хотя бы 1 элемент. Всего элементов m.
Возьмем сперва n. Их размещаем n^m способами.
Т.о. остается m-n элементов. Их надо разместить на (m-1)*n клетках.
Это делается C из (m-1)*n по (m-n) способами.

Итого количество возможных расположений точек на таком прямоугольнике равно n^m*(C из (m-1)*n по (m-n))

cvs-255 ★★★★★
()

Явно не считается. Равно (n! * S(m,n)), где S(m,n) - число Стирлинга второго рода. Последнее определяется как число разбиений множества из m элементов на n подмножеств без учёта их порядка; удовлетворяет ряду красивых соотношений, таких, как:

S(m,n) = n*S(m-1,n) + S(m-1,n-1)

\sum_{m\ge n} S(m,n) x^m/m! = (e^x-1)^n/n!

\sum_{m\ge n} S(m,n) x^m = x^n/(1-x)(1-2x)\dots(1-nx)

и т.д.

Miguel ★★★★★
()
Ответ на: комментарий от cvs-255

> Итого количество возможных расположений точек на таком прямоугольнике равно n^m*(C из (m-1)*n по (m-n))

Тебя не смущает, что общее количество функций (не обязательно сюрьективных) равно n^m?

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

Ну да, я какой-то бред написал.

Вот правильное решение: Сперва возьмем n точек и их надо разместить по n позициям без совпадения позиций. Это n! способов. Затем остается m-n точек и их надо разместить по n позициям, при этом возможные совпадения позиций без разницы. Это дает n^(m-n) способов.

Итого n!*n^(m-n)

cvs-255 ★★★★★
()
Ответ на: комментарий от cvs-255

Проверь, если m=3, n=2. Твоя формула дает 2!*2^1 = 4 Так?

А в действительности, вариантов больше. Вот смотри

Пусть A = {a,b,c} и B = {1,2}

Вот шесть сюръективных функций:

f(a) = 1, f(b) = 1, f(c) = 2

f(a) = 1, f(b) = 2, f(c) = 1

f(a) = 1, f(b) = 2, f(c) = 2

f(a) = 2, f(b) = 1, f(c) = 1

f(a) = 2, f(b) = 1, f(c) = 2

f(a) = 2, f(b) = 2, f(c) = 1

Uncle_Theodore ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.