Egoistiske mengder

[daofeishi]

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.

[Solar Plexsus]

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