- 1. feladat F M
Két permutáció akkor és csak akkor egymás
konjugáltja, ha a ciklusaik méretei megegyeznek.
- 2. feladat F M
(a) Használjunk szitálást. (b) Egy ilyen
permutációt egy adott pontból kiindulva építsünk
fel.
- 3. feladat F M
Számoljuk le azokat a permutációkat, melyekben az
1-et tartalmazó ciklus elemeinek a halmaza
adott.
- 4. feladat F M
Az előzőhöz hasonló leszámlálást
végezzünk.
- 5. feladat F M
Határozzuk meg
k
hosszúságú ciklusokban lévő pontok
számának várható értékét.
- 6. feladat F M
Használjuk a 3.3 második megoldásában mutatott
kódolást.
- 7. feladat F M
Bizonyítsuk be az alábbi rekurzív relációt
- 8. feladat F M
b)-hez, reprezentáljuk ezeket a permutációkat az
osztályok halmazának egy permutációjával, és
k
darab további permutációval, melyek
egy-egy osztály elemeit permutálják.
- 9. feladat F M
Ha a két csoport megfelelő elemeinek a rendje
egyenlő, akkor a reguláris reprezentációjuknak ugyanaz
a ciklusszámlálója.
- 10. feladat F M
Vegyük észre az alábbi azonosságot
- 11. feladat F M
Tekintsük a
kifejezést.
- 12. feladat F M
(a) A bal oldalt
f
n
(
x
)
-szel jelölve, vegyük észre, hogy
f
n
(
x
)
=
n
!
p
n
(
x
,
…
,
x
)
, ahol
p
n
(
x
1
,
…
,
x
n
)
az
S
n
ciklusszámlálója. (b) Számítsuk ki
f
n
′
(
1
)
-t.
- 13. feladat F M
Egy ilyen gráf diszjunkt körökből áll. Ha
irányítjuk ezeket, az
n
elem egy permutációja
ciklusfelbontásának a gráfját kapjuk.
- 14. feladat F M
(a) Kössük össze az egy párban lévő számokat egy
éllel. (b) Hányféleképpen irányíthatjuk az előző gráf
éleit?
- 15. feladat F M
Fejezzük ki ezeket a számokat, mint a
ciklusszámláló bizonyos értékeit.
- 16. feladat F M
A
π
¯
(
1
)
,
…
,
π
¯
(
n
)
sorozat egyértelműen meghatározza a
π
permutációt.
- 17. feladat F M
Ha az
i
-edikként ugró versenyző ugrása a
π
(
i
)
-ik leghosszabb ugrás, akkor a
π
az
{
1
,
…
,
n
}
egy véletlen permutációja. Az
i
-ik ugrás akkor és csak akkor rekord,
ha
π
¯
(
i
)
=
i
.
- 18. feladat F M
Vegyük észre, hogy az optimális stratégia
független az első
k
ugrás sorrendjétől. Határozzuk meg a
p
n
−
1
,
p
n
−
2
,
…
számokat, ebben a sorrendben.
- 19. feladat F M
Ez azzal ekvivalens, hogy
π
¯
(
j
+
1
)
≥
π
¯
(
j
)
.
- 20. feladat F M
A
π
permutáció inverzióinak a száma
- 21. feladat F M
Tegyük fel, hogy egy nagy tartalékkal indulunk,
és akkor használjuk, ha kifogy a benzinünk. Tekintsük
azt a pontot, ahol a szükséges tartalék
maximális.
- 22. feladat F M
(a) Nevezzünk egy különböző egészekből álló,
j
i
(
1
≤
j
i
≤
n
),
(
j
1
,
…
,
j
s
)
sorozatot felszállónak, ha
(i)
x
j
1
+
…
+
x
j
s
>
0
, de
(ii)
x
j
1
+
…
+
x
j
ν
≤
0
ha
1
≤
ν
<
s
.
(
s
=
1
esetén az egyelemű
(
j
1
)
sorozat akkor és csak akkor felszálló,
ha
x
j
1
>
0
.) Nevezzünk egy sorozatot
leszállónak, ha
(i')
x
j
1
+
…
+
x
j
s
≤
0
, de
(ii')
x
j
ν
+
…
+
x
j
s
>
0
1
<
ν
≤
s
esetén.
(Vegyük észre, hogy a két definíció nem teljesen
analóg.) Tekintsük az
{
1
,
…
,
n
}
partícióit otl- és leszálló
sorozatokra, és építsük fel a
π
permutációkat belőlük, melyekre az
a
(
π
)
, ill.
b
(
π
)
, könnyen meghatározható (lásd még
3.21-et is).
(b) Vegyük az
n
=
2
m
,
x
1
=
…
=
x
m
=
1
és
x
m
+
1
=
…
=
x
2
m
=
−
1
értékeket (a)-ban.
- 23. feladat F M
(a) Keressük meg azon
k
-szögek számát, melyek invariánsak egy
adott forgatásra nézve. (b) Használjunk hasonló
módszert.
- 24. feladat F M
Számoljuk meg
Γ
azon elemeit, melyek egy adott pontot
fixen hagynak.
- 25. feladat F M
Ez a 3.24-nek csak egy enyhe
általánosítása.
- 26. feladat F M
Azon permutációcsoport pályáinak a számát akarjuk
meghatározni, melyet
Γ
a
D
-nek
R
-be való leképezéseinek
Ω
halmazán indukál.
- 27. feladat F M
Először találjunk egy
F
-re vonatkozó formulát; aztán
használjuk, hogy
- 28. feladat F M
Használjunk az előzőhöz hasonló módszert; egy
kölcsönösen egyértelmű leképezés, mely a
(
π
,
ϱ
)
-nak fixpontja, szükségszerűen a
π
egy ciklusát a
ϱ
egy ugyanolyan hosszúságú ciklusára
kell, hogy leképezze.
- 29. feladat F M
Először a (
∗
)-ot kielégítő, és egy adott
γ
∈
Γ
által invariánsan maradó
f
leképezések
q
n
(
γ
)
számának a generátorfüggvényét
határozzuk meg.
- 30. feladat F M
Ha
D
a forintok halmaza,
R
a személyek halmaza, és
Γ
a
D
-n ható szimmetrikus csoport, akkor
3.26 adja meg a választ.
- 31. feladat F M
Legyen
|
D
|
=
n
,
|
R
|
=
N
≥
n
,
Γ
=
{
1
}
és
Γ
1
=
S
N
3.27-ben; és
N
→
∞
.