Cím: Egy hozzárendelési problémáról
Szerző(k):  Ádám András ,  Tusnády Gábor 
Füzet: 1971/november, 97 - 101. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az 1140. sz. gyakorlatban Karcsinak 5 piros, 3 fehér és 2 zöld golyót kellett elhelyeznie két dobozban úgy, hogy az elsőbe 4, a másodikba 6 golyó kerüljön. Amint azt a megoldásban* láttuk, a lehetőségek száma 11. Az 1332. sz. gyakorlat megoldása* szerint 204-féleképpen oszthatunk ki Annus, Bözsi, Cili és Dóra között 8 gyümölcsöt: 1 almát, 2 barackot, 3 körtét és 2 szilvát úgy, hogy mindegyikük 2 darab gyümölcsöt kap. További rokon feladat a következő. A Kovács családban 3 fiú, a Nagy családban 4 fiú, Szabóéknál 5 lány, Tóthéknál 2 lány van. Kérdés, hányféleképpen állíthatjuk párba a gyerekeket úgy, hogy minden párban egy fiú és egy lány álljon, ha csak arra vagyunk tekintettel, hogy az egyes párokban melyik családok gyerekei állnak. A lehetséges három párosítás a következő (kezdőbetűkkel jelölve):

1.(K,S),(K,S),(K,S),(N,S),(N,S),(N,T),(N,T)2.(K,S),(K,S),(K,T),(N,S),(N,S),(N,S),(N,T)3.(K,S),(K,T),(K,T),(N,S),(N,S),(N,S),(N,S)



A három feladat közül a másodikat abban az általánosabb megfogalmazásban is vizsgálhatjuk, hogy nem kötjük ki, hogy mindegyik gyerek ugyanannyi gyümölcsöt kapjon. Ekkor ‐ mint a dolgozat végén látni fogjuk ‐ 8000 különböző lehetőség van a kiosztásra (ezek közül nyilván 4 olyan, hogy egyetlen gyerek kapja mind a 8 gyümölcsöt, a többi háromnak semmi sem jut).
 

*
 

A látott feladatok általános megfogalmazása a következő. Adott N golyó, melyek különböző színűek és köztük k-féle szín fordul elő. Az első színből n1, a másodikból n2,..., a k-adikból nk golyó van. (Természetesen n1+n2+...+nk=N.) Adott továbbá l doboz, az elsőbe m1, a másodikba m2,..., az l-edikbe ml golyó fér, ahol m1+m2+...+ml=M≥N. A dobozokat meg tudjuk különböztetni egymástól. Kérdés, hányféleképpen helyezhetjük el a golyókat a dobozokba, ha az azonos színű golyókat nem tudjuk megkülönböztetni. Könnyen látható, hogy ennek a másik két feladat is speciális esete, eltérés csak a megfogalmazásban van. Mindhárom példában M=N, ami az általános esetben is mindig elérhető, ha bevezetünk egy (k+1)-edik, képzeletben létező színt, amelyből (M-N) darab golyó van, és amelyből minden elhelyezésnél minden dobozba kiegészítésül annyit teszünk, hogy az illető doboz megteljen. Ezt az általános feladatot cikkünkben hozzárendelési problémának nevezzük, az elnevezés arra utal, hogy a feladatban szereplő kétféle mennyiségből (golyó és doboz, gyümölcs és gyerek, fiúk és lányok) párokat kell képeznünk, egymáshoz kell rendelnünk őket.
Ez a feladat ilyen általánosan igen nehéz, a lehetőségek száma nem adható meg egyszerű formában, csak nagyon bonyolult, áttekinthetetlen képletek ismeretesek. Itt a feladat két speciális esetéről lesz szó, az elsőben minden mi értéke 1, azaz minden dobozba csak 1 golyó fér, a másodikban minden mi értéke N lesz, vagyis az összes golyó belefér bármelyik dobozba.
A kiindulásul szolgáló három feladat tehát nem tartozik a vizsgálandó esetek körébe, de a második feladat említett átfogalmazása igen.
Ha minden mi értéke 1, akkor célszerű feltenni, hogy M=N. Ekkor a lehetőségek száma csak az n1,n2,...,nk számoktól függ, jelöljük ezt a számot h(n1,n2,...,nk)-val.

