Mamy: {1,2,3} -> {1,2} i g: {1,2,3} -> {1,2,3,4}. Ile istnieje wstrzykiwanych funkcji f i g?

Odpowiedź:

#fa# nie może być wstrzykiwany.

#sol# może być wstrzykiwany #24# sposoby.

Wyjaśnienie:

Funkcja jest wstrzykiwana, jeśli żadne dwa wejścia nie zapewniają tego samego wyjścia. Innymi słowy, coś takiego

#f (x) = f (y), quad x ne y #

nie może się zdarzyć.

Oznacza to, że w przypadku domeny skończonej i kodomainy funkcja może być iniektywna wtedy i tylko wtedy, gdy domena jest mniejsza niż kodomena (lub co najwyżej równa), pod względem liczności.

Dlatego #fa# nigdy nie może być wstrzykiwany. W rzeczywistości możesz naprawić #f (1) # jak chcesz. Mówić #f (1) = 1 #, na przykład. Przy wyborze #f (2) #, nie możemy tego powtórzyć #f (2) = 1 #lub #fa# nie byłoby wstrzykiwane. Ale jeśli chodzi o #f (3) # nie mamy wyboru, jeśli powiemy #f (3) = 1 # mamy #f (1) = f (3) #i jeśli mówimy #f (3) = 2 # mamy #f (2) = f (3) #.

Innymi słowy, musimy przypisać jeden z dwóch możliwych wyjść do każdego z trzech wejść. Powinno być oczywiste, że wejścia nie mogą zapewnić różnych wyjść.

Z drugiej strony #sol# może być wstrzykiwany, ponieważ jest „wystarczająco dużo miejsca”: każde z trzech wejść może wybrać jedno z czterech wyjść w taki sposób, że żadne inne wejście nie zapewnia tego samego wyjścia.

Ale na ile sposobów? Załóżmy, że zaczniemy od nowa #f (1) #. Możemy wybrać dowolną z czterech wydajności dla tego wejścia, abyśmy mogli wybrać #f (1) # na cztery sposoby.

Jeśli chodzi o #f (2) #, tracimy trochę wolności: możemy przypisać dowolną wartość #f (2) #, z wyjątkiem tego, do którego przydzieliliśmy #f (1) #, więc mamy dwie możliwości. Na przykład, jeśli naprawiliśmy #f (1) = 2 #, następnie #f (2) # może być #1#, #3# lub #4#.

Zgodnie z tą samą logiką mamy do wyboru dwie opcje #f (3) #: z czterech możliwych wyborów wykluczamy te, które już zostały przypisane #f (1) # i #f (3) #.

Możemy więc zdefiniować #sol# w #4*3*2 = 24# sposoby takie #sol# jest wstrzykiwany.