Liczba permutacji z warunkiem na sąsiednie wyrazy
-
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
Ile jest permutacji zbioru \(\displaystyle{ \left\{ 1,2,\ldots,n\right\}}\), w których suma sąsiednich wyrazów jest różna od \(\displaystyle{ n+1}\).
Przychodzi mi do głowy jedynie brutalne użycie zasady włączeń i wyłączeń. Jeśli \(\displaystyle{ A}\) oznacza szukany zbiór permutacji, to
\(\displaystyle{ S_n\setminus A=\left\{\textrm{permutacje, w których występują obok siebie }1\textrm{ i }n\right\}\cup}\)
\(\displaystyle{ \cup\left\{\textrm{permutacje, w których występują obok siebie }2\textrm{ i }n-1\right\}\cup\ldots\cup}\)
\(\displaystyle{ \cup\left\{\textrm{permutacje, w których występują obok siebie }n\textrm{ i }1\right\}}\)
Moc zbioru \(\displaystyle{ S_n\setminus A}\) można policzyć z zasady włączeń i wyłączeń, co nie jest specjalnie eleganckie. A jak inaczej?
Przychodzi mi do głowy jedynie brutalne użycie zasady włączeń i wyłączeń. Jeśli \(\displaystyle{ A}\) oznacza szukany zbiór permutacji, to
\(\displaystyle{ S_n\setminus A=\left\{\textrm{permutacje, w których występują obok siebie }1\textrm{ i }n\right\}\cup}\)
\(\displaystyle{ \cup\left\{\textrm{permutacje, w których występują obok siebie }2\textrm{ i }n-1\right\}\cup\ldots\cup}\)
\(\displaystyle{ \cup\left\{\textrm{permutacje, w których występują obok siebie }n\textrm{ i }1\right\}}\)
Moc zbioru \(\displaystyle{ S_n\setminus A}\) można policzyć z zasady włączeń i wyłączeń, co nie jest specjalnie eleganckie. A jak inaczej?
-
- Użytkownik
- Posty: 1591
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 246 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
można się zastanowić nad zależnością reukencyjną
na pierwszej pozycji ustawiamy dowolną z \(\displaystyle{ n}\) liczb
na drugiej jedną z \(\displaystyle{ n-2}\) (bo jedna odpada, ta, która dałaby sumę \(\displaystyle{ n+1}\))
na reszcie miejsc ustawiamy również dowolnie
stąd bierze się \(\displaystyle{ a_n = n\cdot (n-2) \cdot a_{n-2}}\)
do takiej rekurencji potrzebujemy jeszcze rozbiegówki w postaci dwóch początkowych wyrazów:
\(\displaystyle{ a_2 = 0}\)
\(\displaystyle{ a_3 = 3}\)
dla \(\displaystyle{ a_1}\) nie określamy wartości bo zbiór musi mieć co najmniej \(\displaystyle{ 2}\) elementy żeby móc mieć dwa sąsiednie elementy
ostatecznie mamy \(\displaystyle{ \begin{cases}
a_2 = 0\\
a_3 = 3\\
a_n = n(n-2)a_{n-2}\end{cases}}\)
na pierwszej pozycji ustawiamy dowolną z \(\displaystyle{ n}\) liczb
na drugiej jedną z \(\displaystyle{ n-2}\) (bo jedna odpada, ta, która dałaby sumę \(\displaystyle{ n+1}\))
na reszcie miejsc ustawiamy również dowolnie
stąd bierze się \(\displaystyle{ a_n = n\cdot (n-2) \cdot a_{n-2}}\)
do takiej rekurencji potrzebujemy jeszcze rozbiegówki w postaci dwóch początkowych wyrazów:
\(\displaystyle{ a_2 = 0}\)
\(\displaystyle{ a_3 = 3}\)
dla \(\displaystyle{ a_1}\) nie określamy wartości bo zbiór musi mieć co najmniej \(\displaystyle{ 2}\) elementy żeby móc mieć dwa sąsiednie elementy
ostatecznie mamy \(\displaystyle{ \begin{cases}
a_2 = 0\\
a_3 = 3\\
a_n = n(n-2)a_{n-2}\end{cases}}\)
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
Niech \(\displaystyle{ n=5}\) i załóżmy, że najpierw wybrałeś liczbę \(\displaystyle{ 3}\). W drugim kroku jednak mamy cztery, a nie trzy możliwości.Gouranga pisze: na pierwszej pozycji ustawiamy dowolną z \(\displaystyle{ n}\) liczb
na drugiej jedną z \(\displaystyle{ n-2}\) (bo jedna odpada, ta, która dałaby sumę \(\displaystyle{ n+1}\))
Natomiast dalsza część wzoru, tzn. \(\displaystyle{ a_{n-2},}\) jest dla mnie niezrozumiała.
-
- Użytkownik
- Posty: 1591
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 246 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
dobra pomysł do kosza, bo przecież podciągi musiałyby też zawierać kolejne liczby a tak nie będzie, przepraszam za wprowadzenie w błąd.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
\(\displaystyle{ x=\sum_{i=1}^{p}(-1)^{i+1} {p \choose i}(2!)^i(n-i)!}\)
gdzie:
\(\displaystyle{ p= \left\lfloor \frac{n}{2} \right\rfloor}\)
Jest to ilość możliwości, że przynajmniej jedna para jest koło siebie
do warunku zadania wystarczy zapisać:
\(\displaystyle{ n!-x}\) - to wynik
Sprawdzałem dla \(\displaystyle{ n=2,3,4,5}\) - działa
gdzie:
\(\displaystyle{ p= \left\lfloor \frac{n}{2} \right\rfloor}\)
Jest to ilość możliwości, że przynajmniej jedna para jest koło siebie
do warunku zadania wystarczy zapisać:
\(\displaystyle{ n!-x}\) - to wynik
Sprawdzałem dla \(\displaystyle{ n=2,3,4,5}\) - działa
-
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
Zgadza się (wszystko to trzeba jeszcze odjąć od \(\displaystyle{ n!}\)). Takie rozwiązanie otrzymuje się właśnie, robiąc to tak, jak proponowałem, poprzez zasadę włączeń i wyłączeń. Kiedy to napisałem, wydawało mi się, że będzie jakoś żmudnie, ale potem zobaczyłem, że właściwie to nie.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
Też chciałem to zrobić inaczej bo nie za bardzo lubię zasadę włączeń i wyłączeń ale nie mam pomysłu na nic innego!
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
Liczysz porządek \(\displaystyle{ (1,2,3,4,5,6,7)}\) czy nie? w końcu \(\displaystyle{ 1+2\neq 7}\)arek1357 pisze:Nie rozumiem
-
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
Może faktycznie na upartego powinienem dopisać: "(…) w których żadne dwa kolejne wyrazy nie sumują się do \(\displaystyle{ n+1}\)". Jakoś wydawało mi się to oczywiste, bo chyba jedyna inna interpretacja to "(…) w których pewne dwa kolejne wyrazy nie sumują się \(\displaystyle{ n+1}\)", a ona nie prowadzi do zbyt ciekawego zadania kombinatorycznego.
-- 12 lutego 2015, 23:12 --
-- 12 lutego 2015, 23:18 --
Tfu! Oczywiście sumują się, bo jest para \(\displaystyle{ (3,4)}\). Przepraszam za zamieszanie, moje niedopatrzenie! Tym niemniej chyba - jako założyciel tematu - wyjaśniłem wątpliwości. Inna interpretacja jest bez sensu.
-- 16 lutego 2015, 13:57 --
Takich przecięć jest \(\displaystyle{ {p\choose i}}\). W każdym z nich musimy wybrać \(\displaystyle{ i}\) z \(\displaystyle{ n-i}\) miejsc dla wszystkich par, następnie na \(\displaystyle{ 2^i}\) sposobów ustalamy kolejność w każdej z nich. Pozostaje \(\displaystyle{ (n-2i)}\) elementów, które możemy rozstawić na \(\displaystyle{ (n-2i)!}\) sposobów. Zatem
\(\displaystyle{ x=\sum_{i=1}^p(-1)^{i+1}{p\choose i}{n-i\choose i}2^i(n-2i)!}\)
\(\displaystyle{ x=-\sum_{i=1}^p(-2)^i{p\choose i}\frac{(n-i)!}{i!}}\)-- 16 lutego 2015, 14:00 --Powinno być: \(\displaystyle{ x=\left| \bigcup_{k=1}^pX_{k,n+1-k}\right|}\).
-- 12 lutego 2015, 23:12 --
Tak, w tej permutacji żadne dwa kolejne wyrazy nie sumują się do \(\displaystyle{ 7}\), czyli taką permutację wliczamy do naszego zbioru \(\displaystyle{ A}\).a4karo pisze:Liczysz porządek \(\displaystyle{ (1,2,3,4,5,6,7)}\) czy nie? w końcu \(\displaystyle{ 1+2\neq 7}\)arek1357 pisze:Nie rozumiem
-- 12 lutego 2015, 23:18 --
Tfu! Oczywiście sumują się, bo jest para \(\displaystyle{ (3,4)}\). Przepraszam za zamieszanie, moje niedopatrzenie! Tym niemniej chyba - jako założyciel tematu - wyjaśniłem wątpliwości. Inna interpretacja jest bez sensu.
-- 16 lutego 2015, 13:57 --
Jednak nie do końca mi się to zgadza. Będę się trzymał Twoich oznaczeń. Niech \(\displaystyle{ X_{s,t}}\) oznacza zbiór wszystkich permutacji, w których \(\displaystyle{ s}\) stoi obok \(\displaystyle{ j}\) (w dowolnej kolejności). Wówczas \(\displaystyle{ x=\bigcup_{k=1}^pX_{k,n+1-k}}\). Chcemy zastosować zasadę włączeń i wyłączeń, opiszmy więc przecięcie \(\displaystyle{ i}\) zbiorów postaci \(\displaystyle{ X_{s,t}}\), gdzie \(\displaystyle{ 1\le i\le p}\).arek1357 pisze:\(\displaystyle{ x=\sum_{i=1}^{p}(-1)^{i+1} {p \choose i}(2!)^i(n-i)!}\)
gdzie:
\(\displaystyle{ p= \left\lfloor \frac{n}{2} \right\rfloor}\)
Jest to ilość możliwości, że przynajmniej jedna para jest koło siebie
do warunku zadania wystarczy zapisać:
\(\displaystyle{ n!-x}\) - to wynik
Sprawdzałem dla \(\displaystyle{ n=2,3,4,5}\) - działa
Takich przecięć jest \(\displaystyle{ {p\choose i}}\). W każdym z nich musimy wybrać \(\displaystyle{ i}\) z \(\displaystyle{ n-i}\) miejsc dla wszystkich par, następnie na \(\displaystyle{ 2^i}\) sposobów ustalamy kolejność w każdej z nich. Pozostaje \(\displaystyle{ (n-2i)}\) elementów, które możemy rozstawić na \(\displaystyle{ (n-2i)!}\) sposobów. Zatem
\(\displaystyle{ x=\sum_{i=1}^p(-1)^{i+1}{p\choose i}{n-i\choose i}2^i(n-2i)!}\)
\(\displaystyle{ x=-\sum_{i=1}^p(-2)^i{p\choose i}\frac{(n-i)!}{i!}}\)-- 16 lutego 2015, 14:00 --Powinno być: \(\displaystyle{ x=\left| \bigcup_{k=1}^pX_{k,n+1-k}\right|}\).
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
Tak ale w Twoim wzorze dla \(\displaystyle{ n=4}\) wyjdzie możliwości \(\displaystyle{ 20}\) takich, że przynajmniej jedna para jest koło siebie a u mnie wychodzi \(\displaystyle{ 16}\) na piechotę licząc szesnaście jest prawdziwe a nie dwadzieścia!
zobacz: dla \(\displaystyle{ n=4}\)
\(\displaystyle{ (1,2)4,3}\)
\(\displaystyle{ 4,3(1,2)}\)
\(\displaystyle{ (2,1)3,4}\)
\(\displaystyle{ 3,4(2,1)}\)
\(\displaystyle{ (1,3)4,2}\)
\(\displaystyle{ 4,2(1,3)}\)
\(\displaystyle{ (3,1)2,4}\)
\(\displaystyle{ 2,4(3,1)}\)
Jest osiem możliwości, że koło siebie nie stoją wyznaczone pary
Dla \(\displaystyle{ n=5}\)
U Ciebie wynik jest \(\displaystyle{ 84}\) , u mnie \(\displaystyle{ 72}\)
Sprawdzałem na piechotę i powinno wyjść \(\displaystyle{ 72}\) !
Oba się zgadzają tylko dla: \(\displaystyle{ n=2, n=3}\)
Napisałeś, że:
zobacz: dla \(\displaystyle{ n=4}\)
\(\displaystyle{ (1,2)4,3}\)
\(\displaystyle{ 4,3(1,2)}\)
\(\displaystyle{ (2,1)3,4}\)
\(\displaystyle{ 3,4(2,1)}\)
\(\displaystyle{ (1,3)4,2}\)
\(\displaystyle{ 4,2(1,3)}\)
\(\displaystyle{ (3,1)2,4}\)
\(\displaystyle{ 2,4(3,1)}\)
Jest osiem możliwości, że koło siebie nie stoją wyznaczone pary
Dla \(\displaystyle{ n=5}\)
U Ciebie wynik jest \(\displaystyle{ 84}\) , u mnie \(\displaystyle{ 72}\)
Sprawdzałem na piechotę i powinno wyjść \(\displaystyle{ 72}\) !
Oba się zgadzają tylko dla: \(\displaystyle{ n=2, n=3}\)
Napisałeś, że:
a permutujemy ze sobą tak naprawdę \(\displaystyle{ n-i}\) - elementówPozostaje\(\displaystyle{ (n-2i)}\) elementów do permutacji
-
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Liczba permutacji z warunkiem na sąsiednie wyrazy
Masz rację, dzięki.
Błąd w moim rozumowaniu pojawia się w miejscu, w którym nie uwzględniłem, że należy nie tylko wybrać miejsca dla par, ale wskazać, gdzie która para stanie. Wówczas faktycznie, zamiast osobno wybierać miejsca dla par, a potem próbować permutować resztę i pary, lepiej od razu zobaczyć, że mamy do czynienia z \(\displaystyle{ n-i}\) elementami - czasem pojedynczymi, czasem podwójnymi - które trzeba spermutować. Uzyskamy wtedy Twój wzór.Majeskas pisze:
Takich przecięć jest \(\displaystyle{ {p\choose i}}\). W każdym z nich musimy wybrać \(\displaystyle{ i}\) z \(\displaystyle{ n-i}\) miejsc dla wszystkich par, następnie na \(\displaystyle{ 2^i}\) sposobów ustalamy kolejność w każdej z nich. Pozostaje \(\displaystyle{ (n-2i)}\) elementów, które możemy rozstawić na \(\displaystyle{ (n-2i)!}\) sposobów.