5 svar
89 visningar
Marx 65
Postad: 23 apr 2019 Redigerad: 23 apr 2019

Bevisföring

Visa att C(n,0)+C(n,1)·2+C(n,2)·22+....+ C(n,n)·2n=3n.


Kan någon hjälpa mig med den här uppgiften? Jag har ju förstått att man kan tänka sig att exempelvis har vi tre bokstäver A,B och C. Det går ju att skriva 33ord med tre bokstäver(högerledet) och för att förstå VL:et, vi kan säga hur många av orden innehåller bokstaven A? hur många av orden innehåller bokstäverna B och C?.....

Men finns det något generellt sätt att bevisa sambandet?

SeriousCephalopod 1818
Postad: 23 apr 2019 Redigerad: 23 apr 2019

När man har en summa av en massa binomialkoefficienter kan detvara användbart att jämföra med binomialsatsen.

Att försöka hitta en kombinatorisk tolkning vore förstås också kul. Ord med bokstäver tror jag fungerar bra även om jag skulle köra på tal uttryckta i bas 3.

Marx 65
Postad: 24 apr 2019
SeriousCephalopod skrev:

När man har en summa av en massa binomialkoefficienter kan detvara användbart att jämföra med binomialsatsen.

Att försöka hitta en kombinatorisk tolkning vore förstås också kul. Ord med bokstäver tror jag fungerar bra även om jag skulle köra på tal uttryckta i bas 3.

Men finns det något algebraiskt sätt att bevisa det? 

Smaragdalena 28036 – Moderator
Postad: 24 apr 2019 Redigerad: 24 apr 2019

Ja, som SeriousCephalopod skrev.

Albiki 4226
Postad: 24 apr 2019

Du kan skriva summan såhär:

    n0201n+n1211n-1++nn2n10.{n\choose 0}2^{0}1^{n}+{n\choose 1}2^{1}1^{n-1}+\cdots+{n\choose n}2^{n}1^{0}.

En jämförelse med Binomialsatsen ger det sökta svaret omedelbart.

    (a+b)n=n0a0bn+n1a1bn-1++nnanb0.(a+b)^{n} = {n\choose 0}a^{0}b^{n}+{n\choose 1}a^{1}b^{n-1}+\cdots+{n\choose n}a^{n}b^{0}.

SeriousCephalopod 1818
Postad: 24 apr 2019 Redigerad: 24 apr 2019

Den lösning Albiki presenterat är i praktiken den snabbaste men finns också kombinatoriska argument som kan användas för att bevisa den här typen av identiteter.

Jag tycker att din (marx) idé om att det kan ha något med strängar som byggs upp av symboler var väldigt bra. Så även fast du nu har en lösning kan du gärna fundera mer på om det finns fler. De koncepten som jag tror är användbara för det är:

  • nk{n \choose k} kan tolkas som antalet binära strängar av längd n med k ettor. 

exempel: 42{4 \choose 2} räknar upp antalet binära strängar av längd 4 med 2 ettor: 1100, 0110, 0011, 1010, 0101, 1001

  • Samtidigt är 2n2^n det totala antalet binära strängar av längd n

exempel: 242^4 är antalet binära strängar av längd 4 med godtyckligt många ettor: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

  • Och 3n3^n är antalet trinära trängar av längd n.

exmpel: 343^4 är antalet trinära strängar av längd 4. 0000, 0001, 0002, 0010, 0011, 0012, 0020, 0021, 0022, 0100, 0101, 0102, 0110, 0111, 0112, 0120, 0121, 0122, 0200, 0201, 0202, 0210, 0211, 0212, 0220, 0221, 0222, 1000, 1001, 1002, 1010, 1011, 1012, 1020, 1021, 1022, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1121, 1122, 1200, 1201, 1202, 1210, 1211, 1212, 1220, 1221, 1222, 2000, 2001, 2002, 2010, 2011, 2012, 2020, 2021, 2022, 2100, 2101, 2102, 2110, 2111, 2112, 2120, 2121, 2122, 2200, 2201, 2202, 2210, 2211, 2212, 2220, 2221, 2222

Man kan hålla på med ord ABC istället för siffror 012 men var enklare att generera. 


Identiteten ovan kan alltså tolkas som någon slags relation mellan antalen av olika typer av binära och trinära strängar och borde gå att härleda utifrån något argument om relationen mellan dem. 

Svara Avbryt
Close