Ile istnieje funkcji rosnących odwzorowujących zbiór X w Y?

[MultiGumis]

Dane są dwa zbiory X i Y takie, że \(\displaystyle{ \left| X\right|=n}\) i \(\displaystyle{ \left| Y\right|=k}\), gdzie \(\displaystyle{ k \ge n}\). Obliczyć ile istnieje funkcji rosnących odwzorowujących zbiór X w zbiór Y.

Wiem, że funkcji odwzorowujących X w Y jest \(\displaystyle{ k ^{n}}\) ale nie wiem jak mam obliczyć ile jest funkcji rosnących odwzorowujących X w Y. Proszę o pomoc.

[a4karo]

W przypadku \(\displaystyle{ X=\{\triangle, \circ, \square\}, Y=\{\cup, \cap\}}\) nie ma żadnej

[kerajs]

Toż ten przykład nie spełnia warunku: \(\displaystyle{ k \ge n}\)

Układam elementa zbioru X w kolejności wzrostu, i elementa Y takoż. Ciachnąłwszy \(\displaystyle{ {k \choose k-n}}\) elementów z Y, postęp rosnący dostaję.
Ergo:
\(\displaystyle{ {k \choose k-n}}\) postępów rosnących jest.

[MultiGumis]

Toż ten przykład nie spełnia warunku: \(\displaystyle{ k \ge n}\)

Układam elementa zbioru X w kolejności wzrostu, i elementa Y takoż. Ciachnąłwszy \(\displaystyle{ {k \choose k-n}}\) elementów z Y, postęp rosnący dostaję.
Ergo:
\(\displaystyle{ {k \choose k-n}}\) postępów rosnących jest.

A mógłbym jeszcze prosić o wytłumaczenie dlaczego \(\displaystyle{ {k \choose k-n}}\)? Bo w sumie to nie rozumiem.

[a4karo]

Toż ten przykład nie spełnia warunku: \(\displaystyle{ k \ge n}\)

Toż to jedna ryba. Żeby mówić o funkcji rosnącej trzeba mieć porządek. Na dowolnych zbiorach raczej ich nie ma.

[kerajs]

@ a4karo
A Japońce jakoś dają radę: 39985,2250.htm#p5422071

@ MultiGumis
Funkcja jest rosnąca gdy dla każdego \(\displaystyle{ x_i<x_j}\) zachodzi \(\displaystyle{ f(x_i)<f(x_j)}\)
Porządkuję więc zbiory X i Y

np:    

\(\displaystyle{ X=left{ 2,3,5,6,8,10,11,23,25,46
ight}\
Y=left{ 0,1,2,3,4,5,6,8,9,11,12,14,15
ight} \
n=10 wedge k=13}\)

Aby otrzymać dowolną funkcję muszę skreślić k-n elementów ze zbioru Y (aby ilość elementów w obu zbiorach była równa) oraz przyporządkować i-temu elementowi X i-ty element Y.

np:    

\(\displaystyle{ X=left{ 2,3,5,6,8,10,11,23,25,46
ight}\
Y=left{ 0,1,2, ,4,5, , ,9,11,12,14,15
ight}\
\
2
ightarrow 0\
3
ightarrow 1\
...\
...\
46
ightarrow 15}\)

Funkcji będzie tyle, ile sposobów skreślenia k-n elementów ze zbioru k elementowego, czyli \(\displaystyle{ {k choose k-n}}\)

np:    

\(\displaystyle{ {13 choose 13-10}= {13 choose 3}=286}\)

[MultiGumis]

Dziękuję bardzo