Ilość ustawień liczb w ciąg

dexter257 · Post autor: **dexter257** » 15 paź 2010, o 12:02

Na ile sposobów da się ustawić z liczb \(\displaystyle{ 1,2,3,4,5}\) ciąg długości \(\displaystyle{ 10}\), by każda liczba występowała
\(\displaystyle{ 2}\) razy i żadne dwie takie same liczby nie stały w ciągu obok siebie.

Mój pomysł był następujący:

Wylosować liczbę spośród danych pięciu, a następnie znaleźć dla niej \(\displaystyle{ 2}\) miejsca w ciągu, wybierając na
\(\displaystyle{ {10\choose 2} - 9}\) sposobów (wszystkie możliwe ustawienia - te, gdzie liczby stoją obok siebie.
Potem można wziąć kolejną z 4 pozostałych liczb i powtórzyć proces dla ciągu \(\displaystyle{ 8}\)-elementowego, ale jest problem. Gdy już (powiedzmy jedynki) zajmują dwa miejsca w ciągu, pojęcie "stania obok siebie" jest inne niż dla ciągu nie zapełnionego jeszcze żadnymi liczbami. Np, w ciągu \(\displaystyle{ (1[][][][][][][][]1)}\) kolejne 2 liczby można ustawić, analog. jak poprzednim razem, na \(\displaystyle{ {8\choose 2} - 7}\) sposobów, ale dla ciągu \(\displaystyle{ (1[][][]1[][][][][])}\) to rozumowanie się psuje. Stąd też taka metoda do niczego mnie nie doprowadzi.

Prosiłbym o jakieś wskazówki odnośnie tego zadania. Próbuję ugryźć to zadanie z różnych stron, ale ciągle ląduję w tym samym miejscu.

abc666 · Post autor: **abc666** » 15 paź 2010, o 16:16

Można by zrobić tak. Mamy \(\displaystyle{ \frac{8!}{2!2!2!2!}}\) wszystkich możliwych ustawień liczb \(\displaystyle{ \{1,1,2,2,3,3,4,4\}}\). Część z tych ustawień jest dobra, część zła. Dodatkowo tą część która jest zła możemy podzielić na takie które da się "naprawić" wstawiając dwie piątki oraz takie których się nie da. Policzmy ile jest takich których się nie da naprawić. Są to takie sytuacje:
1. Mamy 4 pary liczb stojących koło siebie np
\(\displaystyle{ 11332244}\)
Takich ustawień jest \(\displaystyle{ 4!}\)

2.Mamy 3 pary liczb stojących koło siebie a dwie pozostałe nie stoją obok siebie. Ile jest takich sytuacji możemy policzyć tak:
Ustawiamy 3 pary, a następnie pomiędzy paru (lub na brzegach) wstawiamy dwie pozostałe. Takich możliwości jest
\(\displaystyle{ 4\cdot {4 \choose 2}}\) (wybieramy, którą z liczb nie będzie w parze, a potem wybieramy dwa miejsca dla nich)

Czyli odpowiedzią do zadania jest liczba możliwości wstawienia 5-tek do ciągu 8 elementów minus nienaprawialne sytuacje. Czyli
\(\displaystyle{ \left( \frac{8!}{2!2!2!2!} -4!- 4\cdot {4 \choose 2}\right) \cdot {9 \choose 2}=179712}\)

Na razie nie widzę luki w swoim rozumowaniu. Ale niech ktoś jeszcze sprawdzi.

dexter257 · Post autor: **dexter257** » 15 paź 2010, o 17:08

Ustawiamy 3 pary, a następnie pomiędzy paru (lub na brzegach
) wstawiamy dwie pozostałe. Takich możliwości jest \(\displaystyle{ 4\cdot {4 \choose 2}}\) (wybieramy, którą z liczb nie będzie w parze, a potem wybieramy dwa miejsca dla nich)

A nie powinno być \(\displaystyle{ 4\cdot {4 \choose 2}\cdot 3!}\) ? Mamy \(\displaystyle{ 3}\) pary, które mogą stać w dowolnej kolejności.

abc666 · Post autor: **abc666** » 15 paź 2010, o 18:47

Tak racja.

mat_61 · Post autor: **mat_61** » 15 paź 2010, o 20:11

abc666 wypisałeś dwa warianty "nienaprawialne" poprzez losowe umieszczenie piątek w dwóch z dziewięciu możliwych miejsc. Oczywiście zgadzam się, że np. trzech "par" nie da się rozdzielić za pomocą dwóch piątek.

Ale pozostają jeszcze warianty gdzie są dwie "pary" i jedna "para". Te warianty są niestety, tylko "potencjalnie naprawialne" tzn. układ spełni warunki zadania w sytuacji gdy dwa spośród wybranych miejsc do "włożenia" piątek znajdą się w odpowiednim miejscu. Np. taki układ dwóch "par" (jak i każdy inny):

\(\displaystyle{ xxAAxBBx}\)

ulegnie "naprawie" tylko wtedy jeżeli piątki znajdą się w konkretnych miejscach:

\(\displaystyle{ xxA5AxB5Bx}\)

natomiast pozostanie układem nie spełniającym warunków jeżeli piątki znajdą się w innych miejscach np. w takich:

\(\displaystyle{ 5x5xAAxBBx}\) lub takich: \(\displaystyle{ xxAAxB5B5x}\)

Czyli dobrym wariantem jest tylko jeden spośród \(\displaystyle{ {9 \choose 2}}\) możliwych.

Podobna sytuacja jest dla układów z jedną "parą". Np. taki układ:

\(\displaystyle{ xxxxAAxx}\)

może się "zmienić" na taki:

\(\displaystyle{ xx5xxA5Axx}\) lub taki: \(\displaystyle{ xx5x5xAAxx}\)

abc666 · Post autor: **abc666** » 15 paź 2010, o 20:21

Tak. Masz racje :-p Mam to nawet na kartce ale jak zacząłem pisać rozwiązanie to zapomniałem o tym.

mat_61 · Post autor: **mat_61** » 15 paź 2010, o 20:41

Mam taki pomysł na rozwiązanie, żeby policzyć ilość możliwości dla zdarzenie przeciwnego, tzn.

Na ile sposobów da się ustawić z liczb 1,2,3,4,5 ciąg długości 10, by każda liczba występowała
2 razy i co najmniej dwie takie same liczby stały obok siebie:

Wówczas należałoby zsumować ilości możliwości dla wariantów:

A: wszystkie pięć "par" jest razem:

5!

B: cztery pary są razem:

- wybieramy cztery pary z pięciu (kombinacja)
- rozmieszczamy te pary w szeregu (permutacja)
- dla pozostałych dwóch liczb wybieramy dwa spośród pięciu miejsc (kombinacja)

\(\displaystyle{ C^{4}_{5} \cdot 4! \cdot C^{2}_{5}}\)

C: trzy pary razem:

- wybieramy trzy pary z pięciu (kombinacja)
- rozmieszczamy te pary w szeregu (permutacja)
- dla pierwszej z pozostałych dwóch par wybieramy dwa spośród 4 miejsc (kombinacja)
- dla drugiej z pozostałych dwóch par wybieramy dwa spośród 6 miejsc (kombinacja)

\(\displaystyle{ C^{3}_{5} \cdot 3! \cdot C^{2}_{4} \cdot C^{2}_{6}}\)

Analogicznie dla pozostałych wariantów:

D: dwie pary razem:

\(\displaystyle{ C^{2}_{5} \cdot 2! \cdot C^{2}_{3} \cdot C^{2}_{5} \cdot C^{2}_{7}}\)

E: jedna para razem:

\(\displaystyle{ C^{1}_{5} \cdot 1! \cdot C^{2}_{2} \cdot C^{2}_{4} \cdot C^{2}_{6} \cdot C^{2}_{8}}\)

Wskazana byłaby krytyczna analiza powyższego rozwiązania.
Oczywiście na koniec należy tą wartość odjąć od ilości wszystkich możliwych ciągów, czyli:

\(\displaystyle{ \frac{10!}{2^{5}}}\)

dexter257 · Post autor: **dexter257** » 16 paź 2010, o 11:28

C: trzy pary razem:

- wybieramy trzy pary z pięciu (kombinacja)
- rozmieszczamy te pary w szeregu (permutacja)
- dla pierwszej z pozostałych dwóch par wybieramy dwa spośród 4 miejsc (kombinacja)
- dla drugiej z pozostałych dwóch par wybieramy dwa spośród 6 miejsc (kombinacja)

A nie powinniśmy wcześniej wybrać tę parę? Co przemnożyłoby wynik przez 2 ? Analogicznie dla reszty przypadków.

mat_61 · Post autor: **mat_61** » 16 paź 2010, o 11:43

Wg mnie nie, bo wtedy wynik należałoby podzielić przez dwa, bo jeżeli mamy np. taki układ po ustawieniu razem trzech par (znakiem "-" oznaczyłem te miejsca gdzie można "dostawiać" kolejne elementy):

\(\displaystyle{ -AA-BB-CC-}\)

i mamy dodać elementy x;x;y;y, to wybierając parę x;x i ustawiając ją np. tak:

\(\displaystyle{ -AA-x-BB-x-CC-}\)

a następnie parę y;y i ustawiając np. tak:

\(\displaystyle{ \textcolor{red}{-AA-x y BB-x-CC y}}\)

mamy taki sam układ jak przy wyborze najpierw pary y;y i jej ustawieniu tak:

\(\displaystyle{ -AA-y-BB-CC-y-}\)

a następnie pary x;x i ustawieniu jej tak:

\(\displaystyle{ \textcolor{red}{-AAxy-BB x CC-y-}}\)

Czyli taki układ byłby policzony dwukrotnie (układy oznaczone na czerwono są jak widać takie same).

Wg mnie dowolna kolejność wyboru kolejnych "zestawów" do rozmieszczania pomiędzy istniejące pary uwzględnia wszystkie możliwe wyniki.