Egoistiske mengder

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Egoistiske mengder

Innlegg daofeishi » 08/10-2007 11:03

Definer en egoistisk mengde som en mengde som har sin egen kardinalitet (antall elementer i mengden) som element. Finn antall undermengder av {1, 2, ... n} som er minimale egoistiske mengder, altså egoistiske mengder som ikke har undermengder som er egoistiske.
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Innlegg Solar Plexsus » 21/10-2007 10:38

La [tex]S_k \,=\, \{1,2, \, \ldots \, ,k\}.[/tex] Anta at [tex]X[/tex] er en delmengde av [tex]S_n[/tex] med kardinalitet [tex]k.[/tex] En delmengde av [tex]X[/tex] vil dermed ha kardinalitet [tex]\leq[/tex] [tex]k.[/tex] Dette innebærer at X er en minimal egoistisk mengde hvis og bare hvis [tex]S_k \cap X = \emptyset.[/tex] Følgelig må [tex]X \subset \{k+1, \, k+2, \, \ldots \, ,n\}.[/tex] M.a.o. kan de [tex]k[/tex] tallene i X velges blant [tex]n \,-\, k[/tex] tall. Ergo er det [tex]{n \choose k}[/tex] minimal egoistiske delmengder av [tex]S_n[/tex] med kardinalitet [tex]k.[/tex] Så antall minimalt egoistiske delmengder av [tex]S_n[/tex] blir

[tex]\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \sum_{k=0}^{[n/2]} \: {n \choose k} \;=\; F_{n+1}.[/tex]

Det faktum at summen på venstre side er identisk med [tex]F_{n+1}[/tex] kan vi f.eks. lese av formel (61) på nettsiden http://mathworld.wolfram.com/FibonacciNumber.html
Solar Plexsus offline
Over-Guru
Over-Guru
Innlegg: 1673
Registrert: 03/10-2005 11:09

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 19 gjester