Vi har at [tex]2^n = \sum_{k=0}^n {n \choose k}[/tex]. Jeg har et kombinatorisk bevis for dette, men er ikke sikker på om det holder mål.
Antar at vi har en samling av n objekter. Da kan jeg trekke ut en delmengde av nøyaktig k av dem på [tex]{n \choose k}[/tex] forskjellige måter (dette blir dermed summen av alle måtene, høyresiden av ligningen). Men det totale antallet delmengder er også [tex]2^n[/tex].
Jeg beviser det siste her med at om vi skal trekke ut delmengder fra n elementer, så kan det i'te elementet enten være med eller ikke være med. Det er altså 2 mulige utfall for det i'te elementet. Da blir det [tex]2^n[/tex] mulige måter for alle n elementene tilsammen.
Holder dette beviset?
Kombinatorisk bevis
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Guru
- Innlegg: 628
- Registrert: 06/08-2011 01:56
Det holder det, kunne eventuelt tatt med hvorfor summen av alle delmengder er 2^n.
Et annet bevis er:
[tex]2^n=(1+1)^n=\sum_{k=0}^n{n\choose k}[/tex]
Hvor binominalteoremet brukes i andre overgang.
Et annet bevis er:
[tex]2^n=(1+1)^n=\sum_{k=0}^n{n\choose k}[/tex]
Hvor binominalteoremet brukes i andre overgang.
-
- Dirichlet
- Innlegg: 194
- Registrert: 25/01-2013 17:58
Takk for svar!
Ja skulle bevise dette på to måter...
Ja skulle bevise dette på to måter...