Kombinatorikai feladat (többi lent)?
Szóval nem teljesen házi, de talán ez a legjobb topik. A megoldás is megvan, de nem nagyon értem. Valaki el tudná mondani, vagy le tudná vezetni? Köszi előre is!
Egy 100 elemű halmaz esetén melyikből van több, páros vagy páratlan elemszámú részhalmazból?
(A megoldás elméletileg az, hogy egyenlő a számuk.)
Kb. 1:1-ben hasonló példát megoldottam, de abban 101 elemű halmaz volt. Amit ott használtam, itt nem működik (ott az (n k) = (n n-k) egyenlőség segített, ahol (n k) az "n alatt a k").
válasza:Itt C(n;k)-val jelölöm az (n alatt a k) értéket.
Ha n páros, akkor a páros elemű részhalmazok száma:
C(n;0)+C(n;2)+...+C(n;n)
A páratlan elemű részhalmazok száma:
C(n;1)+C(n;3)+...+C(n;n-1)
Most nézzük az (1-1)^n kifejezést és alkalmazzuk a binomiális tételt:
(1-1)^n=C(n;0)-C(n;1)+C(n;2)-C(n;3)+....-C(n;n-1)-C(n;n)
Mivel ennek az összegnek az értéke nulla, emiatt épp a keresett állítást igazoltuk.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!