Re: Кто умеет считать?

если n>m то ни одной:)

Re: Кто умеет считать?

это и так ясно

Re: Кто умеет считать?

мне почему-то кажется, что во всех остальных случаях число функций бесконечно

Re: Кто умеет считать?

очевидно, что это не так, раз A и B конечные множества

Re: Кто умеет считать?

m >= n

m * (m - 1) * ... * (m - n) * n ^ (m - n)

Re: Кто умеет считать?

По-моему это не очевидно.

Re: Кто умеет считать?

n^m

Re: Кто умеет считать?

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

Re: Кто умеет считать?

n!*n^(m-n)

Re: Кто умеет считать?

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

Re: Кто умеет считать?

> n^m

m^n

Re: Кто умеет считать?

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

Re: Кто умеет считать?

да, теперь очевидно) спасибо)

Re: Кто умеет считать?

Явно не считается. Равно (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)

и т.д.

Re: Кто умеет считать?

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

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

Re: Кто умеет считать?

s/подмножеств/непустых подмножеств/

Re: Кто умеет считать?

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

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

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

Re: Кто умеет считать?

Проверь, если 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

Re: Кто умеет считать?

Service Pack 2:

N = m! / n! * n^(m-n)

Re: Кто умеет считать?

Остынь, ответ уже дан.