szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Podział liczby
PostNapisane: 15 lip 2017, o 13:01 
Użytkownik

Posty: 167
Lokalizacja: Polska
Dla ustalonego podziału \pi liczby n, niech A(\pi) oznacza liczbę jedynek w \pi, zaś B(\pi) - liczbę różnych składników w \pi.
Przykład: dla podziału \pi: 1 + 1 + 2 + 2 + 2 + 4 mamy A(\pi) = 2 oraz B(\pi) = 3.
Udowodnij, że \sum_{\pi}^{} A(\pi) =  \sum_{\pi}^{} B(\pi), gdzie sumowanie odbywa się po wszystkich podziałach ustalonej liczby n.

Wskazówka: Spróbuj wyrazić każdą ze stron tożsamości przez P(1), P(2), ..., P(n-1), gdzie P(k) to łączna liczba podziałów liczby k.


Pomoże ktoś?
Góra
Mężczyzna Offline
PostNapisane: 15 lip 2017, o 14:58 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Interpretacja kombinatoryczna:
Pokażemy, że \sum_{\pi}^{} A(\pi) =  \sum_{i = 0}^{n - 1} P(i).
Sortujemy podziały rosnąco (tak żeby kolejne składniki podziału były ustalone w porządku niemalejącym). Taki podział może zaczynać się od pewnej liczby jedynek. Jeżeli na i-tej pozycji w takim podziale jest 1, to wcześniej też są same 1. Suma składników występujących po tej jedynce to n - i. Zliczamy dla każdej pozycji i w ilu podziałach na i-tej pozycji występuje jedynka. Takich podziałów jest tyle co podziałów liczby po tej jedynce, czyli P(n - i).

Pokażemy, że \sum_{\pi}^{} B(\pi) = \sum_{i = 0}^{n - 1} P(i).
Zliczamy osobno dla każdej liczby w ilu podziałach występuje. Bierzemy dowolną liczbę i występującą w podziale. Reszta tego podziału to n - i. Dlatego liczba podziałów, w których występuje ta liczba to P(n - i). Sumujemy po i i dostajemy to co chcemy.
Góra
Mężczyzna Offline
PostNapisane: 15 sie 2017, o 21:37 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
To jest zadanie nr 5 z USAMO 1986:

https://mks.mff.cuni.cz/kalva/usa/usoln/usol865.html
https://artofproblemsolving.com/community/c6h424771p2403884

-- 20 sierpnia 2017, 19:44 --

Poza tym to zadanie było na egzaminie poprawkowym z MD dla informatyki MIMUW w 2016 r. jako zadanie nr 2:
http://wakacjezmd.github.io/2016/egzamin/2/
http://i.imgur.com/wXxtskpg.jpg
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podział liczby  Maath  1
 Podział liczby - zadanie 4  cis123  1
 Podział liczby - zadanie 2  pingwindyktator  4
 liczby stirlinga 2 rodzaju i symbol newtona - tożsamość  unK  3
 liczby ze zbioru powtarzające się  jemcole  1
cron
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl