Kezdőoldal » Közoktatás, tanfolyamok » Házifeladat kérdések » Ismétlés nélküli kombináció...

Ismétlés nélküli kombináció bizonyítása?

Figyelt kérdés

Ugye az ismétlés nélküli kombináció az azt jelenti, hogy n elemből k darabot kiválasztok (n >=k), úgy hogy nem számít a sorrend.

Vagyis, hogy egy n elemű alaphalmaznak hány k elemű részhalmaza létezik.

Ezt pontosan n!/k!*(n-k)! amit "n alatt k"-val (binomiális együttható) is szoktak jelölni

Eddig én úgy tudtam, hogy ezt úgy lehet bizonyítani, hogy ugye ha n elemből k darabot kiválasztok, hogy a sorrend az számít akkor az n!/(n-k)!, mert ekkor ez egy ismétlés nélküli variáció.

Viszont a kombinációnál nem számít a sorrend tehát az n!/(n-k)!-ban benne vannak azok is amikor ugyanazokat az elemeket választom ki, csak más a sorrend. Pl.: piros, kék, zöld és kék, piros, zöld, ezt ilyenkor külön számoltam, két külön sorrendnek, míg ez kombináció esetén 1-nek számít. És ezért kell leosztani k!-al, hogy ezeket amikor ugyanazokat az elemeket kiválasztom, csak más sorrendben, akkor azt ne számoljuk meg 1-nél többször.

Viszont azt olvastam, hogy máshogy is lehet bizonyítani:

Amikor n elemből kell k darabot kiválasztani, akkor készítsek egy n hosszú 0/1-es sorozatot, amiben k darab 1-es és n-k darab 0 szerepel.

Pl.: ha n = 5 és k = 3, akkor:

10110

És ennek a 0/1-es sorozatnak az ismétléses permutációja (n!/(k1!*k2!*...kl!) az pont megadja az ismétlés nélküli kombinációt. Azaz minden ismétlés nélküli kombináció az egy ismétléses permutáció is.

pl az 10110 sorozatnak az ismétléses permutációja (mivel 5 elemem van és 3db 1-es, meg 2db 0-ás) az nem más mint 5!/(3!*2!) = 10

És ez pont megegyezik a C(5,3)-al, vagy "5 alatt 3"-al mert a C(5,3) = 10.

Az lenne a kérdésem, hogy mind a kettő bizonyítást jól írtam le és helyes?

Egy szóbeli vizsgánál melyiket érdemes elmondani, esetleg mondjam el mind a 2-t, vagy válasszak csak 1-et a 2 közül?

#bizonyítás #szóbeli #kombináció #variáció #permutáció #kombinatórika

2023. febr. 24. 12:05

1/6 anonim

válasza:

Ahogy szokták tanítani, az valóban az, hogy ha mindenki különböző lenne, akkor az ismétléses variáció szerinti n!/(n-k)! képlet alapján számolhatóak az esetek, de a k elemet tartalmazó eseteket mind k!-szor lettek megszámolva 1 helyett, ezért osztani kell k!-sal, így jön ki az n!/(n-k)!*k!).

A másik esetedben az az orbitális nagy hiba, hogy nem definiálod a 0/1 sorozatot, vagyis mi alapján szándékozod értelmezni; mivel a sorrend nem számít, ezért adjunk egy adott sorrendet az elemeknek;

a1 a2 a3 a4 a5

Ha egy esetben kiválasztunk egy elemet, akkor az alá írjunk 1-est, ha nem, akkor 0-t. A leírásod alapján 3 elemet akarsz kiválasztani, tehát pontosan 3 darab 1-esnek kell lennie. Például a

01101 azt jelenti, hogy a2,a3,a5 került kiválasztásra, az 10110 pedig az a1,a3,a4 kiválasztását jelenti. Könnyen belátható, hogy minden ilyen számsor 1 darab esetet jelöl.

A fontos, hogy KÖLCSÖNÖS EGYÉRTELMŰSÉG legyen, vagyis ha van egy kiválasztás, akkor ahhoz pontosan 1 számsor tartozzon. Például az a1,a3,a5 egyértelműen leírható egy számsorral? Igen: 10101. És ez bármelyik kiválasztásra igaz.

Innentől kezdve csak az a kérdés, hogy hányféle ilyen számsor létezik, erre a válasz az ismétléses permutáció alapján 5!/(2!*3!). Ugyanezt n-nel és k-val leírod, és meg is van a formális bizonyítás.

Ez azt is jelenti, hogy általánosságban a kombinációs feladatok mind visszavezethetőek ismétléses permutációra (ritkábban ismétlés nélkülire is).

2023. febr. 24. 12:24

Hasznos számodra ez a válasz?

2/6 anonim

válasza:

Az n!/(n-k)! képlet az n elem k-ad osztályú ismétlés nélküli variációinak számát adja.

2023. febr. 24. 13:03

Hasznos számodra ez a válasz?

3/6 anonim

válasza:

Igen, elírtam; nem ismétléses variáció, hanem ismétlés nélküli.