Kombinatorika.pdf

(302 KB) Pobierz
Hetyei Gábor – Kiss Péter :
KOMBINATORIKA és GRÁFELMÉLET
Bevezetés
A kombinatorika véges halmazokkal foglalkozó ága a matematikának. A legközismertebb
kombinatorikai problémák különböző játékokkal kapcsolatosak (kártyajátékok, TOTÓ,
LOTTÓ, sakk, stb.), de ezek a kombinatorikának csak speciális területei. A kombinatorika
általában a véges halmazok leképzéseivel, adott tulajdonságú részhalmazaival, illetve,
részrendszereivel, továbbá számossági, kiválasztási, leszámlálási és még sok más
problémával foglalkozik.
A gráfelmélet a kombinatorika és a topológia határterülete, problémaköre és módszerei
hasonlóak mint a kombinatorikának. Sok esetben használunk fel gráfelméleti eredményeket
kombinatorikai problémák megoldására és viszont.
A XX. században e két tudományág felvirágzásának korát éljük, alkalmazási területük is
egyre bővül, egyre szorosabbá válik kapcsolatuk a dinamikusan fejlődő számítástudo­
mánnyal is és az ezzel szoros kapcsolatban álló algoritmuselmélettel.
Az intenzív továbbképzés keretein belül egyrészt a kombinatorika és gráfelmélet alapvető
fogalmainak megismerése illetve felelevenítése a célunk, másrészt betekintést szeretnénk
nyújtani a két tudományág jellegzetes problémaköreibe és eredményeibe. Reméljük, hogy
ez a segédanyag a tanfolyamon elhangzottakkal együtt használható lesz az iskolai
tananyagban vagy szakkörökön felmerülő problémák megoldásában és feladatsorok
összeállításában. Bízunk abban, hogy ezen anyag ismerete hozzájárul az oktatómunka
színvonalának emeléséhez.
Az anyagunk bizonyos fokig támaszkodik a Tanárképző Főiskolán tanult anyagra, így
ismertnek vesszük az alapvető halmazelméleti jelöléseket, a klasszikus kombinatorikai
eredményeket, illetve ezek bizonyításait. Nem térünk ki például a binomiális tételre, a
binomiális együtthatók tulajdonságaira vagy a Pascal háromszög ismertetésére, hiszen ezek
megtalálhatók Dr. Szendrei János forgalomban lévő „Algebra és Számelmélet” című
főiskolai jegyzetében.
Igyekeztünk úgy összeállítani az anyagot, hogy segítse kialakítani a megfelelő szemlélet­
módot. Az általános tételeket feladatokkal készítettük elő, néhol feladatsorozatokkal
helyettesítettük őket a könnyebb érthetőség kedvéért. Az anyag terjedelemben túlmegy a
továbbképzés alatt 8 órában feldolgozhatón, de így egyrészt mód van a résztvevők
előképzettségének megfelelő szelektálására, másrészt a tárgy iránt érdeklődők a tanfolyam
keretein túlmenő ismereteket szerezhetnek.
²³
I. KOMBINATORIKA
1. Klasszikus kombinatorikai alapfogalmak
Először a klasszikus kombinatorika néhány alapfogalmával foglalkozunk. Legyen a továb­
biakban
H
egy
n
elemű,
K
pedig egy
k
elemű halmaz
n
≥
k
≥ 1 feltétellel.
K
halmaznak az
N
halmazba való injektív leképzéseit
n
elem
k
tagú
variációinak
nevezzük.
Vagy más megfogalmazásban,
n
különböző elem egy sorrendjét az
n
elem egy
k
tagú
variációjának is szoktuk nevezni. Mint ismert,
n
elem különböző
k
tagú variációinak száma
V
n
=n(n−1)...(
n−k
+1)=
k
n!
.
(n−k )!
Természetesen két variáció nemcsak akkor különbözik egymástól, ha más elemekből áll,
hanem akkor is ha elemeik azonosak és csak a sorrendben különböznek. Például az
1, 2, 3
elemek összes különböző kéttagú variációi: (1,2); (1,3); (2,1); (2,3); (3,1); (3,2).
Ha a
K
halmaznak az
N
halmazba való leképzéséről nem kötjük ki, hogy injektív legyen,
akkor ezt a leképzést az
n
elem egy
k
tagú
ismétléses variációjának
nevezzük (az előző
esetben a variációkat ismétlés nélküli variációknak is szokás nevezni). Az
n
elem
k
tagú
ismétléses variációi ezek szerint olyan
k
tagú sorozatok, melyek tagjai az
N
halmaz nem
feltétlen különböző elemei. Az előző példa
1,2,3
elemeinek 2 tagú ismétléses variációihoz
tehát az ott felsorolt hat számpáron kívül még az (1,1); (2,2); (3,3) párok is hozzátartoznak.
k
n
elem különböző
k
tagú ismétléses variációknak száma
V
n
=n
k
.
Az
N
halmaz egy
k
elemű részhalmazát az
N
halmaz elemeinek egy (ismétlés nélküli)
k
tagú
kombinációjának
nevezzük. Mivel halmazok elemeit általában nem rendezzük sorozatba,
ezért kombináció esetén nem vagyunk tekintettel a sorrendre, két kombinációt azonosnak
tekintünk, ha azok csak az elemek sorrendjében különböznek.
Összehasonlítva a variációkkal: az
1,2,3
elemeknek pl. (1,2) és (2,1) párok különböző 2 tagú
variációi, de azonos kombinációi. Az összes különböző 2 tagú kombináció: (1,
2);
(1,
3);
(2,
3).
Ismert, hogy
n
elem különböző
k
tagú kombinációinak száma
C
k
=
n
n!
n
=
.
k
!⋅
(n−k )!
k
()
Az olyan
k
elemből álló rendszereket, melyek elemei az
N
halmaz nem feltétlen különböző
elemei, de a rendszerek elemeinek a sorrendjére nem vagyunk tekintettel, az
n
elem
k
tagú
ismétléses kombinációinak
nevezzük. A különböző ismétléses kombinációk száma
̄
C
k
=
n+ k
−1
n
k
(
)
.
Az említett négy kombinatorikai alapfogalmat, illetve ezek használatát, az alábbi táblázat
szemlélteti:
n
elemből kiválasztunk
k
darabot
ismétlés
nincs
Sorrend
számít
nem számít
Variáció
V
n
=n(n−1)...(n−k +1)
k
van
Ismétléses variáció
V
n
=n
k
k
Kombináció
C
k
=
n
Ismétléses kombináció
̄
k
C
n
=
n+ k
−1
k
()
n
n!
=
k k
!⋅
(n−k )!
(
)
A következő feladat jól érzékelteti a variációk és a kombinációk közötti különbséget.
I. Feladat.
Egy 20 létszámú osztályban 5 könyvet osztunk ki. Hányféleképpen tehető ez meg, ha
a.) egy tanuló csak egy könyvet kaphat és a könyvek különbözőek
b.) egy tanuló csak egy könyvet kaphat és a könyvek azonosak
c.) egy tanuló több könyvet is kaphat, és a könyvek különbözőek
d.) egy tanuló több könyvet is kaphat, és a könyvek azonosak
Megoldás:
Rakjuk sorba a könyveket és olvassuk fel 5 tanuló nevét. Az első tanuló kapja az
első könyvet, a második a második könyvet, stb.
a.) A feltétel miatt
öt különböző
tanuló nevét kell felolvasnunk és a könyvek különböző­
sége miatt a sorrend is lényeges, ezért az esetek száma
b.) Most felolvasás sorrendje lényegtelen, hiszen a könyvek között nincs különbség, csak az
a lényeg, hogy
melyik öt tanuló
kapja a könyveket. Ezért az esetek száma
20
20⋅19⋅18⋅17⋅16
C
5
=
20
=
=
20
5!⋅15!
1⋅2⋅3⋅4⋅5
5
( )
c.) A kiválasztott öt tanuló között azonosak is szerepelhetnek, mivel egy tanuló több
könyvet is kaphat. A felolvasás sorrendje viszont lényeges a könyvek különbözősége miatt,
ezért az esetek száma
V
̄
5
=20
5
.
20
d.) A feltételek miatt most minden eset a 20 tanuló egy 5 tagú ismétléses kombinációjának
24
̄
5
felel meg, ezért
C
20
=
féleképpen oszthatjuk ki a könyveket.
(
5
)
n=k
esetben a variációkat az
N
halmaz elemeinek
permutációinak
nevezzük. Tehát
n
külön­
böző elem egy sorrendje az
n
elem egy permutációja. Alkalmazva a variációk számára adott
képletet az
n=k
esetben, az
n
elem különböző permutációinak száma
P
n
=n!
.
Gyakran előfordul, hogy olyan rendszer tagjait kell sorozatokba rendeznünk, melynek
azonos, nem megkülönböztethető tagjai is vannak.
II. Feladat
Hány hatjegyű szám írható fel az
1, 1, 1, 2, 2, 3
számjegyekből?
Megoldás:
Itt nyilván a hat elem különböző elrendezéseinek számát kell meghatároznunk.
Úgy is megfogalmazhatjuk a problémánkat, hogy hat hely közül ki kell választanunk
hármat, ahova
1-eseket
írunk, a megmaradó 6 - 3 = 3 hely közül ki kell választani kettőt,
ahova
2-t
kell beírnunk és a megmaradó helyek (egy) közül kell még kiválasztani egyet,
ahova
3-at
írunk. Így a lehetőségek száma
( )( )( )
6
⋅
3
⋅
1
=
6!
.
3 2 1 3!⋅2!⋅1!
Hasonlóan gondolkodva, felhasználva a binomiális együtthatók
()
n
=
n⋅( n−1)...(n−k
+1)
k
!
k
1,
2...
alakját, a következő általános eredményhez jutunk. Ha n elem között egy fajtából
k₁,
egy másik fajtából
k₂,
... darab van
k₁, k₂,
… ≥ 1,
k₁+k₂+...
= n akkor ezeknek
P
k k
=
n
( )
( )
n!
n
⋅
n−k
1
...=
k
1
!⋅k
2
!...
számú különböző sorrendje van. Egy ilyen elrendezést az
n
elem
k
1
k
2
egy
ismétléses permutációjának
szoktuk nevezni.
Kártyákkal, kártyajátékokkal kapcsolatban nagyon sok feladat konstruálható, Ezeknél
fontos, hogy megadjuk a kártyák kiválasztásának módját. Például ha egyszerre veszünk ki
néhány kártyát a csomagból, akkor általában sorrendet nem tudunk megkülönböztetni, tehát
kombinációval állunk szemben. De ha egyesével választjuk ki a kártyákat, akkor a sorrend
is fontos lehet, ezért általában minden kiválasztás egy-egy variáció vagy kombináció,
aszerint, hogy a kihúzás sorrendjére tekintettel vagyunk-e vagy sem. Nézzünk néhány
egyszerű példát a 32 lapos magyar kártya csomaggal kapcsolatban.
III. Feladat.
A csomagból egyszerre kiveszünk tíz lapot. Hányféleképpen lehetséges ez? (
a sorrendre vagyunk tekintettel az egyszerre kiválasztás miatt.)
IV. Feladat.
Pasziánszozáskor a 32 lapot 4 sorba rakjuk. Hányféleképpen alakulhat az első sor? (
mert most lényeges a sorrend).
V. Feladat.
Egy játék (pl. ulti) során valaki egyszerre 10 lapot kap. Hány olyan leosztása van, amikor
nála van a piros hetes? (
( )
32
, mert
10
32!
,
24!
( )
31
, mert egy lapot rögzítettünk.)
9
Néha az úgynevezett komplementer gondolkodással egyszerűbb a feladat megoldása.
VI. Feladat.
32 lap közül hányféleképpen választhatunk ki egyszerre 10 lapot úgy, hogy legyen köztük
piros?
( )( )
32
−
24
féleképpen, mert összesen
10
10
( )
32
10
lehetőségünk van, de ezek közül
( )
esetben
24
10
nincs köztük piros.
Ennél a feladatnál úgy is eredményre jutnánk, ha összeadnánk azoknak az eseteknek a
számát, amelyekben pontosan 1, pontosan 2, ... pontosan 8 piros lap van a kiválasztottak
között, de ez nyilván nehézkesebb mint az előző megoldás.
Egy feladat megoldásához több úton is eljuthatunk. Jellemző erre a következő jól ismert
feladat.
VII. Feladat.
M A T E M A T
A T E M A T I
T E M A T I K
E M A T I K A
Hányféleképpen olvasható le az ábráról a MATEMATIKA szó, ha csak jobbra vagy lefelé
haladunk?
1. Megoldás:
Vegyük sorra, hogy az egyes helyekre hányféleképpen juthatunk el. Az első sor és első
oszlop minden helyére csak egy módon. Minden további helyre a fölötte lévőtől vagy a tőle
balra lévő helyről juthatunk, ezért az odajutások száma e kettőbe jutások számának összege.
Így minden helyre beírható, hogy hányféleképpen juthatunk oda, míg végül eljutunk az
utolsó A betűhöz. (84, a kitöltött ábra voltaképpen a Pascal háromszög egy része.)
2. Megoldás:
Minden kiolvasás során hatszor kell jobbra lépni és háromszor lefelé. Ezért egy kiolvasást a
j, j, j, j, j, j, l, l, l
elemek egy permutációja reprezentálja egyértelműen (j jobbra lépést jelent,
l
pedig lefelé lépést). Tehát a kiolvasások száma annyi, mint az adott elemek permutációi­
nak száma, vagyis
9!
6!3!
3. Megoldás:
Természetesen nem minden feladat oldható meg az alapképletek mechanikus alkalmazásá­
val. Oldjunk meg most egy összetettebb feladatot!
VIII. Feladat.
Hány olyan hárommal osztható hatjegyű szám van. amelyben előfordul a 6-os számjegy?
Megoldás:
A 90 000 ötjegyű szám között minden harmadik, tehát összesen 30 000 osztható hárommal.
Határozzuk meg, ezek között hány olyan szám van, amely
6-ost
nem tartalmaz! Egy ilyen
szám első számjegyét nyolcféle képpen választhatjuk meg, mert
0
és
6
nem választható. A

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin