zadania_Partycje.pdf

Matematykadyskretna-zadania

Zadanie1.

Pokaza¢,»eilo±¢podziałówliczby n na r składnikówjestrównailo±cipodziałów

liczby n onajwi¦kszymskładnikurównym r .

Rozwi¡zanie:

Niech p = p 1 + ... + p r 2 P ( n,r ).Podziałowi p odpowiadadiagramFerrersa:

p 1 • ··· •

··· ···

p r •

> =

r składników

> ;

Przyporz¡dkujmytemudiagramowijegodiagramdualny

p 1 ··· p r

• ··· • najwi¦kszyskładnikrówny r

···

•

Diagramowidualnemuodpowiadapodziałliczby n naskładnikinieprzekraczaj¡ce

r .Przyporz¡dkowaniejestbijekcj¡codowodzirówno±ci.

Zadanie2.

Zbada¢,czyilo±¢podziałówliczby n naconajwy»ej r składnikówjestrównailo±ci

podziałówtejliczbynasum¦składnikównieprzekraczaj¡cych r .

Rozwi¡zanie:

Podziałowiliczby n naconajwy»ej r składnikówodpowiadadiagramFerrersa

p 1 • ··· •

··· ···

p s •

> =

¬ r składników

> ;

Przyporz¡dkujmytemudiagramowidiagramdualny

p 1 ··· p s

• ··· • najwi¦kszyskładnik ¬ r

···

•

Diagramdualnyodpowiadapodziałowiliczby n naskładnikinieprzekraczaj¡ce r .

Przyporz¡dkowaniejestbijekcj¡,awi¦cbadanarówno±¢zachodzi.

Zadanie3.

Pokaza¢,»eilo±¢podziałówliczby n + k na k składnikówjestrównailo±cipodziałów

liczby n naconajwy»ej k składników,tzn.: P ( n + k,k )= p ( n,k ).

Rozwi¡zanie:

Niech( a 1 ,...,a k )b¦dziepodziałemliczby n + k na k składników.Przyporz¡dkujmy

temupodziałowipodział( a 1 − 1 ,...,a k − 1).Jesttopodziałliczby n naconajwy»ej

k składników.

Awi¦cfunkcja( a 1 ,...,a k ) ! ( a 1 − 1 ,...,a k − 1)wyznaczawzajemniejednoznaczn¡

odpowiednio±¢mi¦dzy P ( n + k,k )oraz p ( n,k )

Zadanie4.

Niech P ( n,k )oznaczaliczb¦podziałówliczby n nadokładnie k składników.Pokaza¢,

»e:

k X

P ( n,k )=

P ( n − k,i ) , dla n>k> 0

i =0

Rozwi¡zanie:

Niech p 2 P ( n,k ).Najwi¦kszyskładnikwpodziale p mo»ewynosi¢ n − ( k − 1).

Wtedy p =( n − ( k − 1) , 1 ,..., 1).

Podział p mo»eniezawiera¢liczby1lubmo»ezawiera¢liczby1wilo±ciod1do

k − 1.Niech p =( p 1 ,...,p k ).Przyporz¡dkujmytemupodziałowipodział q =( p 1 −

1 ,...,p k − 1).

Je±liwpodziale p niemaliczby1,to q 2 P ( n − k,k ).

Je±liwpodziale p wyst¦pujejednaliczba1,to q 2 P ( n − k,k − 1)

Je±liwpodziale p wyst¦puje k − 1liczb1,to q 2 P ( n − k, 1)

Topost¦powaniejestodwracalne.Je±li q =( q 1 ,...,q s )jestpodziałemliczby n − k na

conajwy»ej k składników,topodziałowi q przyporz¡dkujemypodział p 2 P ( n,k ),

taki»e

( p i = q i +1 , gdy i ¬ s

p i =1 , gdy i>s

p =( p 1 ,...,p k )=

Awi¦costatecznie

P ( n,k )=

k X

P ( n − k,i ) , dla n>k> 0

i =0

Zadanie5.

Pokaza¢,»eilo±¢podziałówliczby2 n nadokładnie n składnikówjestrównailo±ci

wszystkichpodziałówliczby n .

Rozwi¡zanie:

Zauwa»my,»e: P (2 n,n )= P ( n + n,n )= p ( n,n ).Jednak p ( n,n )oznaczadokładnie

zbiórwszystkichpodziałówliczby n .St¡d P (2 n,n )= p ( n ).

Zadanie6.

Pokaza¢nast¦puj¡c¡zale»no±¢dlapodziałówliczby:

P ( n,k )= P ( n − 1 ,k − 1)+ P ( n − k,k )

Rozwi¡zanie:

Niech =( a 1 ,...,a k )b¦dziepodziałemliczby n na k składników.Je±li a k =1,to

przyporz¡dkujmypodziałowi podział( a 1 ,...,a k − 1 ).Je±li a k > 1,topodziałowi

przyporz¡dkujemypodział( a 1 − 1 ,...,a k − 1).Funkcja

(

( a 1 ,...,a k − 1 ) , gdy a k =1

( a 1 − 1 ,...,a k − 1) , gdy a k > 1

( a 1 ,...,a k ) !

ustalawzajemniejednoznaczn¡odpowiednio±¢mi¦dzyzbiorem P ( n,k )isum¡zbio-

rów P ( n − 1 ,k − 1)oraz P ( n − k,k )

Zadanie7.

Podziałemsprz¦»onymliczby n nazywamypodziałokre±lonyprzeztranspozycj¦w

diagramieFerrersawierszyzkolumnami.Podziałsamosprz¦»onytopodziałliczby

n ,wktórympozamianiewierszyzkolumnamiwdiagramieFerrersaotrzymamyten

sampodział.

Poka»,»eilo±¢podziałówsamosprz¦»onychliczby n jestrównailo±cipodziałówlicz-

by n naró»neskładnikinieparzyste.

Rozwi¡zanie:

Niechdanyb¦dziepodziałsamosprz¦»ony liczby n .Odpowiadaj¡cytemupodziało-

widiagramFerrersajestsymetryczny.Zauwa»my,»eliczbapunktówwpierwszejko-

lumniediagramujestrównaliczbiepunktówwpierwszymwierszu.Ponadtopierwsza

kolumnaipierwszywierszmaj¡jedenpunktwspólny.Oznaczato,»esumapunktów

wpierwszejkolumnieiwpierwszymwierszujestliczb¡nieparzyst¡.Doanalogicz-

nychwnioskówdochodzimydlakolumnydrugiej,trzeciejitd.

Przyporz¡dkujmywi¦cpodziałowi podział ? ,któregoskładnikamib¦d¡sumy

odpowiednichwierszyikolumndiagramuFerrersaodpowiadaj¡cegopodziałowi .

Podział ? jestpodziałemliczby n naró»neskładnikinieparzyste.

Procestenjestodwracalny,st¡dwnioskujemy,»eilo±¢podziałówsamosprz¦»onych

liczby n jestrównailo±cipodziałówliczby n naró»neskładnikinieparzyste.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: