Zadanie:
Ile jest permutacji \(\displaystyle{ <a_1,a_2,...,a_{2n-1},a_{2n}>}\) zbioru\(\displaystyle{ \{1,2,...,2n-1,2n\}}\), gdzie \(\displaystyle{ n \ge 1}\) takich, że dla każdej liczby \(\displaystyle{ k \in {1,...,n}}\) liczby \(\displaystyle{ 2k-1}\) i \(\displaystyle{ 2k}\) nie stoją obok siebie w ciągu \(\displaystyle{ a_1,a_2,...,a_{2n-1},a_{2n}}\)?
Próbowałem przejść do dopełnienia i użyć wzoru włączeń i wyłączeń, ale wydaje się wtedy zbyt skomplikowane.
permutacje z ograniczeniami
-
kolegasafeta
- Użytkownik
- Posty: 209
- Rejestracja: 26 lis 2009, o 23:45
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 17 razy
- Pomógł: 8 razy
permutacje z ograniczeniami
Ja proponuję tak:
Ustaw sobie liczby (albo indeksy - nieistotne) w ten sposób:
\(\displaystyle{ -2-4-6-8-10-.......-2n-}\), gdzie znak `-` reprezentuje miejsce, w które można dowolną ilość liczb niewykorzystanych w schemacie. Tych miejsc jest \(\displaystyle{ n+1}\).
Teraz tak: wiadomo, że \(\displaystyle{ 1}\) nie może stać koło \(\displaystyle{ 2}\), czyli masz \(\displaystyle{ (n + 1) - 2}\) miejsc, gdzie możesz wstawić \(\displaystyle{ 1}\). Z pozostałymi liczbami nieparzystymi masz tak samo, a liczb nieparzystych mamy tutaj \(\displaystyle{ n}\). Zatem dla jednego układu liczb parzystych mamy:
\(\displaystyle{ n(n-1)}\).
Z tym, że takich układów liczb parzystych jest: \(\displaystyle{ n!}\). Zatem ostateczny wynik wynosi:
\(\displaystyle{ n! \cdot n(n-1)}\).
Pozdrawiam -- 14 wrz 2013, o 15:04 --Mała poprawka, w takiej jednej przerwie `_` można umieścić \(\displaystyle{ n-2}\) różnych liczb w różnym porządku, co komplikuje mój model do tego stopnia, że raczej staje się on bezużyteczny w tym zadaniu. Wybacz - było późno, jak pisałem moje rozwiązanie.
Ustaw sobie liczby (albo indeksy - nieistotne) w ten sposób:
\(\displaystyle{ -2-4-6-8-10-.......-2n-}\), gdzie znak `-` reprezentuje miejsce, w które można dowolną ilość liczb niewykorzystanych w schemacie. Tych miejsc jest \(\displaystyle{ n+1}\).
Teraz tak: wiadomo, że \(\displaystyle{ 1}\) nie może stać koło \(\displaystyle{ 2}\), czyli masz \(\displaystyle{ (n + 1) - 2}\) miejsc, gdzie możesz wstawić \(\displaystyle{ 1}\). Z pozostałymi liczbami nieparzystymi masz tak samo, a liczb nieparzystych mamy tutaj \(\displaystyle{ n}\). Zatem dla jednego układu liczb parzystych mamy:
\(\displaystyle{ n(n-1)}\).
Z tym, że takich układów liczb parzystych jest: \(\displaystyle{ n!}\). Zatem ostateczny wynik wynosi:
\(\displaystyle{ n! \cdot n(n-1)}\).
Pozdrawiam -- 14 wrz 2013, o 15:04 --Mała poprawka, w takiej jednej przerwie `_` można umieścić \(\displaystyle{ n-2}\) różnych liczb w różnym porządku, co komplikuje mój model do tego stopnia, że raczej staje się on bezużyteczny w tym zadaniu. Wybacz - było późno, jak pisałem moje rozwiązanie.