Elemi kombinatorika

Az elemi kombinatorika a kombinatorika illetve a véges matematika egy szűk szelete, mely egy előre megadott véges halmaz elemeiből alkotott és adott tulajdonságot kielégítő csoportosításainak számát szándékozik meghatározni. Az elemi kombinatorika feladatai általában a mindennapi életből vett "leszámlálási feladatok" matematikai megfogalmazásai és a jobb áttekinthetőség és érthetőség kedvéért sokszor meg is maradnak az eredeti szövegkörnyezetben, így kártyapaklikról, dobókockákról, golyókkal teli urnákról és hasonlókról szólnak. Ezek a feladatok igen változatosak lehetnek, de bizonyos alapesetek, mint például az elemek permutációja, variációja vagy kombinációja újra és újra visszaköszönnek.

Az elemi kombinatorika alapgondolata

Jellegzetes feladat az elemi kombinatorikában, amikor egy n elemű H alaphalmazból:

$H=\{h_{1},h_{2},...,h_{n}\}\,$

kiválasztunk k elemből álló csoportokat, k-asokat:

$[a_{1},a_{2},...,a_{k}]\,$,

melyek valamilyen előre megadott tulajdonságot teljesítenek és a tulajdonságot teljesítő összes elemcsoportok (k-asok) számára vagyunk kíváncsiak.

Példák.

– Egyszerre feldobunk három egyforintost. Ha a fejek száma több, akkor Aladár fizet, ha az írások száma több, akkor Béla. Hány kimenetele lehet a dobásoknak (aszerint, hogy hány írást és hány fejet dobtunk)?

– Egy piros és egy kék dobókockával dobunk egyszerre. Hány olyan eset van, amikor a piros dobókockán páros számot, a kék dobókockán pedig hárommal osztható számot látunk?

– Pályázaton első, második és harmadik helyezést hirdetnek. 11 pályázat érkezett be. Hányféleképpen oszthatják ki a helyezéseket (ha a helyezések nem lehetnek megosztottak és mindegyiket kiosztják)?

A példák szövegéből is kitűnik: lényeges minden esetben eldönteni azt, hogy a kiválasztott k-asok között bizonyos elemek ismétlődését megengedjük-e, vagy fontosnak tartjuk-e, hogy az elemek milyen sorrendben vannak felsorolva. Például a három pénzérmés feladatnál biztosan nem számít a sorrend, és egy dobáson belül biztosan lesz ismétlődő fej vagy írás, míg a pályázatos példánál kizártuk, hogy több helyezést érjen el egy jelölt, ám a sorrendet lényegesnek tartjuk. Eszerint a k-asok két szempontból csoportosíthatók: ismétlődés és sorrend (vagy rendezettség) szempontjából. A négy alapesetet táblázatba foglaltuk és feltüntettük a jelüket is:

Adott, fenti típusú összes k-asok halmazai általában a lehetséges elrendezések egyfajta keretét, a valószínűségszámításban használt kifejezéssel eseményterét adják. Ezeknek a legbővebb eseménytereknek a konkrét alakjai a következők. (H az n elemű alaphalmaz.)

n elem k-adosztályú ismétléses variációi

Olyan rendezett k-asok, melynek minden eleme H-beli:

$\{(a_{1},a_{2},...,a_{k})\mid a_{i}\in H\}$

Ez tehát a H^k Descartes-szorzat. Elemszáma:

$V_{k}^{n,(ism)}=n^{k}\,$

Példa. Hány négyjegyű szám van, melyet csupa páratlan számjegy alkot? Nyilván ismétlődés lehet (az 1939 ilyen négyjegyű szám) és a sorrend is számít (1359 ≠ 3159). Az 1, 3, 5, 7, 9 számjegyekből a négyjegyű szám első helyére 5-öt, másodikra is 5-öt, …, választhatunk, azaz 5$\cdot$5$\cdot$5$\cdot$5 = 5⁴ darab ilyen szám van.

n elem k-adosztályú ismétlés nélküli variációi

Olyan rendezett k-asok, melynek minden eleme H-beli, de minden elem csak egyszer fordulhat elő.

$\{(a_{1},a_{2},...,a_{k})\mid a_{i}\in H\wedge (i\neq j\Rightarrow a_{i}\neq a_{j})\}$

