Galeria zdjęć interaktywnych

Polecenie 1

Zapoznaj się z przedstawioną poniżej galerią zdjęć interaktywnych. Przeanalizuj zaprezentowane w niej  rozwiązania zadań, w których jest pokazane, jak wyznaczyć liczbę funkcji niemalejących ze skończonego zbioru A do skończonego zbioru B.

1
RMGvRms3dW3WV
Ilustracja pierwsza. Rozpatrzmy dwa zbiory a i b. a=1,2,3,...,k gdzie k≥1 a to zbiór k początkowych dodatnich liczb całkowitych. b=1,2,3,...,n. n≥1 b to zbiór n początkowych dodatnich liczb całkowitych. Wykażemy, że liczba wszystkich funkcji niemalejących, których dziedziną jest zbiór A i o wartości ze zbioru B jest równa k+n-1k. Niemalejąca funkcja f spełnia warunki zadania wtedy i tylko wtedy, gdy
1≤f1≤f2≤f3≤…≤fk≤n.
1

1. {audio}Niemalejąca funkcja f spełnia warunki zadania wtedy i tylko wtedy, gdy

1≤f1≤f2≤f3≤…≤fk≤n.
RgA6ykenDO3KD
Ilustracja druga. sprawdzimy poprawność wzoru dla kilku przykładowych zbiorów a oraz b. przykład pierwszy. Obliczymy ile jest funkcji niemalejących f, których dziedziną jest zbiór A=1,2,3,4 i których wartości są w zbiorze B=1,2. Wtedy niemalejąca funkcja f spełnia warunki
1≤f1≤f2≤f3≤f4≤2
,bezpośrednio sprawdzamy że dla tak ustalonych zbiorów a i b jest 5 funkcji które spełniają warunki zadania f1=f2=f3=f4=1
. f1=f2=f3=1, f4=2
. f1=f2=1, f3=f4=2
. f1=1, f2=f3=f4=2
(5)  f1=f2=f3=f4=2. Sprawdzamy że przyjmując we wzorze k równe 4 i n równe 2 otrzymujemy poniższą wartość 4+2-14=54=5
1
2

1. {audio}Wtedy niemalejąca funkcja f spełnia warunki

1≤f1≤f2≤f3≤f4≤2

2. {audio}(1) f1=f2=f3=f4=1
(2) f1=f2=f3=1, f4=2
(3) f1=f2=1, f3=f4=2
(4)f1=1, f2=f3=f4=2
(5)  f1=f2=f3=f4=2

RYgsVb9yQdTo8
Ilustracja trzecia. Przykład drugi. Obliczymy ile jest funkcji niemalejących f których dziedziną jest zbiór A=1,2,3,4,...,100 i których wartości są w zbiorze B=1,2. Wtedy niemalejąca funkcja f spełnia warunki
1≤f1≤f2≤f3≤...≤f100≤2>
, Dla tak ustalonych zbiorów liczba funkcji niemalejących jest równa liczbie sposobów przydzielania wartości 2 najmniejszemu z możliwych do wyboru argumentów. Ponieważ tych sposobów jest 101, wiec tyle jest funkcji niemalejących które spełniają warunki zadania.. Możemy wartości 2 nie przydzielić żadnemu z argumentów, wtedy f1=f2=f3=...=f100=1.

Poza tym przypadkiem najmniejszy argument, dla którego funkcja f przyjmuje wartość 2 możemy wybrać spośród elementów zbioru A=1,2,3,4,…,100, czyli na 100 sposobów:
(1) f1=f2=f3=...=f100=2
(2) f1=1, f2=f3=...=f100=2
(3) f1=f2=1, f3=...=f100=2
…
(99) f1=f2=f3=...=f98=1, f99=f100=2
(100) f1=f2=f3=...=f98=f99=1, f100=2

Łącznie mamy więc 101 możliwości. Sprawdzamy ze przyjmując we wzorze k równe 100 oraz n równe 2 otrzymujemy poniższą wartość. 100+2-1100=101100=101
R1WzO1fxGcFJr
Ilustracja czwarta. Przykład trzeci. Obliczymy ile jest funkcji niemalejących f których dziedziną jest zbiór A=1,2,3,4,5 i których wartości są w zbiorze B=1,2,3. Wtedy niemalejąca funkcja f spełnia warunki
1≤f1≤f2≤f3≤f4≤f5≤3
. Zliczanie przeprowadzimy w trzech rozłącznych przypadkach.
1

