Treść zadania

Rozwiązania

• 

  8 0

  antekL1 24.1.2017 (22:04)

  Mamy injekcję f : X --> Y gdzie
  skończony zbiór X ma n elementów, skończony zbiór Y ma m elementów.
  
  Jeżeli n > m to ilość takich funkcji jest równa zero, ponieważ:
  Pierwszym "m" elementom zbioru X przyporządkujemy jednoznacznie Yi = f(Xi).
  Tego wymaga "funkcja różnowartościowa".
  Dla elementu o numerze m+1 zbioru X nie istnieje już wolny element w zbiorze Y,
  Więc różnowartościowa funkcja X --> Y nie istnieje.
  
  Jeśli n = m to możemy zbiorowi { 1..n } przypisać jego dowolną permutację.
  Ilość tych permutacji = ilość funkcji = n! [ n silnia, wiesz, co to za zwierzę ]
  
  Jeśli n < m to:
  Pierwszemu elementowi zbioru X przypisujemy jeden z m elementów Y.
  To jest możliwe na m sposobów.
  Drugiemu elementowi X przypisujemy któryś z m - 1 elementów Y.
  Jak dotąd mamy: m (m - 1) sposobów,
  Trzeciemu elementowi... i tak dalej.
  W iloczynie ilość sposobów = ilość funkcji = m (m - 1)(m - 2)... (m - n + 1)
  Można to w skrócie zapisać jako: m! / ( m - n) !
  W rachunku prawdopodobieństwa jest to ilość "wariacji bez powtórzeń".
  ===========
  
  Przykład: n = 2, m = 4. Ilość funkcji: 4! / ( 4 - 2)! = 24 / 2 = 12
  Możliwości:
  f(1) = 1 ; f(2) = 2
  f(1) = 2 ; f(2) = 1
  f(1) = 1; f(2) = 3
  f(1) = 3; f(2) = 1
  .... i tak dalej po dwie funkcje dla różnych par po stronie Y, czyli takich:
  (1,4), (2,3), (2,4), (3,4).
  Razem mamy po 2 funkcje dla każdej z 6 możliwych par Y, czyli 12 funkcji.
  ==============================
  
  Przykład: n = 3, m = 4. Ilość funkcji: 4! / ( 4 - 3)! = 24 / 1 = 24
  Możliwości:
  f(1) = 1 ; f(2) = 2 ; f(3) = 3;
  f(1) = 1 ; f(2) = 2 ; f(3) = 4;
  f(1) = 1; f(2) = 3; f(3) = 2;
  f(1) = 1; f(2) = 3; f(3) = 4;
  f(1) = 1; f(2) = 4; f(3) = 2;
  f(1) = 1; f(2) = 4; f(3) = 3;
  no i popróbuj dalej :) dla f(1) = 2 też mamy 6 funkcji etc.
  ==============================
  
  W razie pytań pisz proszę na priv.

  Dodawanie komentarzy zablokowane - Zgłoś nadużycie