- 1. feladat F Ö
Vonjuk le 30-ból azon tanulók számát, akik
szeretik a matematikát, fizikát, ill. a kémiát:
Ilyenkor azonban azoknak a tanulóknak a
számát, akik mind a matematikát, mind a fizikát
szeretik, kétszer vontuk le; tehát ezt hozzá kell adni
az összeghez, és ugyanígy a többi tantárgypárra is:
De ekkor még mindig bajunk van azokkal, akik
mindhárom tárgyat szeretik, őket háromszor vontuk le,
de háromszor hozzá is adtuk, tehát még egyszer hozzá
kell adnunk, hogy a helyes eredményt kapjuk
- 2. feladat F Ö
(a) Legyen
az
A
1
,
…
,
A
n
által generált Boole-algebra egy
tetszőleges atomja (az indexek megfelelő választásával,
minden atom felírható ilyen formában). A formulában
szereplő minden esemény bizonyos atomok (diszjunkt)
uniója; fejezzünk ki minden
P
(
A
I
)
és
P
(
A
1
+
…
+
A
n
)
valószínűséget, mint a megfelelő
atomok valószínűségeinek az összegét. Megmutatjuk, hogy
tetszőleges, adott atom valószínűsége kiesik.
P
(
B
)
együtthatója a bal oldalon
B
akkor és csak akkor fordul elő az
A
I
-ben, ha
I
⊆
{
1
,
…
,
k
}
, így a jobb oldalon az együtthatója
Így
P
(
B
)
-nek az együtthatója mindkét oldalon
ugyanaz, ami (a)-t bizonyítja.
(b) Válasszuk
S
egy
x
elemét az egyenletes eloszlás szerint.
Ekkor
A
i
azonosítható azzal az eseménnyel, hogy
x
∈
A
i
, és kapjuk, hogy
A fentiek szerint kapjuk, hogy
vagy ami ezzel ekvivalens,
A (b) állítás ezután már következik, ha
|
S
|
-kel szorzunk.
- 3. feladat F Ö
Legyen
A
i
a
p
i
-vel osztható, 1 és
n
közti egészek halmaza. Ekkor
tetszőleges
I
⊆
{
1
,
…
,
r
}
halmazra,
és így
Ebből
Most
∏
i
∈
I
p
i
végigfut az
n
számnak azokon az osztóin, amelyek
egyik prím négyzetével sem oszthatók. Ahhoz, hogy
(1)-et szebb alakra hozzuk, definiáljuk a következő
függvényt:
Ekkor
Ugyanakkor észrevehetjük, hogy (1) az alábbi
szorzat kifejtése:
- 4. feladat F Ö
Legyen
|
X
|
=
k
,
Y
=
{
y
1
,
…
,
y
n
}
. Ekkor
X
azon leképezéseinek a száma
Y
-ba, melyek ráképezések, nyilvánvalóan
Másrészt, jelölje
A
i
az
X
-nek
(
Y
−
y
i
)
-be történő leképezéseinek halmazát,
és legyen
S
az
X
összes
Y
-ba történő leképezéseinek a halmaza.
Ekkor bennünket
|
S
−
(
A
1
∪
…
∪
A
n
)
|
érdekel. A szita-formula szerint
Itt
A
I
az
X
-nek
(
Y
−
{
y
i
:
i
∈
I
}
)
-be történő leképezéseinek a halmaza,
ebből
Így
ami az állítást bizonyítja.
Ha
k
>
n
, ugyanez a szitálási eljárás az
X
-nek
Y
-ra való leképezéseinek a számát adja,
mely
n
!
k
n
. Így az eredményből egy új
bizonyítást kapunk 1.8-ra.
- 5. feladat F Ö
Írjuk
x
i
=
0
-t
σ
0
p
−
σ
1
p
+
…
-ba. Ekkor, a
jelöléssel kapjuk, hogy
σ
k
p
|
x
i
=
0
=
σ
k
−
1
p
˜
+
σ
k
p
˜
(a
p
változóinak egy
k
-asa vagy tartalmazza, az
x
i
)-t, vagy nem, és
így
Ezért
x
1
…
x
n
osztója
σ
0
p
−
σ
1
p
+
…
-nak. Mivel
σ
0
p
−
σ
1
p
+
…
foka legfeljebb
m
, ebből következik, hogy
Vegyük észre azt is, hogy
σ
k
p
(
k
≥
1
) biztos, hogy nem tartalmaz
x
1
…
x
n
alakú tagot; ezért az
x
1
…
x
n
együtthatója
c
-vel egyenlő
σ
0
p
=
p
-ben. Megjegyezzük, hogy
p
(
x
1
,
…
,
x
n
)
=
(
x
1
+
…
+
x
n
)
k
és
x
1
=
…
=
x
n
=
1
esetén az előző eredményt kapjuk (vö.
4.3)
- 6. feladat F Ö
Fejezzük ki a
P
(
B
)
valószínűséget, mint atomok
valószínűségének összegét; megmutatjuk, hogy minden
atom együtthatója nemnegatív lesz. Legyen
az
A
1
,
…
,
A
n
által generált Boole-algebra egy
tetszőleges atomja. Legyen
A
1
′
=
…
=
A
k
′
=
1
,
A
k
+
1
′
=
…
=
A
n
′
=
0
, és legyen
B
i
′
=
f
i
(
A
1
′
,
…
,
A
n
′
)
. Ekkor
B
⊆
B
i
akkor és csak akkor teljesül, ha
B
i
′
≠
0
. Ezért
P
(
B
)
együtthatója a
∑
i
=
1
k
c
i
P
(
B
i
)
összegben
a feltétel szerint.
- 7. feladat F Ö
(a) Az előző eredmény alapján feltehetjük, hogy
Ekkor a bal oldal értéke 1, ha
k
=
q
és 0 ha
k
≠
q
; a jobb oldal pedig
Ha
q
>
k
, ez az összeg, nyilvánvalóan, 0 lesz.
Ha
q
=
k
, az összeg 1 lesz. Végül, ha
q
<
k
, akkor
Így azt kapjuk, hogy
(b)
E
η
j
várható érték az
A
1
,
…
,
A
n
események azon
j
-esei a számának várható értéke, ahol
mind a
j
bekövetkezik. Mivel egy adott
{
A
i
1
,
…
,
A
i
j
}
j
-es együttes előfordulásának a
valószínűsége
P
(
A
i
1
…
A
i
j
)
, azt kapjuk, hogy
Így
- 8. feladat F Ö
Felhasználva az előző eredményt, a meghatározandó
valószínűség
1.42h szerint.
- 9. feladat F Ö
Legyen
j
>
0
, páratlan. Ekkor meg akarjuk mutatni,
hogy
2.6 szerint, feltehetjük, hogy
A
k
=
0
eset triviális, ezért legyen
k
≥
1
. Ekkor meg kell mutatnunk, hogy
ha
j
páratlan. Ez világos, ugyanúgy, mint
1.42h-ban:
A páros
j
esete hasonlóan következik.
- 10. feladat F Ö
I. 2.6 szerint ismét feltehetjük, hogy
Ekkor
így, amit bizonyítanunk kell, az az, hogy
vagy
k
r
-rel végigosztva,
ami világos [M. Frèchet].
II. Az alábbi egyenlőtlenséget bizonyítjuk:
a megszokott módon. Elég megmutatni, hogy
Rendezés után kapjuk, hogy
Ez világos, ha
k
<
m
, tegyük fel tehát, hogy
k
≥
m
. Végigosztva a bal oldallal, kapjuk,
hogy
ami nyilvánvalóan igaz.
Ha még azt is tudjuk, hogy
σ
r
+
1
=
0
, akkor azt kapjuk, hogy
σ
r
≤
1
r
σ
r
−
1
.
- 11. feladat F Ö
I. Tegyük fel, hogy
A
1
,
…
,
A
n
ilyen események, és legyen
J
⊆
{
1
,
…
,
n
}
. A 2.2a szitaformula szerint
Mivel egy valószínűség mindig nemnegatív, kapjuk, hogy
minden
J
⊆
{
1
,
…
,
n
}
-re. És nyilvánvalóan,
II. Megmutatjuk, hogy (2) és (3) elégséges.
Vegyük az összes
v
J
atomot (
J
⊆
{
1
,
…
,
n
}
), és legyen
Ekkor
Azt állítjuk, hogy
egy valószínűségi mértéket definiál
A
∅
-án, és
P
(
A
I
)
=
p
I
. Mutassuk meg először a második
állítást:
Itt
így azt kapjuk, hogy
Ahhoz, hogy megmutassuk, hogy
P
egy valószínűségi mérték, mindössze
annyit vegyünk észre, hogy (2)-ből következik, hogy
P
≥
0
, míg (3)-ból következik, hogy
P
(
A
∅
)
=
1
.
- 12. feladat F Ö
Elég az egyenlőtlenséget bizonyítani abban az
esetben, ha van egy olyan
K
⊆
{
1
,
…
,
n
}
halmaz, melyre
2.6 miatt. Ha
K
=
∅
, akkor mindkét oldal értéke 1. Legyen
tehát
K
≠
∅
. Az általánosság megszorítása nélkül
feltehetjük, hogy
K
=
{
1
,
…
,
n
}
; mert különben tekinthetjük a
K
által feszített részgráfot. Ekkor az
egyenlőtlenség ilyen alakú lesz:
Ezt a következővel együtt bizonyítjuk:
n
szerinti indukcióval. Ha
G
egy teljes gráf, akkor
így (4) és (5) teljesülnek. Tegyük fel, hogy
G
nem teljes, és legyen mondjuk
n
∈
V
(
G
)
az
1
,
…
,
h
pontokkal összekötve, és nem
összekötve a
h
+
1
,
…
,
n
−
1
pontokkal. Vegyük a
G
-nek a
G
∗
és
G
∗
∗
részgráfjait, melyeket az
{
1
,
…
,
h
}
ill. a
{
h
+
1
,
…
,
n
−
1
}
pontok feszítenek. Jelöljük
E
0
∗
, ill.
E
0
∗
∗
-gal, stb az
E
0
halmazt, stb.
G
∗
-ra ill.
G
∗
∗
-ra vonatkozóan. Ekkor egy
G
-beli független halmaz vagy a
G
∗
egy független halmaza, vagy
n
-ből és egy
G
∗
∗
-ból való független halmazból tevődik
össze. Ebből
G
∗
minden részhalmaza, mely legalább egy
élt kifeszít,
G
-nek is egy ilyen halmaza; és ha
X
a
G
∗
∗
-nak egy ilyen részhalmaza, akkor
X
∪
{
n
}
a
G
-nek egy ilyen részhalmaza. De most
G
-nek lehet más olyan részhalmaza is,
mely legfeljebb egy élt feszít ki, például az
{
1
,
n
}
élt. Így csak azt tudjuk, hogy
Az indukciós feltevés szerint,
és hasonló egyenlőtlenségek teljesülnek
G
∗
∗
-ra. Így (6)-ból és (7)-ből következik
(4) és (5).
Az alsó becslés (5)-ből következik, teljesen
hasonlóan, mint a felső becslés következett (4)-ből, és
a következő lesz az alakja:
[A. Rényi, J. Math. Pures Appl. 37 (1958)
393–398].
- 13. feladat F Ö
Ismét feltehetjük, hogy
valamely
K
⊆
{
1
,
…
,
n
}
részhalmazra. Ha
K
=
∅
, akkor mindkét oldal 1 lesz, így
feltehetjük, hogy
K
≠
∅
. Ekkor azt kell megmutatnunk, hogy
Legyen
x
a
K
legnagyobb eleme. Az (8) összegben
azok a
(
−
1
)
|
I
|
,
(
−
1
)
|
J
|
tagok párokba állíthatók, ahol
J
=
I
∪
{
x
}
(
x
∉
I
), és ezek nyilvánvalóan kinullázzák
egymást. Ha
J
∈
I
és
x
∈
J
, akkor nyilvánvalóan
J
−
{
x
}
∈
I
. Így (8)-ban csak azok a
(
−
1
)
|
I
|
tagok maradnak meg, ahol
x
∉
I
és
I
∪
{
x
}
∉
I
. Megmutatjuk, hogy az összes ilyen
tag pozitív. Valóban,
I
∪
{
x
}
∉
I
azt jelenti, hogy
valamely
k
-ra; mivel
I
∈
I
, teljesülnie kell az
egyenlőtlenségnek, ahol
k
≥
x
és
De
I
⊆
K
⊆
{
1
,
…
,
x
}
⊆
{
1
,
…
,
k
}
, és így
azaz
(
−
1
)
|
I
|
=
(
−
1
)
2
f
(
k
)
=
1
, mint állítottuk.
Az alsó becslés a következő: legyen
ekkor
[A szita-módszerek egy számelméleti
szempontból vett áttekintése megtalálható a következő
könyvben: H. Halberstam–K. F. Roth,
Sequences, Clarendon Press, Oxford, 1966.]
- 14. feladat F Ö
(a) 2.6 szerint feltehetjük, hogy
Ha
k
=
0
, akkor
P
(
A
I
∪
J
)
=
0
, kivéve, amikor
I
=
J
=
∅
, és akkor azt kell, megmutatnunk,
hogy
ami világos. Ha
k
>
0
, akkor be kell látnunk, hogy
ami szintén világos.
λ
I
=
(
−
1
)
|
I
|
esetén a jobb oldal éppen a
szita-formulával egyezik meg, így egyenlőség
teljesül.
(b) Az ötlettárban megadott alsó becslés
bizonyításához ismét feltehetjük, hogy
(mivel ebben a formulában számít az indexek
sorrendje, most nem tehetjük fel, hogy a
K
halmaz
{
1
,
…
,
k
}
) alakú). A reláció triviális, ha
K
=
∅
(
1
≥
1
), így tegyük fel, hogy
K
≠
∅
. Ekkor meg kell mutatnunk, hogy
Legyen
ekkor ez az egyenlőtlenség úgy írható fel,
hogy
ami nyilvánvalóan igaz.
- 15. feladat F Ö
Tudjuk, hogy
mert
és
Így
ahol
Itt
λ
I
-t kifejezhetjük úgy, mint
mert a
μ
K
-k nyilvánvalóan meghatározzák a
λ
I
-ket és a (11) által definiált
λ
I
-k kielégítik (10)-et:
Így minimalizálnunk kell a
összeget, feltéve, hogy
Ez megtehető vagy a Lagrange módszerrel,
vagy egyszerűen az alábbi transzformáció
alkalmazásával:
ahol
ami teljesül a (13) feltevése mellett. Mivel
a változóknak egy olyan választása, mely
minimalizálja (14) jobb oldalát, és ugyanakkor
kielégíti a (13) feltételt, azt kapjuk, hogy a (12)
minimuma
1
∕
Q
és (15) adja a szélsőértéket. Ebből
- 16. feladat F Ö
2.14 szerint,
λ
I
(
I
⊆
{
1
,
…
,
n
}
)
tetszőleges választása mellett, azzal
az egyetlen megszorítással, hogy
λ
∅
=
1
. Csak azokat a
λ
I
-kat fogjuk használni, melyek
kielégítik a
λ
I
=
0
követelményt
I
∉
H
esetén. Legyen
Azt kapjuk, hogy
Mint az előző megoldásban, a
választás minimalizálja az első tagot, és
értéle
1
∕
Q
, ahol
Most (16)-ban a második tagot becsüljük meg,
amikor
λ
I
-t (17)-ből kapjuk. Ekkor
mert
L
∪
I
∈
H
-ből következik
L
∈
H
. Így
Az első tag a következőképpen becsülhető:
Ha kiszorozzuk a formulát, pontosan azokat a
p
1
l
1
…
p
n
l
n
tagokat kapjuk, melyekre
∏
l
i
>
0
p
i
≥
1
M
; így biztosan megkapjuk ezen formula
azon tagjait, melyek önmagukban legalább
1
M
nagyságúak. Így
és az állítás következik.
- 17. feladat F Ö
Legyen
P
1
,
…
,
P
n
,
M
az ötlettárban megadott módon
definiálva. Válasszunk az
l
,
k
+
l
,
…
,
(
x
−
1
)
k
+
l
számok közül véletlenszerűen egyet és
legyen
A
i
az az esemény, hogy ez osztható
P
i
-vel. Legyen
x
⋅
P
(
A
I
)
a
P
I
többszöröseinek száma az
l
,
k
+
l
,
…
,
(
x
−
1
)
k
+
l
számok között. Mivel
(
P
I
,
k
)
=
1
, ezért
P
I
-nek csak egy többszöröse van a
μ
P
I
⋅
k
+
l
,
(
μ
P
I
+
1
)
k
+
l
,
…
,
(
μ
P
I
+
P
I
−
1
)
k
+
l
számok között minden
0
≤
μ
≤
x
P
I
−
1
-re. Ebből
és így
Ezért a
p
i
=
1
P
i
,
ɛ
=
1
x
értékkel, 2.16 feltételei teljesülnek,
és ebből
Itt
ahol az összegezés kiterjed az
l
1
,
…
,
l
n
≥
0
összes olyan választására, melyre
P
1
l
1
…
P
n
l
n
≤
M
teljesül. Ez az összeg pontosan
Hogy egy alsó korlátot is kapjunk, vegyük
észre, hogy
ahonnan
Másrészről ismeretes, hogy
és így
ha
x
elég nagy. Így az
l
,
k
+
l
,
…
,
(
x
−
1
)
k
+
l
sorozatbeli prímek száma legfeljebb
ha
x
elég nagy.
- 18. feladat F Ö
Bebizonyítjuk, hogy
n
szerinti indukcióval. Ez maga után
vonja, hogy
mert az indukciós feltevés szerint
P
(
A
¯
2
…
A
¯
n
)
>
0
(ez azt is garantálja, hogy a
P
(
A
1
|
A
¯
2
…
A
¯
n
)
feltételes valószínűség
értelmes).
Legyenek mondjuk a
2
,
…
,
h
csúcsok az 1 szomszédai. Ekkor
Itt a számláló
(mivel
A
1
független
A
¯
h
+
1
,
…
A
¯
n
)-től), míg a nevezőre azt kapjuk,
hogy
Most az
{
i
,
h
+
1
,
…
,
n
}
által feszített részgráfra alkalmazva
az indukciós feltevésünket, kapjuk, hogy
és így
mivel az
1
csúcs foka
h
−
1
≥
d
. Így
[P. Erdős–L. Lovász, in: Infinite and Finite
Sets, Coll. Math. Soc. J. Bolyai 10 (1974) Bolyai–North
Holland, 609–627.]
- 19. feladat F Ö
Tudjuk, hogy
Legyen
ekkor
és így
ahonnan
Megjegyezzük, hogy az első lépés a
Csebisev-egyenlőtlenség:
- 20. feladat F Ö
I. 2.9 szerint,
II. A Selberg-módszerből kapjuk, hogy
ahol
λ
∅
=
1
,
λ
{
i
}
tetszőleges. 2.15 szerint, a
λ
I
-ket választhatjuk úgy, hogy a jobb
oldal a következő alakú legyen:
III. Az előző feladatbeli formula adja, hogy
Nyilvánvalóan
γ
≥
β
, így II jobb, mint III. Azonban, I és
II összehasonlíthatatlanok. Mert legyen
p
rögzített, és
n
→
∞
, akkor
β
→
0
, de
α
→
∞
, így II jobb I-nél, ha
n
nagy. Másrészt legyen
n
fix és
p
→
0
, ekkor a
β
hatványsora
alakú lesz, amely nagyobb, mint
α
, ha
p
nagyon kicsi.
- 21. feladat F Ö
Triviális, hogy kompatibilis mátrixok szorzata
kompatibilis. Legyen
A
=
(
a
i
j
)
,
B
=
(
b
i
j
)
két kompatibilis mátrix,
A
B
=
C
=
(
c
i
j
)
és tegyük fel, hogy
c
i
j
≠
0
. Mivel
létezik egy olyan
k
, melyre
a
i
k
≠
0
és
b
k
j
≠
0
. Ebből következik, hogy
x
i
≤
x
k
és
x
k
≤
x
j
, és így a tranzitivitásból
következik, hogy
x
i
≤
x
j
. Így
C
is kompatibilis.
Legyen
A
egy invertálható kompatibilis mátrix.
Az általánosság megszorítása nélkül feltehetjük, hogy
x
i
≤
x
j
⇒
i
≤
j
(ezt megfelelő indexezéssel
elérhetjük). Ekkor látható, hogy az
A
minden nemnulla eleme az átló felett
van, így
det
A
=
∏
i
=
1
n
a
i
i
. Így
a
i
i
≠
0
. Most legyen
B
=
(
b
i
j
)
az
A
inverze, és tegyük fel indirekte, hogy
nem kompatibilis, azaz létezik olyan
x
i
≰
x
j
melyre
b
i
j
≠
0
. Válasszuk itt
i
értékét maximálisnak. Kapjuk, hogy
de
így kell, hogy legyen egy
k
≠
i
, melyre
Mivel
(
a
i
j
)
kompatibilis, ebből következik, hogy
x
i
≤
x
k
és így,
i
<
k
. Az
i
választása miatt,
b
k
j
≠
0
-ből következik, hogy
x
k
≤
x
j
, és így
x
i
≤
x
j
, ami ellentmondás.
[Ez, és a legtöbb probléma e fejezet hátralevő
részében G. C. Rota cikkén alapul: Zeitschr.
f. Wahrscheinlichkeitstheorie, 2 (1964)
340–368.]
- 22. feladat F Ö
Definiáljuk az alábbi
Z
=
(
z
i
j
)
mátrixot:
A
μ
-re tett két utolsó követelmény úgy is
felírható, mint
ahol
M
=
(
m
i
j
)
,
m
i
j
=
μ
(
x
i
,
x
j
)
, és
I
az identitás mátrix. Mivel
z
i
i
≠
0
,
Z
invertálható (lásd az előző
megoldást), és így az előző eredmény szerint,
M
=
Z
−
1
egy kompatibilis mátrix. Ez éppen a
kívánt
μ
(
x
,
y
)
függvényt definiálja.
- 23. feladat F Ö
Vegyük észre, hogy ha ismerjük
μ
(
a
,
y
)
értékét minden olyan
y
-ra, melyre
a
≤
y
<
b
teljesül, akkor a
egyenlet egyértelműen meghatározza
μ
(
a
,
b
)
-t. Ezért
μ
(
a
,
x
)
értékét minden
a
≤
x
≤
b
-re meghatározhatjuk indukcióval úgy,
hogy csak
a
és
b
közti elemeket használunk. Ebből, ha
a
≤
b
∈
V
,
a
′
≤
b
′
∈
V
′
és a
{
z
∈
V
:
a
≤
z
≤
b
}
és
{
z
′
∈
V
′
:
a
′
≤
z
′
≤
b
′
}
halmazok, mint részben rendezett
halmazok, izomorfak, akkor
(a) Azt állítjuk, hogy
μ
(
X
,
Y
)
=
(
−
1
)
|
Y
−
X
|
(
X
⊆
Y
⊆
S
). Valóban,
(b) Itt minden
a
≤
z
≤
b
intervallum lánc. Így elegendő
μ
(
a
1
,
a
n
)
-t kiszámítani egy
a
1
<
a
2
<
…
<
a
n
láncra. A definícióból következik,
hogy
Továbbá
és ebből
Mármost
i
≥
3
esetén
és ebből nyilvánvalóan
Így
(c) Azt állítjuk, hogy
ahol
μ
(
k
)
a (számelméleti) Möbius függvény: ha
k
=
p
1
α
1
…
p
r
α
r
(ahol
p
1
,
…
,
p
r
különböző prímek), akkor
Nyilvánvalóan, az (19) által definiált
μ
(
x
,
y
)
-ra teljesül, hogy
μ
(
a
,
a
)
=
1
. Továbbá, ha
a
≠
b
és
a
|
b
, akkor
Legyen
akkor
- 24. feladat F Ö
Meg kell mutatnunk, hogy
azaz
Az első állítás triviális. A második állítás
bizonyításához vegyük észre, hogy az
M
-et és
Z
-t használva, az állítás kifejezhető
úgy, hogy
ami nyilvánvaló, hiszen
M
=
Z
−
1
.
- 25. feladat F Ö
Legyen
Z
−
I
=
(
u
i
j
)
, akkor
Ekkor az
(
i
,
j
)
-ik elem a
(
Z
−
I
)
n
mátrixban
mert egy nemnulla tag egy
x
i
<
x
k
1
<
x
k
2
<
…
<
x
k
n
−
1
<
x
j
láncnak felelne meg, ami nyilvánvalóan
nem létezik. Ebből
vagy ami ezzel ekvivalens,
M
-mel szorozva, kapjuk, hogy
Vegyük észre, hogy
n
helyett tekinthettük volna a
V
-beli láncok hosszúságának
maximumát.
- 26. feladat F Ö
Az
f
=
(
f
(
x
1
)
,
…
,
f
(
x
n
)
)
,
g
=
(
g
(
x
1
)
,
…
,
g
(
x
n
)
)
jelöléssel
g
definíciója azt jelenti, hogy
az állítás pedig azt, hogy
Hogy megkapjuk a szitaformulát, álljon
V
az
{
1
,
…
,
n
}
összes részhalmazából és a
≤
reláció jelentse a tartalmazást. 2.23
szerint,
μ
(
K
,
L
)
=
(
−
1
)
|
L
−
K
|
(
K
⊆
L
). Legyen
ekkor
és így,
- 27. feladat F Ö
(a) Az
a
és
b
közti elemek száma szerinti indukciót
végzünk. Ha
a
=
b
, akkor az összeg ilyen alakú lesz:
ami
μ
definíciója szerint 0 (mivel
b
≠
0
). Legyen
b
>
a
. Ekkor
A bal oldal a
μ
definíciója miatt 0. A jobb oldalon
minden olyan tag 0, ahol
b
1
<
b
az indukciós feltevés szerint. Így az
utolsó tagnak is 0-nak kell lennie.
(b) azonnal következik (a)-ból, ha mint 2.24-ben
megfordítjuk a rendezést.
- 28. feladat F Ö
Az
x
alatti elemek száma szerinti indukciót
végzünk. Ha
x
=
0
, az állítás igaz (0 az atomok egy
üres halmazának az uniója). Legyen
x
>
0
. Ha
a
≤
x
egy atom, akkor az előző eredményből
következik, hogy
Nyilvánvaló, hogy itt egyik
y
sem lehet atomok uniója. Így minden
olyan tag, ahol
y
<
x
, az indukciós feltevés szerint 0.
Ezért az is következik, hogy
μ
(
0
,
x
)
is 0 lesz.
- 29. feladat F Ö
Tudjuk, hogy
így
Másrészt,
Itt
és hasonlóan,
Ebből (22) ilyen alakú lesz:
ami az állítást bizonyítja.
- 30. feladat F Ö
(a) Legyen
b
=
{
1
}
,
{
2
,
…
,
n
}
. 2.27-t alkalmazva:
vagy, ami ezzel ekvivalens,
Határozzuk meg azokat az
x
partíciókat, melyekre
x
∧
b
=
0
,
x
≠
0
. Legyen
x
=
{
A
1
,
…
,
A
p
}
egy ilyen partíció. Legyen mondjuk
1
∈
A
1
. Ekkor
i
>
1
esetén
A
i
=
A
i
∩
{
2
,
…
,
n
}
az
x
∧
b
=
0
egy osztálya, ebből
|
A
i
|
=
1
. Mivel
x
≠
0
,
|
A
1
|
≥
2
. De
A
1
∩
{
2
,
…
,
n
}
szintén az
x
∧
b
=
0
-nak egy osztálya, így
|
A
1
|
=
2
. Így
x
a következő alakú
A
{
z
:
x
≤
z
≤
1
}
intervallum az összes olyan
partícióból áll, mely az 1-et és az
i
-t nem választja el. Ez az intervallum
nyilvánvalóan izomorf az
n
−
1
elem összes partíciójának a hálójával
(1 és
i
"össze vannak ragasztva"). Ebből
az indukciós feltevés szerint. Mivel
n
−
1
partíciót kell tekintetbe vennünk,
(23)-ból következik, hogy
[M. P. Schützenberger].
(b) Minden
x
lapra, a
[
0
,
x
]
intervallum egy konvex politóp
(nevezetesen
x
) összes lapjának a hálója. Ebből
indukcióval feltehetjük, hogy
teljesül minden
x
lapra, kivéve az
1
-et. Így a
μ
definíciója szerint,
Az Euler-formula szerint, ez éppen
(
−
1
)
d
+
1
.
- 31. feladat F Ö
Ha
F
úgy van definiálva, ahogy az
ötlettárban tettük, akkor tudjuk, hogy
Valóban,
Ebből
Ha
V
csak egy részben rendezett halmaz,
akkor
F
-et úgy definiáljuk, mint korábban, és
tekintsük a következő egyenletet:
Innen azt kapjuk, mint korábban, hogy
Ezt nem írhatjuk fel
x
i
∧
x
j
függvényeként (hiszen ez nincs
definiálva), így a kifejezést a következőképpen kell
felírnunk: legyen
f
(
x
)
egy tetszőleges függvény a
V
-n és legyen
Ekkor
Vegyük észre, hogy ha
V
tetszőleges két
x
i
,
x
j
elemének van egy legnagyobb
x
i
∧
x
j
alsó korlátja, akkor
ahol
[H. S. Wilf, Bull. Amer. Math. Soc. 74
(1968) 960–964].
- 32. feladat F Ö
I. Legyen
V
=
{
1
,
…
,
n
}
, legyen a részben rendezés az
oszthatósággal definiálva, és
g
(
x
)
=
x
. Megpróbáljuk az előző formulát
alkalmazni (
V
ugyan nem egy háló, de zárt az
x
∧
y
=
(
x
,
y
)
operációra nézve, és így ugyanaz a
formula teljesül, az előző feladat végén tett
megjegyzés szerint). Hogy egy alkalmas
f
(
x
)
-et kapjunk, 2.26-ot használjuk fel:
a 2.3 megoldása szerint. Így a determináns
értéke
ϕ
(
1
)
⋅
ϕ
(
2
)
…
ϕ
(
n
)
lesz.
II. Ez a determináns éppen
ϕ
(
1
)
…
ϕ
(
n
)
×
{
bal felső elem
G
−
1
-ben
}
ahol, mint az előző megoldásban,
Így
ahol
M
=
(
m
i
j
)
,
Így
G
−
1
-nek a bal felső sarokbeli eleme
Ebből
- 33. feladat F Ö
Legyen
Tekintsük
x
1
-et, mint gyökeret, ekkor
T
tekinthető egy fenyőnek, és ez a
V
=
V
(
T
)
-nek egy rendezését adja meg:
x
i
≤
x
j
, ha az (egyértelmű)
(
x
1
,
x
j
)
-út tartalmazza
x
i
-t. Legyen
Z
, mint 2.22-ben; állítjuk, hogy
Valóban, a
Z
T
A
Z
(
i
,
j
)
-ik eleme
Mármost
a
k
l
csak akkor nem nulla, ha
k
=
l
, vagy
k
=
1
, vagy
l
=
1
; így azt kapjuk, hogy
ahol
x
i
∧
x
j
az
(
x
1
,
x
i
)
és
(
x
1
,
x
j
)
-utak utolsó közös pontja. Ebből
mint állítottuk. Így
[R. L. Graham–H. O. Pollak, Bell Sys. Tech.
J. 50 (1971) 2495–2519].
- 34. feladat F Ö
Legyen
U
=
Z
−
I
=
(
u
i
j
)
. Ekkor
U
n
=
0
. Továbbá kapjuk, hogy
Így
Ebből
ahol
p
v
′
az
U
v
(
x
,
y
)
-ik eleme; de másrészt ez az elem
- 35. feladat F Ö
Legyen
Ekkor
Legyen
a
1
,
…
,
a
m
az összes
y
-nál nem nagyobb atom. Ekkor a
∑
x
≤
y
q
k
(
x
)
megszámolja az összes
k
-ast az
{
a
1
,
…
,
a
m
}
halmazból. Ezért
és így
A 2.26-beli Möbius-féle inverziós formula
szerint kapjuk, hogy
- 36. feladat F Ö
L
-ben háromféle típusú elemek
vannak:
(a)
C
elemei,
(b) elemek, melyekhez van egy olyan
y
∈
C
, melyre
x
<
y
,
(c) elemek, melyekhez van egy olyan
y
∈
C
, melyre
x
>
y
. (a), (b) és (c) osztályozzák az
elemeket; valóban nem létezik olyan
x
, melyre ezen tulajdonságok közül
kettő teljesül, mert ez
C
-nek két összehasonlítható elemét
adná. Ugyanakkor, ha
x
az (a), (b), (c) tulajdonságok közül
egyikkel sem rendelkezne, akkor egyetlen
x
-et tartalmazó maximális lánc sem
metszené
C
-t.
Írjunk
x
<
C
és
x
>
C
-t, ha (b) ill. (c) teljesül.
Tekintsük azon
k
-asok
q
k
(
a
,
b
)
számát
C
-ben, melyek uniója
b
és metszete
a
, és legyen
a
<
C
<
b
. Ekkor bebizonyítjuk, hogy
az
a
és
b
közti elemek száma szerinti
indukcióval. Legyenek
a
1
,
…
,
a
m
azon elemek a
C
-ben, melyek az
a
és
b
között vannak. Feltehetjük, hogy
a
=
0
és
b
=
1
, mert
{
a
1
,
…
,
a
m
}
a
{
z
:
a
≤
z
≤
b
}
részhálóban egy ugyanolyan
tulajdonságokkal rendelkező halmazt alkot, mint
C
. Kapjuk, hogy
és így
2.29 szerint,
μ
kielégíti ugyanezt az azonosságot:
(24)-ben és (25)-ben
q
(
x
,
y
)
=
μ
(
x
,
y
)
teljesül az indukciós feltevés
alapján, ha
x
≠
0
, vagy
y
≠
1
. Így azt kapjuk, hogy
- 37. feladat F Ö
Ha
a
egy tetszőleges atom, akkor
2.27 szerint. Mivel
a
fedi a 0-t, vagy
x
=
1
, vagy
a
∨
x
=
1
fedi
x
-et, így
x
koatom kell, hogy legyen.
Ha
r
szerinti indukciót végzünk,
feltehetjük, hogy
μ
(
0
,
x
)
előjele
(
−
1
)
r
−
1
(a
0
≤
z
≤
x
intervallum rangja
r
−
1
, mivel tetszőleges, maximális
(
0
,
x
)
-lánc, az 1-gyel kiegészítve, egy
maximális
(
0
,
1
)
-láncot alkot). Így a
összefüggésből következik az állítás.