Permutacja z nietypowym dodatkowym warunkiem

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Balduran
Użytkownik
Użytkownik
Posty: 58
Rejestracja: 17 wrz 2004, o 23:03
Płeć: Mężczyzna
Podziękował: 3 razy
Pomógł: 13 razy

Permutacja z nietypowym dodatkowym warunkiem

Post autor: Balduran »

Kolega wysłał mi takie zadanie z kombinatoryki, i jestem w kropce:
Ile jest takich permutacji zbioru {a,A,b,B,c,C,d,D}, aby mała litera stała przed dużą (niekoniecznie obok) np. acdDbBAC?
Jedyny mój pomysł to rozpisać wszystkie możliwe ustawienia typu (m- mała litera, d- duża)
mmddmmdd, mdmdmdmd, itp., które są dozwolone (wiadomo że m nie może być na ostatnim miejscu i że np. jeśli w pierwszych dwóch slotach było md, to w trzecim będzie m itp.), a potem do każdego miejsca dopisywać ile różnych liter może być w danym miejscu, np. dla przypadku:
mmddmmdd
mamy kolejno możliwości
\(\displaystyle{ 4 \cdot 3 \cdot 2 \cdot 1 \cdot 2 \cdot 1 \cdot 2 \cdot 1}\)
Więc wychodzi dla tego ustawienia 96 możliwości. I tak można rozpisać wszystkie po kolei i tak liczyć, trochę można sobie ułatwić korzystając z tego że między przypadkami zachodzą pewne symetrie.
Z tym że takie rozwiązanie po pierwsze wydaje mi się strasznie nieeleganckie, po drugie że to masa roboty. Na maturze nawet nie starczyłoby mi miejsca żeby to wszystko rozpisać. No i wiadomo że w takich opasłych obliczeniach w nerwach i z ograniczoną ilością czasu łatwo się pomylić. Ma ktoś jakiś lepszy pomysł na to zadanko?
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Permutacja z nietypowym dodatkowym warunkiem

Post autor: »

Odpowiedź to:
\(\displaystyle{ \binom 82 \cdot \binom 62 \cdot \binom 42 \cdot \binom 22}\)
Wybieramy po dwa miejsca na parę jednakowych liter, a jak już są dwa miejsca, to wiadomo, że na lewo jest mała litera, a na prawo wielka.

Q.
ODPOWIEDZ