1. Tétel
h(n1,n2,...,nk)=(n1+n2+...+nk)!n1!⋅n2!⋅...⋅nk!,
ahol n! az első n természetes szám szorzatát jelöli.
 

Bizonyítás. Állításunkat k szerinti teljes indukcióval bizonyítjuk be. k=1 mellett állításunk nyilvánvaló, hiszen csupa ugyanolyan színű golyót csak egyféleképpen helyezhetünk el a dobozokban.
A k=2 esettel külön foglalkozunk, legyen a golyók színe ‐ mondjuk ‐ piros és fekete, ezek számát (n1 és n2 helyett) jelöljük inkább p-vel és f-fel. Most f szerinti indukciót alkalmazunk. Ha f=1, elegendő a fekete golyó dobozát megválasztani. Mivel (p+1) doboz van, ezek közül egyet (p+1)-féleképpen választhatunk ki, és ezt adja az állítás is:
h(p,1)=p+1=(p+1)!p!⋅1!.
Ha már valamely f-re tudjuk, hogy
h(p,f)=(p+f)!p!⋅f!,
akkor h(p,f+1) értékét a következő módon határozhatjuk meg. Válasszunk ki a (p+f+1) dobozból először egyet, ebbe tegyünk egy fekete golyót, majd a többi (p+f) dobozba helyezzük el a többi golyót minden lehetséges módon. Így összesen (p+f+1)⋅h(p,f) elrendezést adtunk meg, aszerint, hogy melyik dobozzal kezdtük, azonban ezek között azonosak is vannak. Minden egyes elrendezést annyiszor kaptunk meg, ahányféleképpen az először elhelyezett fekete golyó dobozát megválaszthatjuk, azaz (f+1)-féleképpen. Emiatt a kapott szám (f+1)⋅h(p,f+1), és a kettőből
h(p,f+1)=p+f+1f+1⋅h(p,f)=(p+f+1)!p!⋅(f+1)!,
amint azt bizonyítani akartuk, vagyis a k=2 esetben igazoltuk tételünk helyességét.
Tegyük fel, hogy a tétel érvényességét valamely k(≥2) természetes számra már beláttuk; bizonyítsuk azt (k+1)-re. Helyettesítsük átmenetileg az első k színt egy közös színnel, ekkor a golyók elhelyezésére a már elintézett k=2 esetre vonatkozó eredményünk szerint:
h(n1+n2+...+nk,nk+1)=(n1+n2+...+nk+nk+1)!(n1+n2+...+nk)!⋅nk+1!
lehetőségünk van. Minden egyes ilyen elhelyezésnél rögzítsük a (k+1)-edik színű golyók helyzetét, és rendezzük át minden lehetséges módon az első k színű golyókat eredeti színük figyelembevételével. Erre az indukciós feltevés szerint minden egyes esetben
h(n1,n2,...,nk)=(n1+n2+...+nk)!n1!⋅n2!⋅...⋅nk!,
lehetőség van, így mind a (k+1) színt figyelembe véve az összes lehetőség száma e két szám szorzata:
h(n1,n2,...,nk,nk+1)=h(n1+...+nk,nk+1)⋅h(n1,n2,...,nk)==(n1+n2+...+nk+nk+1)!n1!⋅n2!⋅...⋅nk!⋅nk+1!,


amint azt bizonyítani akartuk. Tételünk bizonyítását ezzel befejeztük:
 

