- 1. feladat Ö M
Egy üzletben
k
-féle levelezőlapot árusítanak. Lapot akarunk küldeni
n
barátunknak. Hányféleképpen tehetjük ezt meg? Mi
történik, ha különböző lapokat akarunk nekik küldeni? Mi történik,
ha mindegyiküknek két különböző lapot akarunk küldeni (de különböző
személyek kaphatnak egyforma lapot)?
- 2. feladat Ö M
k
különböző levelezőlapunk van és szét akarjuk mindet küldeni
n
barátunknak (mindenki tetszőleges számú lapot kaphat, beleértve a
0
-t is). Hányféleképpen tehetjük ezt meg. Mi
történik, ha azt akarjuk, hogy mindenki kapjon legalább egy lapot?
- 3. feladat Ö M
Hány anagramma készíthető a KARAKTERIZÁCIÓ szóból?
(Anagrammának nevezzük egy szó betűiből kikeverhető szavakat úgy,
hogy minden betűt pontosan ugyanannyiszor használunk mint az
eredeti szóban; az új szavaknak nem kell, hogy értelmük
legyen.)
- 4. feladat Ö M
(a) Hányféleképpen oszthatunk ki
k
forintot
n
ember között úgy, hogy mindenki kap legalább
1
forintot?
(b) Tegyük fel, hogy nem ragaszkodunk ahhoz a
kikötéshez, hogy mindenki kapjon valamit. Mi lesz ebben az
esetben a kiosztások száma?
- 5. feladat Ö M
k
-fajta levelezőlapunk van, mindegyikből adott számú, az
i
-edikből
a
i
darab. Hányféleképpen küldhetjük el ezeket
n
barátunknak? (Előfordulhat, hogy valaki ugyanabból a lapból többet is kap.)
- 6. feladat Ö M
(a) Keressünk rekurziós formulát a Stirling-féle partíciós számokra,
n
k
-ra, és a Stirling-féle ciklikus számokra,
n
k
-ra, és számítsuk ki az értéküket
n
≤
6
esetén.
(b) Mutassuk meg, hogy
n
n
−
k
és
n
n
−
k
n
-nek polinomjai minden fix
k
-ra.
(c) Mutassuk meg, hogy
n
k
és
n
k
egyértelműen terjeszthető ki minden egész
n
-re és
k
-ra az (a) részben meghatározott rekurzív relációt
megtartva, a következő „határfeltételek” mellett:
0
0
=
0
0
=
1
és
0
m
=
m
0
=
0
(
m
≠
0
).
(d) Bizonyítsuk be az alábbi dualitási relációt:
- 7. feladat Ö M
Bizonyítsuk be az alábbi azonosságokat:
(a)
∑
k
=
0
n
n
k
x
(
x
−
1
)
…
(
x
−
k
+
1
)
=
x
n
,
(b)
∑
k
=
0
n
n
k
x
k
=
x
(
x
+
1
)
…
(
x
+
n
−
1
)
,
(c)
∑
k
=
0
n
(
−
1
)
k
n
k
k
j
=
1
,
ha
j
=
n
,
0
,
különben.
- 8. feladat Ö M
Bizonyítsuk be, hogy
Speciálisan, a jobb oldal 0 ha
k
>
n
(vö. 2.4).
- 9. feladat Ö M
(a) Jelöljük
B
n
-nel az
n
-edik Bell számot, azaz
n
számú tárgy összes partíciójának a számát.
Bizonyítsuk be az alábbi formulát:
ahol
λ
(
n
)
úgy van definiálva, hogy
λ
(
n
)
log
λ
(
n
)
=
n
.
- 10. feladat Ö M
Keressünk rekurzív formulát
B
n
-re.
- 11. feladat Ö M
Legyen
p
(
x
)
a
B
n
sorozat exponenciális generátorfüggvénye, azaz
Határozzuk meg
p
(
x
)
-et.
- 12. feladat Ö M
(a) Bizonyítsuk be, hogy
Vezessük le a
p
(
x
)
-re adott formulát ebből a kifejezésből.
(b) Mit kapunk (aszimptotikusan) ha az összegzést
az összes olyan
(
k
1
,
…
,
k
n
)
-re terjesztjük ki, melyre
k
1
+
k
2
+
…
k
n
=
n
?
- 13. feladat Ö M
Adjunk egy másik bizonyítást a
egyenlőségre.
- 14. feladat Ö M
(a) Legyen
Q
n
az
n
-elemű halmaz páratlan sok osztályt tartalmazó
partícióinak a száma (
Q
0
=
1
). Határozzuk meg
és keressük meg az 1.9a-beli formula analogonját.
(b) Legyen
R
n
az
n
-elemű halmaz páros sok osztályt tartalmazó
partícióinak a száma (
R
0
=
1
). Határozzuk meg az
generátorfüggvényt.
- 15. feladat Ö M
Jelölje
S
n
egy verseny összes lehetséges kimeneteleinek a
számát, ahol döntetlen is előfordulhat. Pontosabban, jelölje
S
n
azon
f
:
{
1
,
…
,
n
}
→
{
1
,
…
,
n
}
leképezések számát, melyekre teljesül, hogy ha
f
felveszi az
i
értéket, akkor minden
j
,
1
≤
j
≤
i
, értéket is felvesz. Legyen
S
0
=
1
.
(a) Bizonyítsuk be az alábbi azonosságokat:
és határozzuk meg a következő generátorfüggvényt:
(b) Bizonyítsuk be az alábbi aszimptotikát:
- 16. feladat Ö M
Az
n
szám
r
-nél nem több tagú partícióinak a száma megegyezik
n
azon partícióinak a számával, ahol minden tag legfeljebb
r
nagyságú.
- 17. feladat Ö M
Az
n
szám pontosan
m
tagú partícióinak a száma megegyezik az
n
−
m
szám
m
-nél nem több tagú partícióinak a számával.
Keressünk egy hasonló azonosságot az
n
szám pontosan
m
különböző tagú partícióinak a számára.
- 18*. feladat Ö M
Az
n
szám különböző, de tetszőleges sok tagú
partícióinak száma megegyezik az
n
páratlan sok tagú partícióinak számával.
- 19*. feladat (Ötszögszámok tétele) Ö M
Ha
n
≠
3
k
2
±
k
2
, akkor az
n
páratlan sok különböző tagú partícióinak száma
megegyezik a páros sok különböző tagú partícióinak számával.
- 20. feladat Ö M
Legyen
π
n
az
n
szám partícióinak száma. Határozzuk meg a
π
n
sorozat generátorfüggvényét.
- 21. feladat Ö M
Bizonyítsuk be, hogy az
n
szám különböző tagokból álló partícióinak száma
megegyezik a páratlan sok tagú partícióinak a számával (1.18),
mindkét oldal generátorfüggvényének felhasználásával.
- 22. feladat Ö M
Milyen azonosság következik az 1.19
feladatból?
- 23*. feladat Ö M
A következő azonosságokat kombinatorikus okoskodás segítségével lássuk be:
- 24. feladat Ö M
Az
n
szám olyan tulajdonságú partícióit keressük,
melyekre teljesül, hogy minden
1
és
n
közti szám egyértelműen áll elő a partíció
bizonyos elemeiből. Mikor lesz a triviális
n
=
1
+
…
+
1
partíció az egyetlen megoldás?
- 25. feladat Ö M
A
2
n
kerületű, nem egybevágó, egész oldalú háromszögek
száma megegyezik a
2
n
−
3
kerületű és egész oldalú, nem egybevágó
háromszögek számával. Ez a szám továbbá megegyezik az
n
szám pontosan háromtagú partícióinak a számával.
Adjuk meg ezt a számot.
- 26. feladat Ö M
Van
n
forintunk. Minden nap pontosan egyet vásárolunk az
alábbi termékekből: perec (1 forint), cukorka (2 forint), fagylalt
(2 forint). Határozzuk meg
M
n
-et, ahányféleképpen elkölthetjük a
pénzünket.
- 27. feladat Ö M
Határozzuk meg
A
n
-et, ahányféleképpen megmászhatunk egy
n
fokú lépcsőt, ha vagy egy vagy két lépcsőfokot
teszünk meg minden lépéssel. Határozzuk meg a
generátorfüggvényt.
- 28. feladat Ö M
(a) Van
n
forintunk és minden nap pontosan egy dolgot
vásárolunk. Pontosan
a
i
féle árut vehetünk
i
forintért (
i
=
1
,
…
,
k
). Tegyük fel, hogy az
x
k
−
a
1
x
k
−
1
−
…
−
a
k
polinomnak a különböző gyökei
ϑ
1
,
…
,
ϑ
k
. Mutassuk meg, hogy a pénzünket
-féleképpen költhetjük el.
(b) Határozzuk meg
C
n
generátorfüggvényét, és ezáltal egy formulát
C
n
-re.
- 29. feladat Ö M
Határozzuk meg az alábbi mátrix sajátértékeit:
- 30. feladat Ö M
Hány
n
hosszúságú sorozat képezhető az
a
,
b
,
c
,
d
betűkből azon feltétel mellett, hogy
a
és
b
sohasem szomszédosak?
- 31. feladat Ö M
Hány
k
-ast választhatunk ki az
1
,
…
,
n
elemekből úgy, hogy nincs köztük két egymás utáni
egész szám?
- 32. feladat Ö M
Mi az
{
1
,
…
,
n
}
-et önmagába leképező monoton növő függvények
száma?
- 33. feladat Ö M
(a) Hány olyan monoton növő
f
leképezése van az
{
1
,
…
,
n
}
-nek önmagába, mely kielégíti az
f
(
x
)
≤
x
feltételt minden
1
≤
x
≤
n
-re?
(b) Mi azon sorozatok száma, melyekben a 0-k és 1-esek száma egyaránt
n
, továbbá az első
k
elem között, minden
1
≤
k
≤
2
n
-re, legalább annyi 0 van, ahány 1-es?
- 34. feladat Ö M
Mutassuk meg, hogy az olyan
(
x
1
,
…
,
x
r
)
(
1
≤
x
i
≤
n
) sorozatok száma, melyekben kevesebb, mint
i
szám van az
(
1
,
…
,
i
)
intervallumból minden
i
=
1
, …,
n
-re, egyenlő
(
n
−
r
)
n
r
−
1
-vel, ahol
(
1
≤
r
≤
n
).
- 35. feladat Ö M
Az
n
-elemű
S
halmaz partícióinak egy sorozatát képezzük a
következő módon: Magával az
S
halmazzal indulunk, aztán az
(
i
+
1
)
-edik partícióit az
i
-edikből úgy kapjuk, hogy az
i
-edik partíció valamelyik 1-nél több elemet
tartalmazó osztályát szétvágjuk két nem üres részhalmazra. Így a
csupa 1-elemű osztályt tartalmazó partícióhoz
n
−
1
lépés után jutunk el. Hányféleképpen hajthatjuk
végre ezt az eljárást?
- 36. feladat Ö M
Az előző feladatot úgy módosítjuk, hogy az
i
+
1
-edik partícióit az
i
-edikből úgy kapjuk, hogy minden 1-nél több elemet
tartalmazó osztályt két nem üres részre vágunk szét. Mi lesz most a
lehetséges végrehajtások száma?
- 37. feladat Ö M
Egy
n
hosszúságú botot
n
egységnyi hosszúságú darabra akarunk széttörni. Mi
a lehetséges végrehajtások száma, ha
(a) minden lépésben egy 1-nél hosszabb darabot törünk ketté,
(b) minden lépésben minden 1-nél hosszabb darabot
kettétörünk.
- 38. feladat Ö M
Hányféleképpen zárójelezhetjük az
x
1
⋅
x
2
⋅
…
⋅
x
r
szorzatot (abban az értelemben, hogy minden
zárójelpár pontosan két tényezőt zár be)?
- 39. feladat Ö M
Határozzuk meg egy konvex
n
-szög háromszögeléseinek
D
n
számát. (Egy háromszögelés
n
−
3
átlóból áll, melyek egymást nem metszik belső
pontban, ezért az
n
-szöget
n
−
2
háromszögre vágják fel.)
- 40. feladat Ö M
Határozzuk meg
D
n
generátorfüggvényét az előző feladat felhasználása
nélkül és lássuk be ennek segítségével az előző feladat
eredményét.
- 41. feladat Ö M
Hányféleképpen vághatjuk szét a konvex
n
-szöget
n
−
3
egymást nem metsző átlóval úgy háromszögekre, hogy
mindegyik háromszögnek legyen egy közös oldala a konvex
n
-szöggel?
- 42. feladat Ö M
Keressünk zárt formulát az alábbi formulák mindegyikére:
- 43. feladat Ö M
Bizonyítsuk be az alábbi azonosságokat:
- 44*. feladat Ö M
Bizonyítsuk be az alábbi Abel-azonosságokat:
- 45. feladat Ö M
Legyen
Mutassuk meg, hogy
Keressünk más példát ilyen polinomsorozatra.