funkcje maki: Ile istnieje różnych funkcji różnowartościowych f : {0, 1, . . . , n} → {0, 1, . . . , n+1}?

piotr:

n+1 n

a nie: (n+2)! ?

Adamm: Każda taka funkcja różnowartościowa jest postaci f = g o s gdzie g:{0, 1, ..., n} −> {0, 1, ..., n+1} jest rosnąca a s:{0, 1, ..., n} −> {0, 1, ..., n} jest permutacją Faktycznie, uporządkuj f(0), ..., f(n) rosnąco jako f₀ < ... < f_n i niech f_i = f(n_i). Wtedy n_i −> i −> f_i daje nam takie złożenie. Jeśli g₁ = g₂ o s gdzie g_i są rosnące a s to permutacja Załóżmy że nie zachodzi s(i) = i dla każdego i, tzn. istnieje i<j takie że s(i)>s(j). Wtedy g₁(i) < g₁(j) ale z drugiej strony g₂(s(i)) > g₂(s(j)), sprzeczność. Zatem jeśli f = g₁ o s₁ = g₂ o s₂ są dwoma takimi reprezentacjami f, to s₁ = s₂ oraz g₁ = g₂. Zatem takie funkcje są w bijekcji z parami (g, s) gdzie g:{0, 1, ..., n} −> {0, 1, ..., n+1} jest rosnąca a s:{0, 1, ..., n} −> {0, 1, ..., n} jest permutacją. Takich permutacji (z definicji) jest (n+1)!, a funkcji rosnących jest (ponieważ każda taka funkcja jest zupełnie określona przez jej obraz, równoważnie dopełnienie tego obrazu) dokładnie n+2. Zatem wszystkich funkcji różnowartościowych jest (n+2)!.

Maciess: Myślę, że lepiej tu myśleć po prostu o liczbie ciągów n+1 elementowych, w których wyrazami są elementy zbioru {0,1,...,n+1} i dodatkowo są parami różne.

Adamm: przecież to to samo

ite: ale o ile prościej to brzmi