Következmények. 1. N különböző elemet N!-féleképpen állíthatunk sorba. Valóban, legyen k=N és n1=n2=...=nN=1, vagyis legyen N különböző színű golyónk; ezeket (az egy sorban elhelyezett dobozokba) h(n1,n2,...,nN)=N!-féleképpen helyezhetjük el.
2. Ha adott k különböző elem, ezekből h(n1,n2,...,nk) különböző N-elemű sorozatot képezhetünk úgy, hogy az első n1-szer, a második n2-ször, ..., a k-adik nk-szor forduljon elő. Az indoklás ismét az, hogy a sorbarakást egyszerűen a dobozokon is elvégezhetjük.
3. N különböző elemből (Nn)-féleképpen választhatunk ki n(≤N) különböző elemet, ha a kiválasztás sorrendjére nem vagyunk tekintettel (ahol az (Nn) binomiális együttható értéke
(Nn)=N!n!(N-n)!,
és az itt esetleg fellépő 0! értéke megállapodásszerűen 1). Legyen ugyanis n piros és (N-n) fekete golyónk, ezek elhelyezése egyértelműen jellemezhető a piros golyók számára kiválasztott dobozokkal. Tehát h(n,N-n) egyenlő azzal, hogy hányféleképpen választhatunk ki az N doboz közül n-et.
4. N különböző elemből N(N-1)(N-2)...(N-k+1)-féleképpen választhatunk ki n különböző elemet, ha a kiválasztás sorrendjére is tekintettel vagyunk. Színezés helyett ugyanis számozzunk most meg az N golyó közül n-et 1-től n-ig, a többi N-n maradjon egyforma. Ha ezeket a golyókat elhelyezzük N dobozban úgy, hogy minden dobozban egy golyó legyen, a golyók elhelyezése alapján sorban kiválaszthatunk n dobozt úgy, hogy ebben a sorban a k-adik (1≦k≤n) az a doboz legyen, amelyikbe a k-val jelzett golyó kerül. Tehát a golyók elhelyezése ekvivalens azzal, hogy az N doboz közül sorban kiválasztunk n-et, vagyis a lehetőségek száma
h(1,1,...,1,N-n)=N(N-n)!=N(N-1)⋅...⋅(N-n+1).
 

*
 