Ez a halmaz megfeleltethető a k elemű I indexhalmazon értelmezett összes, H-ba képező injektív (kölcsönösen egyértelmű) függvények halmazának, azaz {f:I $\rightarrow$ H | f injektív }-nek. Elemszáma:

$V_{k}^{n}=n\cdot (n-1)\cdot ...\cdot (n-k+1)={\frac {n!}{(n-k)!}}$

Példa. Aladár, Béla és Csaba abból a célból, hogy eldöntsék ki fizeti a rundot, húznak egy-egy lapot az összes pikk közül. Hány különböző elrendezésben lehetnek náluk a lapok? A pikk 13 lapját páronként különbözőknek tekintjük (ettől különböző egy lapkiosztás) és a sorrend is számít, mert nem mindegy ki fog fizetni, ám ha egy lapot már kihúzott az egyikük, akkor a másik azt nem húzhatja. Az eredmény: 13$\cdot$12$\cdot$11.

E fogalomnak speciális esete az ismétlés nélküli permutáció fogalma (mikor is n=k).

n elem k-adosztályú ismétlés nélküli kombinációi

Olyan rendezetlen, páronként különböző elemű k-asok, melyek minden eleme H-beli.

$\{\;\{a_{1},a_{2},...,a_{k}\}\;\mid a_{i}\in H\wedge (i\neq j\Rightarrow a_{i}\neq a_{j})\}$

Tehát ez nem más, mint H összes k elemű részhalmazának halmaza. Elemszáma:

$C_{k}^{n}={\frac {n\cdot (n-1)\cdot ...\cdot (n-k+1)}{k\cdot (k-1)\cdot ...\cdot 1}}={n \choose k}$

Példa. 32 fős osztályban az osztályfőnök kioszt 3 jutalomkönyvet (mindegyik ugyanaz: Harry Potter és a félvér herceg), elvileg hány különböző módon oszthatja ki a könyveket, ha egy gyerek nem kaphat 2 példányt? A gyerekek megkülönböztethetők (nem ismétlődnek), de a könyvek nem, így az a kérdés, hogy 32-ből hány hármast lehet kiválasztani, amelyekben a sorrend nem számít. Ez ${\frac {32\cdot 31\cdot 30}{3\cdot 2\cdot 1}}={32 \choose 3}$.

n elem k-adosztályú ismétléses kombinációi

Olyan H-beli elemű k-asok, ahol egy elem "többször is előfordulhat" a k-asban. Minden elemhez hozzá van rendelve egy pozitív egész szám, melyet az elem multiplicitásának nevezünk és mely azt mutatja meg, hogy hányszor szerepel a k-asban. Ezeket a halmazszerű, de az elemeik ismétlődését nem tiltó entitásokat néha multihalmazoknak nevezik. Lényegében olyan függvények, melyek egy részhalmaz elemeihez a pozitív számokat rendelik, úgy, hogy az összegük k.

$\{f:A\rightarrow \mathbb {Z} ^{+}\mid \emptyset \neq A\subseteq H\wedge \sum \limits _{i\in A}f(i)=k\}$

Elemszáma:

$C_{k}^{n,(ism)}={{(n+k-1)!} \over {k!(n-1)!}}={{n+k-1} \choose {n-1}}={{n+k-1} \choose {k}}$

Példa. Két ugyanolyan színű tetraéder alakú "dobókockával" (dobótetraéderrel) dobunk. Hány különböző kimenetele lehet a dobásnak? A 4 lapra 4 szám van felírva (n = 4), ezek ismétlődhetnek, de mivel a két dobótetraéder (k = 2) színe ugyanaz, ezért nem megkülönböztethetők (sorrendjük nem számít). A képlet szerint a megoldás ${{4+2-1} \choose {4-1}}={5 \choose 3}={\frac {5\cdot 4\cdot 3}{3\cdot 2\cdot 1}}=10$

Természetesen vannak olyan példák, amelyekben ezek a halmazok nem szolgáltatják a tárgyalásban szereplő legbővebb halmazt. Például, ha dobókockával akárhányat dobhatunk, és az a kérdés, hogy hány olyan dobássorozat van, ahol a dobott értékek összege meghaladja a dobások számának négyzetét, akkor a fenti halmazok egyike sem alkalmas az összes lehetséges kimenetelek halmazának. Ellenben alkalmas a 6 elem összes ismétléses variációinak együttes halmaza, vagyis az alábbi diszjunkt unió:

