Bevis
Hej jag har fastnat på en fråga igen..
”Visa att en mängd med n element har 2^n delmängder”
Jag testat sätta in olika värden och det att det stämmer men har ingen aning om hur jag ska skriva ett generellt bevis. Finns inte heller något facit tyvärr. Kan någon ge en hint?
Tråd flyttad från Kombinatorik till Mängdlära. /Smutstvätt, moderator
Om du är osäker på hur du ska bevisa ett påstående finns det två viktiga saker att göra:
- Definiera begrepp och termer som används
- Prova med några exempel
Steg två har du redan gjort, utmärkt! Definiera nu vad en delmängd är. Hur konstrueras en delmängd? Vilka krav måste en delmängd uppfylla?
Om A är delmängd till N så är A antingen lika med N, och/eller innehåller element som tillhör N
så om N innehåller n element,
Kan A innehålla en av elementen i n, 2 av elementen, 3 osv ända upp till n (plus den tomma mängden)
Jag tänker såhär:
c(n,1) ger mig antal fall där A innehåller endast ett av elementen i N. c(n,2) då A innehåller 2 av elementen osv ända upp till c(n,n) = 1. Sedan adderar jag 1 för tomma mängden.
det känns dock inte som att detta kommer ge mig svaret 2^n
För varje element i mängden så gäller det att antingen är elementet med i delmängden, eller också är det inte med delmängden. Då kan man skriva 1 om elementet är med och 0 om det inte är med. Hur många olika binära tal kan man göra med n stycken siffror?
Vad blir summan
c(n,0) + c(n,1) + ... + c(n,n - 1) + c(n,n)
?
Du kan använda binomialsatsen för utvecklingen av
(a + b)^n
Välj sedan att titta på specialfallet a = b = 1.
ÄDr. G skrev:Vad blir summan
c(n,0) + c(n,1) + ... + c(n,n - 1) + c(n,n)
?
Du kan använda binomialsatsen för utvecklingen av
(a + b)^n
Välj sedan att titta på specialfallet a = b = 1.
Yes jag gjorde det och då slog det mig att det är summan av siffrorna för rad n i pascals triangel. Kan dock inte fortsätta härifrån.
Är det möjligt att jag behöver kunna induktion för att lösa frågan? För vi har inte gått igenom det än?
Smaragdalena skrev:För varje element i mängden så gäller det att antingen är elementet med i delmängden, eller också är det inte med delmängden. Då kan man skriva 1 om elementet är med och 0 om det inte är med. Hur många olika binära tal kan man göra med n stycken siffror?
Jag tror jag förstår. Jag har alltså 2 val för varje nummer. Om det finns n nummer har jag 2^n olika fall
