Kombináció

A binomiális együttható kiszámítási képlete:

\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]

Behelyettesítve az adatokat:

\[ \binom{7}{3} = \frac{7!}{3! \cdot (7-3)!} = \frac{7!}{3! \cdot 4!} \]

Egyszerűsítve \( 4! \)-sal:

\[ \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = \frac{210}{6} = 35 \]

A lottónál a kihúzott számok sorrendje nem számít, és egy számot csak egyszer húznak ki (nincs ismétlés). Ezért ismétlés nélküli kombinációt kell alkalmaznunk.

Kiválasztunk 5 elemet a 90-ből:

\[ \binom{90}{5} = \frac{90 \cdot 89 \cdot 88 \cdot 87 \cdot 86}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 43\,949\,268 \]

Tehát 43 949 268-féle húzás lehetséges.

Mivel a bizottság tagjai között nincs alá-fölé rendeltségi viszony (nem osztunk ki posztokat, mint pl. elnök, titkár), a kiválasztás sorrendje nem számít.

12 emberből 3-at választunk ki:

\[ \binom{12}{3} = \frac{12 \cdot 11 \cdot 10}{3 \cdot 2 \cdot 1} = 220 \]

Összesen 220-féleképpen választható ki a bizottság.

A feladat szövege egyértelműsíti, hogy a sorrend nem számít. Mivel a csomagból húzunk és egy lap csak egyszer szerepelhet a kezünkben, ismétlés nélküli kombinációt használunk.

\[ \binom{32}{4} = \frac{32 \cdot 31 \cdot 30 \cdot 29}{4 \cdot 3 \cdot 2 \cdot 1} = 35\,960 \]

35 960 különböző kéz alakulhat ki.

Minden kézfogásban pontosan 2 ember vesz részt. Az A-nak B-vel történő kézfogása ugyanaz, mint B-nek A-val történő kézfogása, tehát a sorrend nem számít.

A feladat lefordítva: Hány 2 fős csoport képezhető 8 emberből?

\[ \binom{8}{2} = \frac{8 \cdot 7}{2 \cdot 1} = 28 \]

Összesen 28 kézfogás történik.

A halmazoknál az elemek felsorolási sorrendje lényegtelen (pl. \{1, 2\} ugyanaz a halmaz, mint a \{2, 1\}). Így a kiválasztott 4 elem sorrendje sem számít.

Ez egy klasszikus kombinációs feladat:

\[ \binom{7}{4} = \binom{7}{3} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35 \]

Tehát 35 darab 4 elemű részhalmaza van.

Az állítás igaz.

A binomiális együtthatók egyik legfontosabb tulajdonsága a szimmetria, ami matematikailag így írható fel:

\[ \binom{n}{k} = \binom{n}{n-k} \]

A mi esetünkben \( n = 15 \) és \( k = 4 \). Ekkor \( n-k = 15-4 = 11 \). Tehát valóban \( \binom{15}{4} = \binom{15}{11} \).

Logikai magyarázat: Ha 15 dologból kiválasztok 4-et amit "elviszek", azzal pontosan meghatározom azt a 11-et is, amit "ott hagyok".

Ez egy összetett kiválasztás, ahol a szorzási szabályt kell alkalmaznunk a kombinációkkal együtt. Bár egyszerre (vagy visszatevés nélkül) húzunk, a végeredmény szempontjából a sorrend nem érdekes.

• A 2 piros golyót az 5 piros közül választjuk ki: \( \binom{5}{2} \) féleképpen.
• Az 1 kék golyót a 4 kék közül választjuk ki: \( \binom{4}{1} \) féleképpen.

Mivel minden piros párhoz bármelyik kék golyó társulhat, a lehetőségeket összeszorozzuk:

\[ \binom{5}{2} \cdot \binom{4}{1} = 10 \cdot 4 = 40 \]

40-féleképpen húzhatjuk a kívánt összetételt.

A 12-szögnek 12 csúcsa van. Egy szakaszt (legyen az oldal vagy átló) pontosan 2 csúcs határoz meg.

1. Lépés: Számoljuk ki az összes lehetséges szakaszt a 12 pont között. Mivel a szakasz végpontjainak sorrendje nem számít (az AB szakasz ugyanaz, mint a BA):

\[ \text{Összes szakasz} = \binom{12}{2} = \frac{12 \cdot 11}{2} = 66 \]

2. Lépés: Ezek között a szakaszok között ott vannak a sokszög oldalai is, amelyeket nem tekintünk átlónak. Egy 12-szögnek pontosan 12 oldala van.

\[ \text{Átlók száma} = 66 - 12 = 54 \]

A sokszögnek 54 átlója van.

Egy háromszöget 3 csúcs határoz meg. Mivel a pontok egy körvonalon helyezkednek el, semelyik 3 pont nincs egy egyenesen (kollineárisak), így bármelyik 3 kiválasztott pont garantáltan alkot egy háromszöget.

A háromszög ABC csúcsainak felsorolási sorrendje lényegtelen.

\[ \binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120 \]

A 10 pont 120 darab különböző háromszöget határoz meg.

Mivel a bizottságban csak fiúk szerepelhetnek, a lányokkal egyáltalán nem kell számolnunk. A feladat arra redukálódik, hogy a 8 fiúból kell kiválasztanunk 5-öt.

\[ \binom{8}{5} = \binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56 \]

56-féleképpen választható ki a kizárólag fiúkból álló bizottság.

Bontsuk fel a binomiális együtthatót a definíció alapján:

\[ \frac{x \cdot (x-1)}{2 \cdot 1} = 21 \]

Szorozzuk meg mindkét oldalt 2-vel:

\[ x \cdot (x-1) = 42 \]

\[ x^2 - x - 42 = 0 \]

Megoldóképlettel a másodfokú egyenlet gyökei:

\[ x_{1,2} = \frac{1 \pm \sqrt{1 - 4 \cdot 1 \cdot (-42)}}{2} = \frac{1 \pm \sqrt{169}}{2} = \frac{1 \pm 13}{2} \]

A két gyök: \( x_1 = 7 \) és \( x_2 = -6 \).

Mivel a binomiális együttható felső indexe (x) csak nemnegatív egész szám lehet, a -6 hamis gyök. A megoldás: x = 7.

A levelek egyformák, tehát ha betesszük őket az "A", "B", "C" és "D" postaládákba, teljesen mindegy, hogy melyik konkrét levél melyik ládába esett (nem lehet őket megkülönböztetni).

A probléma megfordítható: a 6 különböző postaláda közül kell kiválasztanunk azt a 4-et, amelyekbe levél fog kerülni. A kiválasztás sorrendje nem számít.

\[ \binom{6}{4} = \binom{6}{2} = 15 \]

15-féleképpen oszthatjuk szét a leveleket.

A munkakör azonos, tehát a kiválasztottak között nincs sorrend (csak az a kérdés, ki kerül be és ki nem).

Mivel Kovács urat biztosan felveszik, rá már nem kell választást pazarolni. Tehát már csak 2 további üres hely van a cégnél.

Erre a 2 helyre a maradék 11 jelentkező közül választhatnak.

\[ \binom{11}{2} = \frac{11 \cdot 10}{2 \cdot 1} = 55 \]

55-féleképpen tölthetik be a maradék pozíciókat.

A két szám egyenlő.

Ezt a binomiális együtthatók szimmetriatulajdonsága adja meg:

\[ \binom{n}{k} = \binom{n}{n-k} \]

Esetünkben \( n = 100 \) és \( k = 3 \), így \( n-k = 100-3 = 97 \).

Tehát \( \binom{100}{3} = \binom{100}{97} \).

Két egymást kizáró esetet kell vizsgálnunk, melyek eredményét a végén összeadjuk (összegzési szabály).

1. eset: Mindketten bekerülnek a csapatba.
Ekkor 2 hely már foglalt (Anna és Béla). A maradék 18 osztálytárs közül kell még 2 embert választani.
Lehetőségek száma: \( \binom{18}{2} = 153 \).

2. eset: Egyikük sem kerül a csapatba.
Ekkor Anna és Béla ki van zárva a válogatásból, tehát a maradék 18 osztálytárs közül kell az összes 4 csapattagot kiválasztani.
Lehetőségek száma: \( \binom{18}{4} = 3060 \).

A két esetet összeadva: \( 153 + 3060 = 3213 \).

Összesen 3213-féleképpen választható ki a csapat.

Bármely 2 pont meghatároz egy egyenest. Ha egyetlen egyenesen sem lenne 2-nél több pont, akkor az összes egyenes száma: \( \binom{10}{2} = 45 \) lenne.

Azonban tudjuk, hogy van 4 olyan pont, ami egyetlen egyenesen (egy kollineáris halmazon) fekszik. Ez a 4 pont a \( \binom{4}{2} = 6 \) különböző egyenes helyett csak 1 darab egyenest határoz meg a valóságban.

Tehát az eredeti 45-ből le kell vonnunk a feleslegesen számolt "extra" egyeneseket:

\[ 45 - \binom{4}{2} + 1 = 45 - 6 + 1 = 40 \]

A pontok pontosan 40 egyenest határoznak meg.

A Pascal-háromszög egyik legfontosabb képzési szabálya, az úgynevezett összegzési tétel azt mondja ki, hogy két egymás melletti elem összege megadja az alattuk lévő sorban lévő elemet:

\[ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} \]

Alkalmazzuk ezt a szabályt a mi esetünkre (\( n=12, k=5 \)):

\[ \binom{12}{5} + \binom{12}{6} = \binom{13}{6} \]

Mivel a feladatok sorrendje nem számít (csak az, hogy mely feladatokat oldja meg a diák), kombinációt használunk.

Összesen 8 kérdésre kell válaszolni, de ebből 3 fixen le van foglalva az első 3 kötelező kérdéssel.

Tehát a hallgatónak még \( 8 - 3 = 5 \) kérdést kell választania a maradék \( 10 - 3 = 7 \) szabadon választható kérdésből.

\[ \binom{7}{5} = \binom{7}{2} = 21 \]

21-féleképpen állíthatja össze a feladatsorát.

Bármelyik utat is választjuk, az (5;3) pont eléréséhez mindenképpen meg kell tennünk pontosan 5 lépést Jobbra és pontosan 3 lépést Felfelé. Más irány nem lehetséges a legrövidebb úthoz.

Ez összesen \( 5 + 3 = 8 \) lépést jelent minden út esetén (pl. J-J-J-F-J-F-J-F).

A feladat arra egyszerűsödik: A 8 lépés pozíciója közül hova tegyük be a 3 Felfelé lépést? (A maradék 5 helyre automatikusan a Jobbra lépések kerülnek). A Felfelé lépések sorrendje nem számít (mind egyforma 'F' lépés).

\[ \binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56 \]

Összesen 56-féle legrövidebb úton juthatunk el a célba.