$\biguplus \limits _{k=1}^{\infty }H^{k}\,$

Ami, azért mégis az alapesetekből épül fel.

Az elemi kombinatorikában használatos leggyakoribb módszerek

Ha egy kombinatorikai szituációban adott a lehetséges kimenetelek Ω halmaza, de nem ennek számára kérdeznek rá, hanem egy ω ⊆ Ω valódi részhalmaz számosságára, akkor tovább kell okoskodnunk ennek meghatározásához. Ehhez segítségünkre vannak az alábbi, jellegzetesen kombinatorikai feladatmegoldási módszerek.

Független kimenetelek szorzási szabálya

Ha az összes lehetséges kimenetel Ω halmazának ω ⊆ Ω valódi részhalmazába tartozó elemi kimenetelek száma a kérdés és létezik olyan A és B nemüres halmazok, hogy ω-ból bijekció képezhető az A × B Descartes-szorzatra, vagyis

$\omega \cong {\mathcal {A}}\times {\mathcal {B}}$

azaz ω és A × B kölcsönösen egyértelműen megfeleltethető egymással, akkor a Descartes-szorzat számosságára vonatkozó tétel miatt:

$|\omega |=|{\mathcal {A}}|\cdot |{\mathcal {B}}|$

Ezt a faktorizálhatóságot (hogy ω Descartes-szorzattá bontható) úgy fejezzük ki szavakban, hogy ω-t független kimenetelek rendezett párjai alkotják, és a szabály úgy hangzik, hogy:

Egymástól független kísérletek együttes kimeneteleinek száma a kísérletek számának szorzata.

Természetesen sokszor nem csak két faktorra bonthatók az összetett kísérletek, hanem többre. Ekkor a megfeleltetés ω és egy általános Descartes-szorzat között jön létre:

$\omega \cong \prod _{i\in I}{\mathcal {A}}_{i}$

ahol I véges, nem üres indexhalmaz és (A_i)_i∈I véges halmazok rendszere. Ilyenkor a keresett esetek száma:

$|\omega |=\prod _{i\in I}|{\mathcal {A}}_{i}|$

azaz az A_i-k elemszámainak szorzata.

Figyeljünk fel arra, hogy ebben az esetben, még ha ω elemei eredetileg rendezetlenek is voltak, rendezett sorozatokká alakulnak, hiszen különböző fajtájú objektumok csoportjaival hoztuk megfeleltetésbe őket.

Példa. 52 lapos kártyából 3-at húzunk (a sorrend nem számít, csak hogy melyek vannak a kezünkben). Ezen hármasok közül hányban van pontosan 1 király (sem több, sem kevesebb)?

Ha elképzeljük a keresett számú esetek ω halmazát, akkor felismerhetjük, hogy minden a ∈ ω hármasban pontosan 1 király van és pontosan egy olyan kételemű rendezetlen kártyapár, melyek egyike sem király. Ez azt jelenti, hogy minden a ∈ ω hármast egyértelműen meg tudunk feleltetni az összes királyok K halmazának és a nem királyokat tartalmazó rendezetlen párok G halmazának Descartes-szorzata egy elemének, azaz

$\omega \cong {\mathcal {K}}\times {\mathcal {G}}$

Ezek elemszáma viszont: |K| = $4 \choose 1$ ahányféleképpen kiválaszthatunk 1 királyt 4-ből, és |G| = $48 \choose 2$ ahányféleképpen kiválaszthatunk 48 nemkirályból 2-t (rendezetlent), azaz a végeredmény: |ω| = ${4 \choose 1}\cdot {48 \choose 2}$. Ugyan sorrend vagy sorszámok nincsenek, de a párok elemei mégis megkülönböztethetőek, mert az egyik király, a másik komponens pedig biztosan nem az.

Egymást kizáró lehetőségek összeadási szabálya

Ha a keresett elemszámú ω ⊆ Ω halmaz kölcsönösen egyértelmű módon megfeleltethető nemüres, diszjunkt halmazok A ∪ B diszjunkt uniójának, illetve az A # B := ( A×{$\circ$} ) U ( B×{$\bullet$} ) direkt összegnek, azaz