Rátérünk a második eset vizsgálatára, tehát most minden mi értéke N, így természetesen M=l⋅N≥N. Ez azt jelenti, hogy az N golyót (melyek között most is az első színből n1, a másodikból n2,..., a k-adikból nk van, l dobozba helyezzük el úgy, hogy egy-egy dobozba akárhány (akár az összes) golyó kerülhet. A lehetséges elhelyezések száma most az n1,n2,...,nk számokon kívül az l számtól is függ. Jelöljük ezért most az összes hozzárendelési lehetőségek számát Hl(n1,n2,...,nk)-val.
 


2. Tétel
Hl(n1,n2,...,nk)=(n1+l-1)!(n2+l-1)!⋅...⋅(nk+l-1)!n1!⋅n2!⋅...⋅nk!⋅[(l-1)!]k.

Bizonyítás. A különböző színű golyók elhelyezése most független egymástól abban az értelemben, hogy minden egyes színhez tetszőlegesen készíthetjük el a golyók elhelyezését és ezeket az elhelyezéseket egyesíthetjük. Emiatt
Hl(n1,n2,...,nk)=Hl(n1)⋅Hl(n2)⋅...⋅Hl(nk),
elegendő tehát azt bizonyítanunk, hogy
Hl(n)=(n+l-1)!n!⋅(l-1)!,
vagyis elegendő meghatároznunk, hányféleképpen helyezhetünk el n egyforma golyót l dobozban. Állítsuk sorba a golyókat és tegyünk közéjük (l-1) jelet: az első jel előtti golyókat tegyük az első dobozba, az első két jel köztieket tegyük a másodikba és így tovább, végül az utolsó jel utániakat tegyük az l-edik dobozba. (Megengedjük, hogy a sorozat elválasztó jellel kezdődik vagy végződik és azt is, hogy több jel egymás mellé kerüljön. Ennek megfelelően a dobozok némelyike üresen maradhat.) A lehetőségek száma tehát annyi, ahányféleképpen az n golyót és az (l-1) elválasztó jelet sorba rakhatjuk, ami az 1. tétel 2. következménye szerint h(n,l-1). Tehát
Hl(n)=h(n,l-1)=(n+l-1)!n!⋅(l-1)!,
amint azt bizonyítani akartuk. Tételünk bizonyítását ezzel befejeztük.
 

Következmények. 5. l különböző elemből lk-féleképpen választhatunk ki k elemet, ha a kiválasztás sorrendjére is tekintettel vagyunk és egy-egy elemet akárhányszor választhatunk. Legyen ugyanis n1=n2=...=nk=1, és ismét számozzuk meg a golyókat. Ekkor a golyók elhelyezése ekvivalens az 1 dobozból képezhető k-elemű sorozatokkal. (Hiszen egynél több golyó is kerülhet ugyanabba a dobozba, a sorozatban ugyanaz a doboz többször is előfordulhat.) A lehetőségek száma tehát
Hl(1,1,...,1)=(l!(l-1)!)k=lk.

6. l különböző elemből (n+1-1n)-féleképpen választunk ki n elemet, ha a kiválasztás sorrendjére nem vagyunk tekintettel, de az egyes elemeket akárhányszor is megválaszthatjuk. Az elemek ismét a dobozok, ezekből egy-egy n-es csoportot úgy tekinthetünk, hogy miután valahogy elhelyeztünk bennük n egyforma golyót, minden dobozt annyiszor választunk, ahány golyó van benne.
 

*
 

Fő mondanivalónk végére jutottunk; a tanulságok összefoglalásával és a bevezetőül szolgáló példák egyikének újbóli felvillantásával zárjuk fejtegetéseinket. Legfontosabb tanulságunk nem a két tételben közölt (első látásra elég bonyolultnak tűnő) két képlet, azokat aligha érdemes megjegyezni. A következményekben található eredmények már érdekesebbek, de ezek előállítása sem volt a cikk igazi célja; azokban úgyis rendre felismerhetőek a IV. osztályban sorra kerülő kombinatorikai alapfeladatok (úgymint a permutációk, kombinációk és variációk számának meghatározása), elég lesz akkor megtanulni őket.
Az említett alapfeladatokat általában a kombinatorika építőköveinek tekintik, és a nehezebb problémák megoldását ezekre mint legegyszerűbbekre igyekeznek visszavezetni. Talán meglepő, hogy a permutációk, kombinációk, variációk számának meghatárokása nálunk a két tétel következményeként adódik; anélkül számoltuk meg a lehetőségeket a két fő feladatban, hogy ezeknek az ,,elemi'' feladatoknak a megoldását ismertnek feltételeztük volna. A dolgozatban elsősorban a leszámlálások módszereit kívántuk bemutatni. Ezekkel a módszerekkel számos kombinatorikai feladatot tudunk megoldani, gyakran anélkül, hogy bármiféle kész képletet használnánk.
A nyert eredményeknek megvannak a maguk érvényességi határai. A kiindulásul szolgáló három példa nem oldható meg általános képleteinkkel; e példák megoldása a lehetőségek közvetlen összeszámolását igényli, mert megfelelő képlet, amelyet alkalmazhatnánk, nem is létezik.
A második példának a bevezetés végén szereplő átfogalmazására viszont jól alkalmazható a 2. tételünk. Valóban, l=4 (a gyerekek száma), k ugyancsak 4 (a gyümölcsfélék száma), és n1=1, n2=2, n3=3, n4=2. A 2. tétel szerint a lehetőségek száma
4!⋅5!⋅6!⋅5!1!⋅2!⋅3!⋅2!⋅(3!)4=8000
*K. M. L. 36 (1968) 117.

*K. M. L. 42 (1971) 169.