1. {audio}Wtedy niemalejąca funkcja f spełnia warunki

1≤f1≤f2≤f3≤f4≤f5≤3
RPvQ5fRNYLdL8
Ilustracja piąta. Przypadek pierwszy. korzystając ze spostrzeżeń poczynionych przykładzie 2 obliczymy ile jest funkcji niemających f których dziedziną jest zbiór A=1,2,3,4,5 i których wartości są zbiorze B1=1,2 dla tak ustalonych zbiorów liczba funkcji nie malejących jest równa liczbie sposobów przydzielania wartości 2 najmniejszemu z możliwych do wyboru argumentów. ponieważ tych sposobów jest 6 więc w tym przypadku jest 6 funkcji niemalejących. Możemy wartości 2 nie przydzielić żadnemu z argumentów, wtedy f1=f2=f3=f4=f5=1

Poza tym przypadkiem najmniejszy argument, dla którego funkcja f przyjmuje wartość 2 możemy wybrać spośród elementów zbioru A=1,2,3,4,5, czyli na 5 sposobów:
(1) f1=f2=f3=f4=f5=2
(2) f1=1, f2=f3=f4=f5=2
(3) f1=f2=1, f3=f4=f5=2
(4) f1=f2=f3=1, f4=f5=2
(5) f1=f2=f3=f4=1, f5=2

Łącznie mamy więc 6 możliwości.
1

1. {audio}Możemy wartości 2 nie przydzielić żadnemu z argumentów, wtedy f1=f2=f3=f4=f5=1

Poza tym przypadkiem najmniejszy argument, dla którego funkcja f przyjmuje wartość 2 możemy wybrać spośród elementów zbioru A=1,2,3,4,5, czyli na 5 sposobów:
(1) f1=f2=f3=f4=f5=2
(2) f1=1, f2=f3=f4=f5=2
(3) f1=f2=1, f3=f4=f5=2
(4) f1=f2=f3=1, f4=f5=2
(5) f1=f2=f3=f4=1, f5=2

Łącznie mamy więc 6 możliwości.

Rxl2qktLAsm7M
Ilustracja szósta. Przypadek drugi. obliczymy ile jest funkcji niemających f których dziedziną jest zbiór A=1,2,3,4,5 i których wartości są zbiorze B2=2,3. W tym przypadku nie bierzemy pod uwagę funkcji stałej równej dwa która została rozpatrzona wcześniej. dla tak ustalonych zbiorów liczba funkcji nie malejących jest równa liczbie sposobów przydzielania wartości 3 najmniejszemu z możliwych do wyboru argumentów ponieważ tych sposobów jest 5, więc w tym przypadku jest 5 funkcji nie malejących. Najmniejszy argument, dla którego funkcja f przyjmuje wartość 3 możemy wybrać spośród elementów zbioru A=1,2,3,4,5, czyli na 5 sposobów:
(1) f1=f2=f3=f4=f5=3
(2) f1=2, f2=f3=f4=f5=3
(3) f1=f2=2, f3=f4=f5=3
(4) f1=f2=f3=2, f4=f5=3
(5) f1=f2=f3=f4=2, f5=3

W tym przypadku jest 5 funkcji niemalejących.
1

1. {audio}Najmniejszy argument, dla którego funkcja f przyjmuje wartość 3 możemy wybrać spośród elementów zbioru A=1,2,3,4,5, czyli na 5 sposobów:
(1) f1=f2=f3=f4=f5=3
(2) f1=2, f2=f3=f4=f5=3
(3) f1=f2=2, f3=f4=f5=3
(4) f1=f2=f3=2, f4=f5=3
(5) f1=f2=f3=f4=2, f5=3

W tym przypadku jest 5 funkcji niemalejących.

