Abrakadabra ale inaczej

Hyuuga Neji · Post autor: **Hyuuga Neji** » 24 kwie 2008, o 22:57

Ile jest takich permutacji słowa ABRAKADABRA, że żadne dwie sąsiednie litery nie są identyczne?

Mam problem z tym zadaniem, wiem że liczy sie je banalnie ze wzoru na permutacje z powtórzeniami tylko że jest jeden problem ... w rozwiązaniu nie moge użyć tego wzoru, zadanie ma być rozwiązane zasadą włączeń i wyłączeń. Rozwiązywałem niedawno podobne zadanie ze słowem MATEMATYK, było o tyle proste że litery powtarzały sie tylko 2 razy. W słowei abrakadabra powtarzająsie więcej niż 2 razy i trzeba coś pewnie zauważyć albo dopisac. Szukałem rozwiązania wszędzie i poddaje sie, jeśli ktoś wie jak je rozwiązać piszcie:)

maruda · Post autor: **maruda** » 28 kwie 2008, o 22:41

Mnie przyszło do głowy, żeby zacząć od A. Jest ich 5, mamy je wstawić na któreś z 11 miejsc. Można to zrobić na 4 sposoby:
1) A ... A (i na początku, i na końcu, pozostałe gdzieś w środku)
2) A ... ~A (na początku, ale nie na końcu)
3) ~A ... A (na końcu, ale nie na początku)
4) ~A ... ~A (na początku i na końcu nie będzie A)
W ostatnim przypadku sprawa jest prosta, bo na 9 miejsc, wykluczając sąsiedztwo, można te litery wstawić tylko na jeden sposób. Pomiędzy nimi będą 4 przerwy plus jedno miejsce wolne na początku i jedno na końcu, czyli 6 niestykających się ze sobą, co wyklucza wszelkie sąsiedztwo następnych dodawanych liter.
Ilości rozwiązań sytuacji 2) i 3) jest tyle samo, więc wystarczy rozpatrzyć jedną. Odpadają dwa już zaklepane miejsca plus to obok A, czyli na 8 miejsc mamy wstawić 4 A. Na to są dwa sposoby z "pojedynczymi" (jednomiejscowymi) przerwami: A_A_A_A_ i _A_A_A_A oraz trzy sposoby z jedną "podwójną" przerwą: A_ _A_A_A, A_A_ _A_A, A_A_A_ _A. Tu się zaczynają schody, bo trzeba powykluczać sąsiedztwo następnych dodawanych liter dla każdego sposobu, czego tu robić nie będę, bo akurat nie mam cierpliwości, a i miejsca to pewnie trochę by zajęło.
W sytuacji 1) jest kłopotów najwięcej, bo na 11-4=7 miejsc trzeba wstawić 3 litery A...
Rozpisywać tego nie będę z wymienionych już powodów Zapodałam jedynie ideę.

Hyuuga Neji · Post autor: **Hyuuga Neji** » 30 kwie 2008, o 23:37

dzieki za rozwiązanie, nie dokońca o to mi chodziło ale pomysł jest dobry. spróbuje jeszcze nad tym posiedziec moze cos mi wyjdzie