Egyenként döntsünk a személyekről.
Döntsünk most a levelezőlapokról. A válasz a
második kérdésre
Ha a betűk összes permutációját vesszük, hányszor fog ugyanaz a szó előfordulni?
(a) Képzeljünk el
(b) Redukáljuk a problémát az előző feladatra úgy, hogy minden személynek kölcsönzünk egy forintot.
A különböző levelezőlapokról egymástól függetlenül dönthetünk.
(a) A rekurzív relációk a következők
(b) Vegyük észre, hogy az
(c) A Stirling-féle partíciós számok esetén, írjuk fel (a)-t
alakban, hogy megkapjuk a negatív
(d)
(a) Ha
Végezzük el a következő helyettesítést:
(a) Használjuk fel, hogy
(b) Mutassuk meg, hogy az (a)-beli összeg tagjainak eloszlása aszimptotikusan normális; legyen
akkor
Tekintsük az egy adott elemet tartalmazó partíciós osztályt.
Használjuk az előző rekurzív relációt, hogy egy
differenciálegyenletet kapjunk
(a) Egy partícióra tekintsük az összes olyan
permutációt, melyben az osztályok a hosszúság
tekintetében nem-csökkenő sorrendben vannak elrendezve.
(b) Az eredmény közelítőleg
Tekintsük az
(a) A
(a) Használjuk az alábbi rekurzív relációt:
(b) Használjuk
Reprezentáljuk a
Rendeljük egymáshoz az
Legyen
egy partíció különböző tagokra. Írjuk
Ha
az
Állítsuk elő mindegyik generátorfüggvényt szorzatalakban, úgy mint az előző feladatban.
Az
Az (a) azonosság azt a tényt fejezi ki, hogy a
különböző páratlan tagokból álló partíciók száma
megegyezik a szimmetrikus Ferrers diagrammal rendelkező
permutaciók számával. (Szimmetrikus abban az
értelemben, hogy tükrösek a bal alsó sarokból induló
Döntsük el, hogy 1-gyel indulva, melyik szám,
milyen multiplicitással kell, hogy előforduljon egy
ilyen partícióban. Ha az 1
Ha
Keressünk egy 2-lépéses rekurzív relációt
Keressünk egy rekurzív relációt
Vezessünk le egy rekurzív relációt
Bizonyítsuk be, hogy a
a karakterisztikus polinom kielégíti az alábbi rekurzív összefüggést:
Jelöljük
Használjunk az 1.17 megoldásához hasonló ötleteket.
Egy ilyen függvény grafikonja úgy tekinthető mint
egy poligon, mely az
Kényelmesebben dolgozhatunk az olyan
Jelöljük a kérdéses számot
Tekintsük az eljárást visszafelé.
Használjunk indukciót a következőképpen: vegyük
el
Redukáljuk (b)-t az előző problémára.
Rendeljünk hozzá a
Használjuk az alábbi rekurzív összefüggést:
A háromszögek egy láncot alkotnak.
(a) Számítsuk ki a
(b) Tekintsük a Pascal háromszöget.
(c) Keressünk egy kombinatorikus interpretációt.
(d) Ez az
(e)
(f) Legyen
(g) Keressünk egy rekurzív összefüggést ezen
számok között (
(h) Bizonyítsuk be indukcióval, hogy az eredmény
(i) Az eredmény
(a) Keressünk egy kombinatorikus értelmezést.
(b) Helyettesítsünk
(c) Hajtsuk végre az alábbi helyettesítést
(d) Helyettesítsünk
(e) Fejtsük ki az
Hogy belássuk (a)-t, differenciáljuk mindkét
oldalt
Használjuk, hogy