- 1. feladat F M
Tegyük fel, hogy
d
n
=
1
, hagyjuk el a
v
n
pontot.
- 2. feladat F M
Használjuk az előző eredményt és a binomiális
tételt.
- 3. feladat F M
Mutassuk meg, hogy
és használjuk a 2.5 azonosságot.
- 4. feladat F M
Minden
T
i
-t húzzunk össze egyetlen
v
i
pontra.
- 5. feladat F M
Próbáljuk meg rekonstruálni az elhagyott
b
1
,
…
,
b
n
−
1
pontok sorozatát; vegyük észre, hogy
b
i
az a legkisebb szám, mely nem fordul
elő a
b
1
,
…
,
b
i
−
1
,
a
i
,
…
,
a
n
−
1
számok között.
- 6. feladat F M
Vegyük el a fának egy élét minden lehetséges
módon.
- 7. feladat F M
(a) Bizonyítsuk be, hogy
(b) Használjuk ki azt a tényt, hogy
ahol
C
tetszőleges zárt göbe az origó
körül.
- 8. feladat F M
Használjuk 4.1-et. Az eredmény
n
!
(
n
−
l
)
!
S
(
n
−
2
,
l
)
.
- 9. feladat F M
(a) Használjuk a Binet-Cauchy formulát:
ahol
B
az
A
0
minden
(
n
−
1
)
×
(
n
−
1
)
almátrixán végigfut.
(b) Az
A
0
két sorának legfeljebb egy közös
nemnulla eleme van.
(c)
n
ponton a fák száma egyenlő a
K
n
, teljes
n
-gráf, feszítő fáinak a
számával.
- 10. feladat F M
Írjuk
D
-t
A
0
A
0
T
alakban, és a 4.9-hez hasonló
okoskodást használjunk.
- 11. feladat F M
Ez a feszítő fák száma a teljes páros gráfon, a
{
v
1
,
…
,
v
n
;
w
1
,
…
,
w
m
}
pontokon.
- 12. feladat F M
(a) Használjuk a szita-formulát és 4.4-et.
(b)–(c) Használjuk 4.9-et, vagy
4.12a-t.
- 13. feladat F M
(a) Tekintsük a
k
+
1
végpontú bináris fát úgy, mint egy
diagramot a
k
-tényezős szorzat kiszámolására. (b)
Képzeljük el, hogy egy ilyen fa élei falból vannak. A
gyökértől elindulva, sétáljunk a falrendszer körül,
mindig balra tartva. Írjunk egy 1-est, ha a gyökértől
elfelé megyünk egy élen, és
−
1
-et különben. Milyen
±
1
-sorozatok keletkeznek így?
- 14. feladat F M
Használjuk 4.4-et. Egy másik lehetőség,
bizonyítsuk be az alábbi rekurzív relációt.
- 15. feladat F M
Triviális: a
≠
a
pontokba menő élek függetlenül
választhatók.
- 16. feladat F M
(a) Végezzünk indukciót, a
v
1
-be menő éleket kétfelé osztva, a
C
1
,
C
2
osztályokba, és a
G
−
C
1
,
G
−
C
2
gráfokat tekintve.
(b) Tekintsük az
a
i
j
-ket, mint változókat és végezzük el
az
a
i
j
=
y
i
helyettesítést.
- 17. feladat F M
Ha van egy
x
fix pont, akkor egy ilyen
T
fát irányítsunk úgy, hogy egy
T
→
fenyőt kapjunk, melynek
x
a gyökere. Húzzuk össze
π
összes pályáját és vizsgáljuk meg a
T
→
képét.
- 18. feladat F M
A felső korlát bizonyításához tekintsük a
gyökeres síkfákat.
- 19. feladat F M
(a) Írjuk fel a jobb oldalt a következő formában.
ahol
T
végigfut a fák összes izomorfizmus
típusán.
(b) Jelöljük
W
n
(
d
)
-vel az olyan nemizomorf fák számát,
melyekben a gyökér foka
d
. A
W
n
(
d
)
számok generátorfüggvényét fejezzük ki
egy rögzített
d
-re a
w
(
x
)
függvényeként, a Pólya–Redfield
módszert használva.
- 20. feladat F M
(a)
w
(
x
)
-re teljesül a
egyenlőség, ahol
analitikus egy a
w
-nél nagyobb körben.
(b) Mutassuk meg, hogy
ahol
h
(
x
)
folytonos a zárt
|
x
|
≤
τ
körön.
- 21. feladat F M
A
per
A
minden kifejtési tagja azon 1-faktorok
számát, melyek egy adottal párhuzamosak.
- 22. feladat F M
Keressünk egy rekurzív relációt.
- 23. feladat F M
Végezzünk szitálást.
- 24. feladat F M
A
det
B
azon kifejtési tagjai, melyek olyan
permutációnak felelnek meg, melyeknek van legalább egy
páratlan ciklusuk, egymást kinullázzák.
- 25. feladat F M
(a) A
Pf
B
-ban lévő nemnulla tagok a
G
-beli 1-faktoroknak felelnek
meg.
(b) A
Pf
B
-beli tagok, melyek két 1-faktornak
felelnek meg, mikor kapnak egyforma előjelet?
- 26. feladat F M
A
det
B
-ben minden olyan tag, aminek nincs
1-faktor megfelelője, 0 várható értékű.
- 27. feladat F M
Bizonyítsuk be, hogy létezik egy olyan irányítás,
melyre az teljesül, hogy ha pozitív irányban
végigmegyünk akármelyik korlátos tartomány határán,
akkor páratlan sok olyan élen haladunk át, melynek az
irányítása megegyezik ezzel a körüljárással.
- 28. feladat F M
Irányítsuk a létrát úgy, ahogy a 13. ábra
mutatja, és alkalmazzuk 4.21-et és
4.23-at.
- 29. feladat F M
(a) Írjuk fel
a
n
2
-et
det
p
n
(
A
)
alakban, ahol
Használjuk 1.29-et, hogy
p
n
(
λ
)
gyökeit megkapjuk.
(b) Vegyük észre, hogy az (a) formula két polinom
rezultánsa és használjuk a Sylvester-féle determináns
alakot.
(c) Az (a) formulát használva,
log
a
n
n
2
egy olyan összeg lesz, mely az alábbi
integrált approximálja:
- 30. feladat F M
(a) Tekintsük az
n
×
n
-es sakktáblát úgy, mintha a
(
2
n
−
1
)
×
(
2
n
−
1
)
-es sakktábla minden második
négyzetéből keletkezne.
(b) Vegyük az „unióját”
G
-nek és duálisának.
- 31. feladat F M
Azonosítsuk
u
i
-t
v
i
-vel.
- 32. feladat F M
Keressünk egy rekurzív relációt.
- 33. feladat F M
Tekintsük
a
n
-et, mint egy mátrix permanensét és
fejtsük ki az első sor szerint. Keressünk szimultán
rekurzív relációt
a
n
-re és néhány vele analóg
számra.
- 34. feladat F M
Ez a szám a következő:
Fejtsünk ki az első sor szerint.
- 35. feladat F M
Végezzünk szitálást.
- 36. feladat F M
A szám az alábbi mátrix permanense
Számoljuk össze azokat a tagokat, melyek
k
elemet tartalmaznak a bal felső
blokkból.