$\omega \cong {\mathcal {A}}\#{\mathcal {B}}$

akkor ω elemszámát

$|\omega |=|{\mathcal {A}}|+|{\mathcal {B}}|$

-vel számolhatjuk. Tehát

Egymást kölcsönösen kizáró lehetőségek együttes száma a lehetőségek számának összege.

(Ezt a megfeleltetést például úgy hozhatjuk létre, hogy ω-t felbontjuk két olyan halmaz uniójára (A és B), melynek nincs közös eleme, és a halmazok elemeit abból a célból, hogy megkülönböztessük őket egymástól az I = {$\circ$,$\bullet$} indexhalmaz elemeivel megcímkézzük, és kapjuk az

A # B = { (x,i) | (x∈A ∧ i=$\circ$) ∨ (x∈B ∧ i=$\bullet$)}

direkt összeget.)

Természetesen ω-t több, véges, páronként diszjunkt halmaz uniójára is bonthatjuk (ω egy osztályfelbontását képezzük), azaz előállítjuk a tetszőleges véges, nemüres I indexhalmazzal és az (A_i)_i∈I véges, nem üres elemekkel rendelkező halmazrendszerrel az

$\omega \cong \coprod _{i\in I}{\mathcal {A}}_{i}$

azonosítást és ekkor

$|\omega |=\sum _{i\in I}|{\mathcal {A}}_{i}|$

lesz ω elemszáma.

Példa. 32 lapos magyar kártyából kihúzunk 5 lapot (a sorrendjük nem számít, csak hogy mi van a kezünkben). Hány ilyen ötösben van legalább 3 tök?

Tökből összesen 32/4 = 8 van. A keresett lapkiosztásokban vagy pontosan 3 vagy pontosan 4 vagy pontosan 5 tök van. Ezek egymást páronként kizáró lehetőségek (mert az nem lehet, hogy egyszerre pont 4 tök legyen egy ötösben meg pont 5). Legyen tehát A azon ötösök, melyekben 3, B melyekben 4, és C, melyekben 5 tök van. Ezek elemszáma rendre (az előző példa logikája alapján) ${8 \choose 3}\cdot {24 \choose 2}$, ${8 \choose 4}\cdot {24 \choose 1}$, $8 \choose 5$. Tehát az összes lehetőség száma:

$|\omega |=|{\mathcal {A}}|+|{\mathcal {B}}|+|{\mathcal {C}}|={8 \choose 3}\cdot {24 \choose 2}+{8 \choose 4}\cdot {24 \choose 1}+{8 \choose 5}$.

Logikai szitaformula

Lásd még: logikai szita.

A keresett kimenetelek halmaza előállhat nem diszjunkt unióként, mely unió tagjainak és a tagok metszetének elemszámát tudjuk. Ekkor az unió elemszámára a következő képlet teljesül:

$|A\cup B|=|A|+|B|-|A\cap B|$

A kivonást azért kell elvégezni, mert a metszet elemeire vonatkozóan az összeszámolást az |A| + |B| összegben kétszer végeztük el.

Példa. Osztályban 12 németes, 18 angolos. Hány fős az osztály, ha 5-en mindkét nyelvet tanulják? Osztálylétszám = 12 + 18 – 5 = 25.

A logikai szitaformula általános esetben:

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,i<j}\left|A_{i}\cap A_{j}\right|$$+\sum _{i,j,k\,:\,i<j<k}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \cdots \ \pm \left|A_{1}\cap \cdots \cap A_{n}\right|$

Skatulyaelv

Lásd még: skatulyaelv.

A skatulya elv segítségével általában azt szokták igazolni, hogy létezik bizonyos tulajdonságú véges részhalmaz, de az elemszámát ebből nem feltétlenül lehet megmondani. Az elv:

Ha adott n darab skatulya (doboz) és n+1 darab ugyanolyan golyó, és ezeket mind belerakjuk a skatulyákba, akkor lesz olyan doboz, amiben legalább két golyó van.

Vagy általánosabban:

Ha adott n darab skatulya és m$\cdot$n + 1 darab ugyanolyan golyó, és ezeket mind belerakjuk a skatulyákba, akkor lesz olyan doboz, amiben legalább m + 1 golyó van.

