[Matematyka dyskretna] Obliczanie ilości kombinacji n-zbiorów

pytanie zadane 23 października 2015 w Offtop przez tede774 Bywalec (2,650 p.)

Witam!

Mam dość trudne jak dla mnie zadanie, które polega na stworzeniu funkcji, której wynikiem jest ilość kombinacji relacji zbiorów (nie wiem jak to określić). Ręcznie sprawdzałem ilość kombinacji i np. dla jednego 1, ale dla dwóch już 4, a dla trzech to już aż około 37 (tyle udało mi się narysować, więc jakieś mogłem pominąć przypadkiem)... Nie wiem kompletnie jak to ogarnąć... Fajnie by było gdyby ktoś pomógł mnie nakierować na odpowiedź, ponieważ muszę to rozumieć jak do tego dojść...

Proszę o pomoc. Siedzę nad tym od wielu godzin i nie jest to moje pierwsze podejście do tego...

3 odpowiedzi

odpowiedź 23 października 2015 przez furas Maniak (53,800 p.)

Podaj treść zadania i ewentualnie zdjęcie tego ci już udało Ci się narysować.

komentarz 24 października 2015 przez tede774 Bywalec (2,650 p.)

Niestety treść zadania nie została podana dokładnie, a jeśli chodzi o rysunki to mogą być trochę nieczytelne, ale chodzi o napisanie funkcji, która zależnie od ilości zbiorów f(n) ma przedstawić ilość możliwości rozrysowania tych zbiorów... Nie potrafię tego lepiej wyjaśnić... :/ Wszystkie rysunki na zdjęciu przedstawiają możliwości połączenia 3 zbiorów, ale chyba nie wszystkie kombinacje są na tym zjęciu, ponieważ część jest ucięta...

komentarz 24 października 2015 przez furas Maniak (53,800 p.)

Ten rysunek dobrze wyjasnia problem :)

Przypadek dla trzech zbiorów można by narysować jako

i pole o różnych kolorach ponumerować. W każdym polu zaś wstawiać 1 gdy jest tam jakiś element lub 0 gdy pole jest puste. W ten sposób wszystkie możliwe sytuacje można by to sprowadzić do ciągu cyfr 0 i 1 czyli liczb w zapisie binarny.

Ale taki sposób zawiera także przypadki gdy np. B jest całkiem puste, i trzeba by je odejmować. Odjęcie wszystkich przypadków gdy B jest puste, a potem odjęcie wszystkich przypadków gdy A jest puste doprowadzi do odjęcia dwukrotnie przypadku gdy puste są jednocześnie A i B - więc trzeba by coś dodać. To zaś zaczyna przypominac `wzór na włączenia i wyłączenia`, który też należy do Matematyki Dyskretnej.

Dla 4 zbiorów trudno jednak narysować coś podobnego - może dało by się to zrobić w trzech wymiarach - więc trudno też to dalej pociągnąć i wykorzystać do obliczeń.

Ostatecznie nie mam żadnego pomysłu na to.