RVBsZ2F9WCskE
Ilustracja siódma. Przypadek trzeci. obliczymy ile jest funkcji nie malejących f , których dziedziną jest zbiórA=1,2,3,4,5 i których zbiorem wartości jest zbiór B1=1,2,3. Dla tak ustalonych zbiorów liczba funkcji nie malejących jest równa liczbie sposobów wyznaczenia takich argumentów x indeks dolny jeden koniec indeksu, x indeks dolny 2 koniec indeksu, x indeks dolny 3 koniec indeksu że by spełnione były warunki. 1≤x1≤x2≤x3≤5. fx=1 dla wszystkich x takich, że 1≤x≤x1. fx=2 dla wszystkich x takich, że x1≤x≤x3. fx=3 dla wszystkich x takich, że x3≤x≤5. zauważmy że aby spełnić powyższe warunki wystarczy wybrać 3 różne liczby ze zbioru A=1,2,3,4,5 co można zrobić na 53=10 Sposobów. Zauważmy, że jeżeli przy opisanym powyżej wyborze trzech liczb ze zbioru A=1,2,3,4,5 oznaczymy: najmniejszą z wylosowanych przez x1, największą – przez x3, a trzecią z nich - przez x2, to wszystkie cztery podane warunki będą spełnione. a więc w tym przypadku jest 10 funkcji niemalejących
1

1. {audio}Zauważmy, że jeżeli przy opisanym powyżej wyborze trzech liczb ze zbioru A=1,2,3,4,5 oznaczymy: najmniejszą z wylosowanych przez x1, największą – przez x3, a trzecią z nich - przez x2, to wszystkie cztery podane warunki będą spełnione.

R1OowRUZ0zuxc
ilustracja ósma. Przypadek trzeci. Ostatecznie stwierdzamy, że łączna liczba funkcji niemalejących ze zbioru A=1,2,3,4,5 do zbioru B=1,2,3. Jest równa. 6+5+10=21. Po rozpatrzeniu trzech przypadków ostatecznie stwierdzamy, że liczba funkcji niemalejących ze zbioru A do zbioru B jest równa 21. Sprawdzamy, że przyjmując we wzorze k równe 5 n równe 3 otrzymujemy powyższą wartość. 5+3-15=75
1

1. {audio}Po rozpatrzeniu trzech przypadków ostatecznie stwierdzamy, że liczba funkcji niemalejących ze zbioru A do zbioru B jest równa 21.

RlRxhTL4Vr8Xd
Ilustracja dziewiąta. Przykład czwarty. Obliczymy ile jest funkcji niemalejących f, których dziedziną jest zbiór A=1,2,3,4,5,6,7 i których wartości są w zbiorze B=1,2,3,4. W tym celu zmodyfikujemy pomysł, który był zaprezentowany w rozwiązaniu trzeciego przypadku poprzedniego przykładu. Oznaczmy przez. X indeks dolny jeden koniec indeksu. liczbę tych argumentów funkcji f, którym przypisano wartość 1. X indeks dolny 2 koniec indeksu. liczbę tych argumentów funkcji f, którym przypisano wartość 2. X indeks dolny 3 koniec indeksu. liczbę tych argumentów funkcji f, którym przypisano wartość 3. X indeks dolny 4 koniec indeksu. liczbę tych argumentów funkcji f, którym przypisano wartość 4. Wtedy każda z liczb X indeks dolny jeden koniec indeksu. X indeks dolny 2 koniec indeksu. X indeks dolny 3 koniec indeksu. X indeks dolny 4 koniec indeksu. Jest nieujemna oraz spełniony jest warunek. x1+x2+x3+x4=7. Niemalejąca funkcja f, dla której f1=f2=f3=f4=2, f5=3, f6=f7=4 spełnia warunki zadania.
Tak opisana funkcja jednoznacznie określa wartości: x1=0, x2=4, x3=1,x4=2.

Z drugiej strony – jeżeli przyjmiemy x1=2, x2=2, x3=0, x4=3, to jednoznacznie określimy funkcję niemalejącą f, dla której f1=f2=1, f3=f4=2, f5=f6=f7=4.
1

1. {audio}Niemalejąca funkcja f, dla której f1=f2=f3=f4=2, f5=3, f6=f7=4 spełnia warunki zadania.
Tak opisana funkcja jednoznacznie określa wartości: x1=0, x2=4, x3=1,x4=2.