Példa. Egyszerű, 6 csúcsú teljes gráfban kiszínezzük pirossal meg kékkel az összes élet (minden élet valamelyik színnel). Ekkor van olyan csúcs, melyből legalább három egyszínű él fut ki. Ha nem lenne és minden csúcsból csak legfeljebb 2 egyszínű él futna ki, akkor a teljes, egyszerű gráfnak legfeljebb csak (6$\cdot$4)/2 = 12 éle lenne a valóságos (6$\cdot$5)/2 = 15 helyett.

Komplementer módszer

Ha az ω ⊆ Ω halmaz számosságát nehézkes lenne meghatározni, akkor eljárhatunk úgy is, hogy először kiszámoljuk az összes lehetséges kimenetel |Ω| számát, majd mindazon esetek számát, mely Ω-n belüliek, de nem tartoznak ω-hoz, vagyis az Ω \ ω halmazkülönbség számosságát (azaz az ω halmaz Ω-ra vonatkozó komplementerének számosságát). Ekkor a keresett szám az összeadási szabály szerint:

$|\omega |=|\Omega |-|\Omega \setminus \omega |$

lesz.

Példa. Hány olyan lapnégyest tudunk kihúzni az 52 lapos francia kártyából, melyben legalább egy pikk van.

A nem pikkek száma 52 – 13 = 39. A pikket nem tartalmazó esetek száma $39 \choose 4$, az összes eset száma $52 \choose 4$, tehát a keresett szám: ${52 \choose 4}-{39 \choose 4}$.

Egyéb, a bizonyításokban használt módszerek

A fenti módszereket leginkább konkrét számításokban használják, de az alábbiak is előjönnek a kombinatorikai tételek bizonyításakor.

• Teljes indukció – Minthogy természetes számokról szólnak az állítások, a leggyakoribb bizonyítási módszer a teljes indukció.
• A bijekciók módszere – Gyakran van, hogy egy A halmaz számosságát úgy határozzák meg, hogy egy ismert elemszámú, vagy egyszerűbb B halmazzal hozzák bijektív kapcsolatba. Ha ugyanis létezik A $\rightarrow$ B bijekció, akkor A és B elemszáma ugyanaz.
• A tetszőlegesen választott elem módszere – Amikor az indukciós lépésnél eggyel növelik a bizonyításban szereplő halmaz elemszámát, akkor a következtetéseket egy tetszőlegesen választott k+1-edik elemet vizsgálva vonják le.

Az ismétléses variáció, mint eseménytér

(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)

6 elem (kockadobás) másodosztályú

ismétléses variációi, azaz a H × H halmaz elemei

Sokszor könnyebben áttekinthető (és hatékonyabb stratégia), ha az ismétléses variációk halmazát tekintjük eseménytérnek ($\Omega \,=\,{\mathcal {V}}_{k}^{H,(ism)}$) és ennek elemeitől tekintünk el ismétlés nélküli esetekben illetve a megkülönböztethetetlen k-asok esetén.

Az ismétlés nélküli variáció származtatása

Először tekintsük az ismétlés nélküli variáció esetét ($V_{k}^{n}$). A k=2 esetben (az ábra szerinti) egyszerűen az n darab ismétléstől kell megszabadulnunk és így n²-n = n(n-1) lesz $V_{2}^{n}$. Ha most k-ra vonatkozó teljes indukcióval feltesszük, minden n-re $V_{k}^{n}$ értéke ismert és keressük egy olyan H halmaz (k+1)-edosztályú ismétlés nélküli variációinak számát, melynek elemszáma $n\geq k+1$, akkor lényegében az összes I$\rightarrow$H injektív függvény számát keressük, ahol I tetszőleges k+1 elemű indexhalmaz.

(1,2) (1,3) (1,4) (1,5) (1,6) (2,1) (2,3) (2,4) (2,5) (2,6) (3,1) (3,2) (3,4) (3,5) (3,6) (4,1) (4,2) (4,3) (4,5) (4,6) (5,1) (5,2) (5,3) (5,4) (5,6) (6,1) (6,2) (6,3) (6,4) (6,5)

6 elem (kockadobás) másodosztályú

ismétlés nélküli variációi

