Zadanko z kombinatoryki matematycznej !

alpha_omega [ Senator ]

Wszystkie litery, czy jakiekolwiek mają ze sobą nie sąsiadować? Jeśli jakiekolwiek to po prostu weź to od drugiej strony - oblicz ile mamy kombinacji w których jakiekolwiek dwie takie same litery sąsiadują ze sobą i odejmij wynik od wszystkich kombinacji. Jeśli dobrze rozumuję będzie to rozwiązanie zadania. Wydaje się też, że to prostsze postawienie sprawy.

alpha_omega [ Senator ]

Jednak i takie jej postawienie nie ułatwia zbytnio zadania. Właściwie jest tożsame, i tak i tak trzeba w ten sposób rozumować.

Grabixon1987 [ Pretorianin ]

alpha_omega

wlasnie w tym problem, bo musze zsumowac wszystkie przypadki, gdzie np. 2 litery A sąsiadują ze sobą + np. 3 litery A sąsiaduję ze sobą i 2 litery B sąsiadują ze sobą

licząc te wszystkie przypadki poprzez wariacje wyjdzie prawdoposobnie wielki wynik, wiec ze zdarzenia przeciwnego nici

chodzi o to, ze od liczby wszystkich wyrazów trzeba odjąc takie wyrazy gdzie będzie np. AABRKADABRA i AAABRKDABRA jak i AABBRKADARA i np. AAAAABBRRKD i oczywiscie wszystkie permutacje powyzszych wyrazów

nie mam pojecia jak to liczyc, a takie zadanie mialem na egzaminie w czerwcu

Grabixon1987 [ Pretorianin ]

up

alpha_omega [ Senator ]

Nie wiem, jakoś nie przychodzi mi na myśl sposób rozwiązania tego schludnie. Można natomiast spróbować łopatologii: przyjrzeć się A i wyliczyć ile jest możliwych ustawień, ażeby A się nie powtarzało (nie było obok siebie). Jeśli A się nie jest obok siebie, to mamy chyba (bez różnicowania liter różnych od A):

2 możliwości że tylko dwie litery różne od A sąsiadują ze sobą
1 możliwość, że litery różne od A nigdy nie sąsiadują ze sobą
4 możliwości że trzy litery różne od A sąsiadują ze sobą
6 możliwości, że mamy dwie różne i oddzielne pary liter róznych od A i sąsiadujących ze sobą

Z tego myślę - krok po kroku - i wcale nie tak trudno dałoby się wyliczyć wynik, pewien nie jestem. Ale to jest łopatologia. Na pewno w zadaniu jest jakiś haczyk, który wszystko sprowadziłby do jednej myśli, tylko ja go na razie nie widzę.

alpha_omega [ Senator ]

Up. Jestem ciekawy rozwiązania :)

M'q [ Schattenjäger ]

alpha_omega --> 5xA, a Ty chcesz sobie policzyć wszystkie możliwe kombinacje, na wszystkich pozycjach i odjąć? :> Już na oko tego będzie "trochę".

A co do rozwiązania:
Też jestem ciekawy. Mało tego, na pewno robiłem takie zadania, tyle, że już nie pamiętam :/ Z czystej ciekawości nawet przeglądam notatki, ale niestety jak narazie nie umiem tego znaleść.

alpha_omega [ Senator ]

M'q -----------> Wiem, tak swobodnie rzucam pomysły do rozpatrzenia. Nie mówię, że tak się z całą pewnością daje to rozwiązać. Jak widać we wszystkich tych podejściach i tak powraca problem powodowany tym, że mamy rózne ilości liter i póki nie znajdzie się na to sposobu, nie rozwiąże się tego zadania.

Swoją drogą - to jest zadanko licealne?

Milka^_^ [ Zjem ci chleb ]

Z tego co mi tłumaczył jeden forumowicz (mam nadzieję, że się nie obrazi)(zostawiam w orginale):
zasada wlaczania i wylaczania to tak naprawde liczenie elemntow sumy zbiorow

naprostzy przypadek w wypadku dwoch zbiorow

masz a i B

i chcesz znac liczbe elementow A u B