Z drugiej strony – jeżeli przyjmiemy x1=2, x2=2, x3=0, x4=3, to jednoznacznie określimy funkcję niemalejącą f, dla której f1=f2=1, f3=f4=2, f5=f6=f7=4.

RhYpW6J7c8xzd
Ilustracja dziesiąta. Przykład czwarty. Ponieważ liczba wszystkich rozwiązań równania. x1+x2+x3+x4=7. W liczbach nieujemnych X indeks dolny 3 koniec indeksu. X indeks dolny 4 koniec indeksu. Jest równa 7+4-17=107=120, więc dokładnie tyle jest funkcji niemalejących ze zbioru A=1,2,3,4,5,6,7 do zbioru zbiorze B=1,2,3,4. Skorzystaliśmy z twierdzenia:
Liczba wszystkich rozwiązań równania
x1+x2+...+xn=k
w nieujemnych liczbach całkowitych x1,x2,...,xn, gdzie n oraz k to ustalone dodatnie liczby całkowite, jest równa
k+n-1k
przyjmując w nim: n=4 i k=7. Zauważmy, że analizując zadanie zaproponowanym sposobem otrzymaliśmy bezpośrednie odwołanie do wzoru k+n-1k. W którym k jest równe 7 oraz n jest równe cztery.
Rzw5vAJJZX5Xx
Ilustracja jedenasta. Przykład czwarty. Przystępujemy do dowodu w przypadku ogólnym. Obliczymy ile jest funkcji niemalejących f, których dziedziną jest zbiór A=1,2,3,...,k, gdzie k≥1. I których wartości są w zbiorze B=1,2,3,...,n, gdzie n≥1. Wtedy niemalejąca funkcja f spełnia warunki
1≤f1≤f2≤f3≤…≤fk≤n.
,Oznaczmy przez. X indeks dolny 1 koniec indeksu. Liczbę tych argumentów funkcji f którym przypisano wartość jeden. X indeks dolny 2 koniec indeksu. Liczbę tych argumentów funkcji f którym przypisano wartość dwa. X indeks dolny 3 koniec indeksu. Liczbę tych argumentów funkcji f którym przypisano wartość trzy. X indeks dolny 4 koniec indeksu. Liczbę tych argumentów funkcji f którym przypisano wartość cztery. X indeks dolny n koniec indeksu. Liczbę tych argumentów funkcji f którym przypisano wartość n. Wtedy każda z liczb x indeks dolny 1 koniec indeksu, x indeks dolny 2 koniec indeksu, x indeks dolny 3 koniec indeksu, x indeks dolny n koniec indeksu, jest nieujemna oraz spełniony jest warunek. x1+x2+x3+...+xn=k. Dla dowolnej funkcji niemalejącej f jednoznacznie określone są wartości
x1,x2,x3,...,xn
a także:
jeżeli ustalimy wartości x1,x2,x3,...,xn, to jednoznacznie określimy funkcję niemalejącą f.
RBLj33v3k0qht
Ilustracja dwunasta. Przykład czwarty. Zatem liczba wszystkich funkcji niemalejących, których dziedziną jest zbiór A i o wartościach ze zbioru B jest równa liczbie rozwiązań równania. x1+x2+x3+...+xn=k. W liczbach nieujemnych x indeks dolny 1 koniec indeksu, x indeks dolny 2 koniec indeksu, x indeks dolny 3 koniec indeksu, x indeks dolny n koniec indeksu. Jak wiemy przy ustalonych ograniczeniach dla niewiadomych liczba rozwiązań powyższego równania jest równa. k+n-1k.. a więc tyle jest funkcji niemalejących f, których dziedziną jest zbiór A=1,2,3,...,k, gdzie k≥1. I których wartości są w zbiorze B=1,2,3,...,n, gdzie n≥1. W ten sposób dowód został zakończony.
1

1. {audio}W ten sposób dowód został zakończony.

Polecenie 2

Korzystając z rozwiązań zadań omówionych w powyższej galerii rozwiąż samodzielnie następujące zadanie.

Rozpatrzmy wszystkie funkcje niemalejące f, których dziedziną jest zbiór A=1,2,3,4,5,6,7,8 i których wartości są w zbiorze B=1,2,3,4,5.
Oblicz, ile spośród tych funkcji spełnia warunek f4<f5.

Przeczytaj
Sprawdź się