Zliczanie funkcji.

adek05 · Post autor: **adek05** » 9 lut 2008, o 12:30

Mając zadanie: Niech X = {-3,-2,-1} i Y = {5,6} wyznacz liczbę funkcji, które przekształcają zbiór X na Y.
W tym przypadku rozwiązanie jest proste, ale jak obliczyć liczbę tych funkcji wraz ze wzrostem liczebności zbiorów X i Y. Czy istnieje jakiś wzór, metoda?

scyth · Post autor: **scyth** » 9 lut 2008, o 13:25

każdy z elementów X może mieć dwie wartości (bo tyle jest elementów Y). Jeśli \(\displaystyle{ \# X}\) to liczba elemenów zbioru X to takich funkcji mamy: \(\displaystyle{ (\# X)^{\# Y}}\) (bo to \(\displaystyle{ \# Y}\) możliwości dla każdego argumentu z dziedziny).

adek05 · Post autor: **adek05** » 9 lut 2008, o 16:34

Wszystko ładnie, ale jest pewien problem, funkcja odwzorowuje X na Y co w moim zbiorze oznacza to samo co zbiór wartości funkcji. Czyli odpadają rozwiązania nie posiadające wszystkich elementów ze zbioru X.
Przykładowo dla wyżej podanego przypadku rozwiązaniem jest 6, a nie 9.

scyth · Post autor: **scyth** » 9 lut 2008, o 18:35

ok, po pierwsze to odwrotnie napisałem wzór - wykładnik trzeba zamienić z podstawą.
po drugie w takim razie trzeba wywalić te złe rozwiązania możesz zrobić to rekurencyjnie, w tym przypadku będzie:
\(\displaystyle{ 2^3-2\cdot1^3=8-2=6}\)

Przy większej ilości argumentów i wartości najpierw będzie - potem + potem - itd (włącz-wyłącz). Na pewno można to też rozwiązać kombinatorycznie, ale to później (chyba że ktoś sie pokusi o zrobienie tego zadania).

adek05 · Post autor: **adek05** » 10 lut 2008, o 10:08

Okej, dzięki
Tak czułem, że trzeba będzie odejmować