wiesz tylko ze zbior A ma np. 10 elementow

a zbior B 14

nie wiesz czy gdzie nie ma powstarzajacych sie elementow

jezeli nie ma, to liczba elementow A u B = 10 + 14

jezeli są to dodajac do siebie 10 + 14 liczysz dwa razy, elementy powtarzajace sie

czyli od wyniku ktory otrzymasz musisz odjac jeden raz czesc wspolna

i w tym wypadku wzor wyglada tak:

|A u B| = |A| + |B| - |A n B|

w przypadku trzech zbiorow

wyglada to podobnie

napierw dodajesz liczbe wszytkich elemtnow

potem odejmujesz czesci wspolne

i na koniec dodajesz czesc wspolna calkowitą

czyli

|A u B u C| = |A|+|B|+|C| - |A n B| - |B n C| - |A n C| + |A n B n C|

M'q [ Schattenjäger ]

Póki co, nie dało mi to spokoju. Notatki nie pomogły, a w necie trafiłem jedynie na takie coś, tylko jest to o wiele prostsze zadanie.



I przy okazji trafiłem na "podobny" wątek ;)



Ale widzę, że minutę temu rozwiązanie padło, zaraz przejrzę :)

M'q [ Schattenjäger ]

Milka^_^

Zasada włączania i wyłączania liczy elementy tylko raz.
Dla pewności rozpisałem to sobie na prostych dwóch zbiorach 2-elementowych (w których jeden się powtarza) --> powinno być 5 możliwych kombinacji, wg wzoru są 3. (Czy może coś pomieszałem?)

Milka^_^ [ Zjem ci chleb ]

M'q => ja z tego nic nie rozumiem szczerze mówiąc, a to mi dał student matematyki. Nie sprawdzałem to nie wiem o co tutaj chodzi, ale wkleiłem, bo może coś pomóc.

04.09.2007

18:58

[15]

alpha_omega [ Senator ]

Wiedziałem, że to po prostu wymaga rozkminienia jakiejś dziedziny, jakiej jeszcze nigdy nie rozkminiałem, bo podstawy kombinatoryki wydawały się niewystarczające do ujęcia problemu w jakieś jasne myślowe konstrukcje :) Nie pozostaje nic innego jak jeszcze kilka dni usiłować samemu wypracować jakieś pojęcia potrzebne do rozwiązania, a jeśli się nie uda, wtedy dopiero zasięgnąć wiedzy innych.

Grabixon1987 [ Pretorianin ]

Dzisiaj mialem egzamin poprawkowy z kombinatoryki i bylo wlasnie takie samo zadanie tylko ze slowem MATEMATYK

po egzaminie dowiedzialem sie ze trzeba chyba uzyc wlasnie zasady wlaczania i wylaczania, ale pozniej w domu rozkminialem i nic mi nie wyszlo

te zadanie z ABRAKADABRA mialem na czerwcowym egzaminie

M'q ten drugi link do matematyka.org jest watkiem takze zalozonym przezemnie

M'q [ Schattenjäger ]

Tutaj litery powtarzają się tylko podwójnie, a nie x5, jak w tamtym, także wydaje mi się, że da się to rozwiązać podobnie jak podałem w pierwszym linku:

MATEMATYK

Wszystkich kombinacji jest 9!

AA 2!*5*7!=10*7!
TT 10*7!
MM 10*7!

9!-3(10*7!)
362880-3(10*5040)=362880-151200=211680

Nie wiem, czy dobrzeale ja bym to zrobił tak :)

Milka^_^ [ Zjem ci chleb ]

Zasada włączania i wyłączania, którą zaprezentowałem jest ogólną ideą, i można ją stosować przy większej liczbie zbiorów. W ostatniej wiadomości skończyłem na trzech.
Weźmy np. słowo MATEMATYK. Nie wiem ile liter ma mieć wyjściowy wyraz, bo nie widzę tego w treści - pewnie nie 11 bo wtedy zadanie straci sens, ale załóżmy dla przykładu, że chodzi o liczbę słów mających dokładnie 9 liter (nie bez powodu biorę najprostszy przypadek – chcę pokazać idee, a nie moc obliczeniową). Chcemy policzyć ile jest wyrazów gdzie żadne dwie takie same litery nie sąsiadują ze sobą. Tworzymy trzy zdarzenia.

