Mat2200, grupper ringer og kropper. Bevise antall elementer.

[erlend1983]

Hei!

sliter noe med å komme i mål her.

"La A være en begrenset mengde, og la |A|=s (dvs. antall elementer i A er s). Gi det generelle uttrykket for antall elementer i power set (potensmengde?), dvs |P(A)|, og bevis at det må være slik."

P(A) er samlingen av alle mulige delmengder av A. F.eks. hvis A={1,2}, så er P(A)={ Ø, {1},{2}, {1,2}}, og dermed |P(A)|=4.

Jeg har funnet at hvis |A|=s, så er |P(A)|=2^s. Målet er å vise dette. Før jeg beveger meg over på generelt nivå, kan jeg se på A={1,2,3,4}.

I P(A) er det så en delmengde som har null elementer, nemlig Ø.
Videre er det 4 delmengder som har ett element.
Det er |{{1,2},{1,3}{1,4}{2,3}{2,4}{3,4}}|=6 delmengder som har to elementer. Osv.

Over til generelt nivå:
Anta nå at |A|=s. Hvis vi innfører litt kombinatorikk, så er antall delmengder med 0 elementer nemlig sC0=1. Dvs. antall uordnede utvalg når vi trekker 0 elementer ut av en mengde på s elementer.
Tilsvarende blir antall delmengder med 1 element sC1=s.
Antall delmengder med 2 elementer sC2=(sP2)/(2*1)=(s*(s-1))/(2*1)= s!/(2!*(s-2)!)
...
Antall delmengder med alle elementene: sCs=1.

Vi har altså summen: Sum(sCi), i=0 til i=s. Dette er jo nettopp radsummen i rad s i pascals trekant, der første rad er rad nr 0. Radsummen i rad nr s i pascals trekant er 2^s. Men jeg står fast i hvordan å vise dette. Noen tips?

Takk.



[/list]

[espen180]

Du kan prøve å bruke binomialteoremet.

[Karl_Erik]

Alternativt kan du tenke litt over hvordan du velger ut en delmengde. For hvert element i mengden har du to muligheter - du kan la det være med i delmengden du velger, eller ikke la det være med. Gjør du dette valget for ethvert element i den opprinnelige mengden har du unikt bestemt en delmengde. Ser du hvordan dette gir deg det du vil?

[Håkon K]

Hint: binære tall













Vi kan beskrive en delmengde B av [tex]A=\left{ a_1,\dots , a_n \right}[/tex] ved hjelp av en sekvens av 0’er og 1’ere, slik at f.eks. første tall er 1 hvis [tex]a_1 \in B[/tex], 0 hvis [tex]a_1 \not\in B[/tex] osv. Hvis A={a,b,c}, og delmengden B={a,b} vil B være bestemt av sekvensen 110. Mengden av alle forskjellige sekvenser beskriver potensmengden [tex]\mathscr{P}(A)[/tex]. Hvor mange kombinasjoner kan vi få når n=3? Og generelt?

[Charlatan]

Som espen180 foreslår burde du på ditt trinn i argumentet se på binomialekspansjonen til (1+1)^s.

[erlend1983]

Takker for gode tips. Skal sette meg ned med dette imorgen, så får me sjå:)

[magneam]

Hva hvis du ser på summen av rekke nr. n i Paskals trekant? Hvilken sammenheng har dette med kardinaliteten til powersettet?