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 $S_k=\{1,2,\dots ,k\}.$ Anta at $X$ er en delmengde av $S_n$ med kardinalitet $k.$ En delmengde av $X$ vil dermed ha kardinalitet $\le$ $k.$ Dette innebærer at X er en minimal egoistisk mengde hvis og bare hvis $S_k\cap X=\mathrm{\varnothing }.$ Følgelig må $X\subset \{k+1,k+2,\dots ,n\}.$ M.a.o. kan de $k$ tallene i X velges blant $n-k$ tall. Ergo er det $(\genfrac{}{}{0ex}{}{n}{k})$ minimal egoistiske delmengder av $S_n$ med kardinalitet $k.$ Så antall minimalt egoistiske delmengder av $S_n$ blir

$\sum _{k=0}^{[n/2]}(\genfrac{}{}{0ex}{}{n}{k})=F_{n+1}.$

Det faktum at summen på venstre side er identisk med $F_{n+1}$ kan vi f.eks. lese av formel (61) på nettsiden http://mathworld.wolfram.com/FibonacciNumber.html