[wiskunde] Aantal doorsnedes van verzamelingen

Moderators: ArcherBarry, Fuzzwood

Reageer
Berichten: 12

Aantal doorsnedes van verzamelingen

Hallo,

Voor een project moesten we een decodeertabel opstellen. Een bijvraag komt er op neer dat we een formule moeten vinden die weergeeft hoeveel mogelijke doorsnedes er zijn gegeven een aantal verzamelingen.

Afbeelding

Bovenstaande afbeelding geeft weer wat ik bedoel. Er zijn hier 5 verzamelingen en 12 mogelijke doorsnedes zodat we 17 verschillende 'partities' kunnen hebben. Ik zoek dus een formule f(5) = 12 of f(5) = 17 geldig voor gelijk welke n.

Ik heb reeds een tabel opgesteld die een paar waarden teruggeeft. De waarden in te tabel geven dus het aantal partities (17 in bovenstaand voorbeeld).

f(1) = 1

f(2) = 3

f(3) = 7

f(4) = 13

f(5) = 17

Kan iemand mij op weg helpen?

Alvast bedankt,

Daan

Berichten: 7.068

Re: Aantal doorsnedes van verzamelingen

Hoe kom je bij die tekening? Volgens die tekening is het namelijk niet mogelijk dat een element in verzameling a en verzameling c zit. Waarom wordt deze mogelijkheid uitgesloten?

Berichten: 12

Re: Aantal doorsnedes van verzamelingen

He, ik heb die mogelijkheid gewoon over het hoofd gezien. Verder blijft de vraag gelijk

Berichten: 7.068

Re: Aantal doorsnedes van verzamelingen

Een element zit of wel in een verzameling of niet. Stel je hebt 1 verzameling. Een element zit daar of wel of niet in. Je hebt hier dus 2 mogelijkheden. Als een element altijd in ten minste 1 verzameling zit, moet je hier nog de optie "in geen enkele verzameling" vanaf halen, dus 1 mogelijkheid.

Stel je hebt 2 verzamelingen. Een element kan per verzameling er wel of niet in zitten. Je hebt dus 2*2 = 4 mogelijkheden, dus er zijn 3 mogelijkheden (vanwege de "geen enkele verzameling"-optie).

Zie je het patroon?

Berichten: 12

Re: Aantal doorsnedes van verzamelingen

Ik zie het bijna, zou u het nog eens voor 3 verzamelingen kunnen uitschrijven?

Alvast bedankt,

Daan

Berichten: 7.068

Re: Aantal doorsnedes van verzamelingen

Laat ik het zo zeggen: als je twee verzamelingen hebt dan heb je 4 mogelijkheden. Als je hier een derde verzameling aan toevoegd dan zit een element in een van deze 4 mogelijkheden en niet in de derde verzameling OF in een van die 4 mogelijkheden en wel in de derde verzameling... dus...

Berichten: 12

Re: Aantal doorsnedes van verzamelingen

ah 2 * 4 + 1 omdat het er ook niet in kan zitten. Ben ik juist?

Berichten: 7.068

Re: Aantal doorsnedes van verzamelingen

Maak eens een tabelletjes. Met een 0 geef ik aan dat een element niet in een verzameling zit en met een 1 geef ik aan dat ie er wel in zit. Stel ik heb alleen verzameling A. Dan is het tabelletje:

A

0

1

Ofwel het element zit of wel in verzameling A of niet. Er zijn 2 mogelijkheden, maar de mogelijkheid "in geen verzameling" wil ik niet meetellen, dus 2-1 = 1.

Nu voor twee verzamelingen (A en B):

AB

00

10

01

11

Hier zijn dus vier mogelijkheden, dus 4 - 1 = 3 (vanwege de "in geen verzameling" optie).

Maak nu zelf het tabelletje voor 3 verzamelingen (ABC).

Berichten: 12

Re: Aantal doorsnedes van verzamelingen

ABC

111

110

101

100

011

010

001

000

Dus het aantal mogelijkheden is 2^3 - 1 vanwege de 'in geen verzameling' optie. Ik snap het nu. Bedankt voor de uitleg.

Reageer