rekenen met powersets

[alberthendriks]

Ik weet niet of dit te makkelijk, te moeilijk of onmogelijk is, dus mijn excuses als dit in het verkeerde forum wordt gepost. Ook hoop ik dat ik alles goed opschrijf.
Gegeven is de set van alle natuurlijke getallen kleiner dan .
Neem nu de powerset van de powerset van , en streep daaruit alle sets weg die niet union-free zijn. Ik wil de grootte van deze set hebben als een functie van .

Een set van sets is union free desd als beide van de volgende gelden:



En verder hebben we dus
is union-free


Voorbeelden:
= {0,1,2}
= {
{{0,1},{1,2}},
{{0,2},{1,2}},
{{0,1},{0,2}},
{{0,1,2}},
{{0,1},{2}},
{{0,2},{1}},
{{1,2},{0}},
{{0,1}},
{{0,2}},
{{1,2}},
{{0},{1}},
{{0},{2}},
{{1},{2}},
{{0},{1},{2}}
{{0}},
{{1}},
{{2}},
{{}},
{}
}
Als we kijken naar , dan bevat deze bijvoorbeeld
wel: {{1,2,3},{2,3,4},{0}} maar bijvoorbeeld
niet: {{1,2,3},{2,3,4},{1,4}} maar weer
wel: {{1,2,3},{2,3,4},{1,4,0}} en zelfs ook
(!)wel: {{1,2,3},{2,3,4},{1,4,0},{0,5}}

Eventueel hoef ik niet de grootte exact te weten: onder- en bovengrenzen kunnen interessant zijn.

[Hugo]

Eventueel hoef ik niet de grootte exact te weten: onder- en bovengrenzen kunnen interessant zijn.

het kan aan mij liggen, maar ik zie nergens een vraag

oftwel probeer uit te leggen wat je bedoelt en wilt weten en waarom je het zelf niet weet

[alberthendriks]

Klopt. Om precies te zijn wil ik weten of de volgende uitspraak waar is:

Geformuleerd met de Big-O notatie is dit hetzelfde als


Ik studeer geen wiskunde (maar informatica). Ik me aan het oriënteren voor een onderwerp voor mijn afstudeerscriptie en ik kwam dit probleem tegen. Met hulp van een medestudent was ik er al heel trots op dat we deze formule hadden bedacht: , waarschijnlijk heel basic maar veel verder kom ik eigenlijk niet.