Válasszunk tetszőlegesen és rögzítsünk egy i₀ ∈ I elemet. Az I / {i₀} halmaz k elemű, így az összes I / {i₀}$\rightarrow$H injektív függvény száma $V_{k}^{n}$. Mivel a H halmaz elemszáma n > k ezért mindegyik I / {i₀}$\rightarrow$H injektív függvényt kiterjeszthetjük I-re ráadásul éppen n – k féle különböző módon, olymódon, hogy az i₀-hoz rendelt elem ne legyen egyenlő egyik előző értékkel sem. Ekkor az ilyen függvények száma összesen $V_{k}^{n}\cdot (n-k)$, tehát $V_{k+1}^{n}=V_{k}^{n}\cdot (n-k)$. Innen könnyen adódik $V_{k}^{n}$ már említett képlete, melyet így is jelölünk:

$n^{\underline {k}}=n\cdot (n-1)\cdot ...\cdot (n-k+1)$

és az n szám (k hosszúságú) leszálló faktoriálisának mondunk.

Az ismétlés nélküli kombináció származtatása ismétlés nélküli permutáció segítségével

{1,2} {1,3} {1,4} {1,5} {1,6} {2,3} {2,4} {2,5} {2,6} {3,4} {3,5} {3,6} {4,5} {4,6} {5,6}

6 elem (kockadobás) másodosztályú

ismétlés nélküli kombinációi

Ha adott H alaphalmaz esetén k-asok ismétlés nélküli kombinációja a kérdés ($C_{k}^{n}$), akkor érdemes az összes ismétlés nélküli variáció esetét venni és a sorrendből adódó különbségeket megszüntetni. Ezt könnyen megtehetjük, ha észrevesszük, hogy ha $C_{k}^{n}$-t keressük, akkor $V_{k}^{n}$-hoz képest minden elemet többször, de ugyanannyiszor (!) számoltunk. k=2 esetén a táblázat jól szemlélteti, hogy mivel két elemnek kétféle sorrendje lehet, ezért $C_{2}^{n}={\frac {V_{2}^{n}}{2}}$. Általában az a kérdés, hogy k különböző elemnek hányféle sorrendje lehet (ha ismétlődést nem engedünk meg). Ez nem más mint az ismétlés nélküli variáció az n=k esetben, melyet ismétlés nélküli permutációnak nevezünk, és értéke:

$P_{k}=k\cdot (k-1)\cdot ...\cdot 1=k!$

ami tehát nem más, mint k faktoriálisa. Az általános esetben rögtön adódik a képlet:

$C_{k}^{n}={\frac {V_{k}^{n}}{P_{k}}}={\frac {n^{\underline {k}}}{k!}}={n \choose k}$

Ismétléses kombináció származtatása

[1,1] [1,2] [1,3] [1,4] [1,5] [1,6] [2,2] [2,3] [2,4] [2,5] [2,6] [3,3] [3,4] [3,5] [3,6] [4,4] [4,5] [4,6] [5,5] [5,6] [6,6]

6 elem (kockadobás) másodosztályú

ismétléses kombinációi

Ezt az esetet visszavezethetjük az ismétlés nélküli kombinációra, de ehhez teljesen meg kell változtatnunk a gondolkodásmódunkat. A H halmaz minden eleméhez hozzá van rendelve egy nemnegatív egész szám, mely megmondja, hogy hányszor szerepel a kiválasztásban, és melyeknek összege pontosan k. Ezt úgy ábrázolhatjuk, hogy sorba rakjuk a H halmaz elemeit, föléjük egy "dobozt" rajzolunk és ezekbe a dobozokba gyűjtjük a golyókat. Pontosan n db rekesz van és ennek pontosan n-1 olyan fala, mely rekeszeket választ el. Ha a rekeszekbe golyót teszünk, akkor falak és golyók összesen n+k-1 elemű sorozatát találjuk.

doboz _ o ooo … … … oo _ o H 1. 2. 3. … … … (n-2). (n-1). n.

Az ábrán n–1 db köztes válaszfal, k db golyó: összesen

n+k–1 hely, melyből a k db golyó helyét kell kiválasztani

Megoldjuk a feladatot, ha megmondjuk, hány féleképpen lehet sorbarendezni ezeket a tárgyakat. Először lerakjuk a kijelölt n+k-1 helyre a golyókat. Ez már kijelöli, hogy hol lesznek a válaszfalak, így a végeredmény:

$C_{k}^{n,(ism)}={n+k-1 \choose k}$