A - litery M sąsiadują ze sobą
B - litery T sąsiadują ze sobą
C - litery A sąsiadują ze sobą

Innych zdarzeń nie ma sensu tworzyć, bowiem litery E, Y, K nie mogą sąsiadować ze sobą ze względu na ich jedyność.
Przypominam, że „zdarzenia” to po prostu „pewien podzbiór zbioru wszystkich zdarzeń elementarnych”.
Interesuje nas moc zdarzenia A u B u C (czyli, liczba wyrazów gdzie istnieją litery stojące obok siebie).

Liczymy moc zdarzeń A, B, C

|A| = 8 *(7 nad 2) * (5 nad 2)* 3! tutaj zawierają się także przypadki, że T sąsiadują ze sobą, jak i że A sąsiadują, ze sobą. Nas to jednak nie obchodzi. Analogiczna właściwość zachodzi niżej.
|B| = j.w. ponieważ przypadek jest analogiczny. Tutaj zawierają się także przypadki, że M sąsiadują ze sobą, jak i że A sąsiadują, ze sobą.
|C| = j.w. ponieważ przypadek jest analogiczny. Tutaj zawierają się także przypadki, że M sąsiadują ze sobą, jak i że T sąsiadują, ze sobą.

Jeżeli dodamy do siebie te wartości to:

Dwa razy policzymy słowa gdzie zarówno M i T sąsiadują ze sobą - zdarzenie A n B
Dwa razy policzymy słowa gdzie zarówno T i A sąsiadują ze sobą - zdarzenie B n C
Dwa razy policzymy słowa gdzie zarówno M i A sąsiadują ze sobą - zdarzenie A

razy policzymy słowa gdzie zarówno M, T, A sąsiadują ze sobą - zdarzenie A n B n C

Wiec od |A| + |B| + |C| odejmijmy |A n B|, |B n C|, |A n C|

|A n B| = (6*5 + 2*6)*(5 nad 2)*3!
|B n C| = (6*5 + 2*6)*(5 nad 2)*3!
|A n C| = (6*5 + 2*6)*(5 nad 2)*3!

Mamy teraz wartość liczbową:

|A| + |B| + |C| - |A n B| - |B n C| - |A n C|

- policzyliśmy w efekcie wszystkie przypadki jeden raz, poza przypadkiem gdzie w słowie występują zarówno M,T,A - w wyniku odejmowania trzykrotnego w w.w. wyrażeniu nie policzyliśmy takiej opcji ani razu. A więc liczymy:

|A n B n C| = 35*3!*3!

I dodajemy do całości

|A| + |B| + |C| - |A n B| - |B n C| - |A n C| + |A n B n C|

W ten sposób otrzymujemy wartość |A u B u C| czyli liczbę takich wyrazów w których pojawiają się obok siebie dwie litery. Teraz wystarczy policzyć liczbę wszystkich permutacji z powtórzeniami i od nich odjąć to co wyliczyliśmy.
Taka jest ogólna idea. Można ją modyfikować. Ze słowem ABRAKADABRA będzie podobnie, ale sprawę komplikuje fakt, że
1. Litera A występuję więcej niż dwa razy, a co za tym idzie, będzie więcej babrania podczas liczenia pojedynczych zdarzeń.
2. Słowo układane ma mniej liter niż wyjściowe.
Te dwa punkty będą jedynie komplikować liczenie podczas pojedynczych zdarzeń. Trzeba zrozumieć, że zasada włączania i wyłączania nie rozwiązuje zadań, a tylko pozwala je rozbić na mniejsze składowe problemy. Idea jednak jest cały czas ta sama. W słowie ABRAKADABRA także będą dokładnie trzy zdarzenia.

Wyjaśnienie. Tekst nie mój. Tyle wyjaśnień.

M'q możesz to sprawdzić.

05.09.2007

18:17

[19]

M'q [ Schattenjäger ]

Eee, pewnie dobrze. Zamiast to liczyć, pójde sobie na piwko :-)