Liczba permutacji bez rozwiazan lustrzanych/symetrycznych

[randomlogin]

Witam wszystkich na forum, i - jak to zwykle bywa - przyznaje, ze od razu przychodze z pytaniem, na ktore mam nadzieje ktos bedzie tak dobry i udzieli mi odpowiedzi.

(background, mozna pominac)
Zajmuje sie ogolnie zupelnie czym innym, ale przyszlo mi napisac skrypt, ktory bedzie podliczal... w sumie niewazne co. Wydawalo sie to proste jak budowa cepa, wiec bez zastanowienia sie podjalem. Okazalo sie jednak, ze to proste rozwiazanie - jakkolwiek poprawne - przy liczbach jakie beda wchodzily w gre zajmuje za duzo i czasu, i pamieci. Duzo za duzo. Oczywiscie moglbym odpuscic i powiedziec, ze jednak nie da rady - ale ja ambitna bestia jestem, i zaczela sie walka o optymalizacje - na zywym organizmie wprowadzalem iles zupelnie mi obcych do tej pory rozwiazan, i ogolnie programistycznie mnie to rozwinelo (trudno powiedziec po co, bo jak mowilem - zupelnie nie moja dzialka), utknalem jednak na banalnym problemie matematycznym (ktory mialbym pewnie szanse rozwiazac w liceum, ale z przerazeniem stwierdzam, ze bylo to zbyt dawno temu):
(koniec backgroundu)


Majac dany n-elementowy zbior, np \(\displaystyle{ \left \{ A, A, B, B, B \right \}}\) potrzebuje policzyc:
Liczbe jego permutacji, uwzgledniajac powtarzanie sie elementow (do tego miejsca jest to proste, silnia ilosci elementow przez silnie powtorzen kazdego roznego z nich, czyli w przykladzie \(\displaystyle{ \frac{5!}{3! * 2!} = 10}\) ), ale traktujac \(\displaystyle{ AABBB}\) i to samo w odwrotnej kolejnosci \(\displaystyle{ BBBAA}\) jako jedno. Moglbym podzielic przez 2, ale niestety sa ciagi takie jak np \(\displaystyle{ BABAB}\), ktore juz sa tylko raz, wiec musze je odjac przed podzieleniem.

I to niestety mnie pokonalo: jak policzyc liczbe tych ciagow, ktore beda takie same od obu stron? W powyzszym przypadku beda takie dwa, ale nie umiem tego w zaden sposob zgeneralizowac, a google pytane o to zagadanienie atakuje mnie sciana symboli, ktore rownie dobrze moglyby byc zapisem po chinsku - watpie, czy w ogole odpowiadaja na moje pytanie. Gdyby ktos byl w stanie cos podpowiedziec, to bylbym niezmiernie wdzieczny.

[Marian517]

Dzielimy wystąpienie każdego ze znaków na 2, następnie ustawiamy z tego pierwszą połowę ciągu dowolnie, a drugą połowę dopasowujemy do pierwszej na jeden sposób. Jeżeli któryś ze znaków występuje nieparzyście wiele razy to znaczy, że jest w środku. Na przykład jeśli:\(\displaystyle{ \left\{A,A,B,B,B \right\}}\)
Ustawiamy \(\displaystyle{ \left\{A,B \right\}}\) dowolnie, to są 2 sposoby. Potem dokładamy \(\displaystyle{ B}\), a następnie dokładamy pozostałe dwie litery.
Kiedy więcej niż jeden ze znaków występuje nieparzystą liczbę razy to nie ma takich ciągów.

[randomlogin]

Heh, czulem, ze odpowiedz jest prosta - ale nie spodziewalem sie, ze az tak zenujaco oczywista. Zamowie jakas msze pozegnalna dla mojego myslenia. Dzieki wielkie za pomoc.