Liczba permutacji z warunkiem na sąsiednie wyrazy

[Majeskas]

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?

[Gouranga]

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}}\)

[norwimaj]

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}\))

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.

Natomiast dalsza część wzoru, tzn. \(\displaystyle{ a_{n-2},}\) jest dla mnie niezrozumiała.

[Gouranga]

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]

\(\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

[Majeskas]

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]

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!

[a4karo]

A możesz doprecyzować: każdych dwóch sąsiednich? pewnych dwóch sąsiednich?

[arek1357]

Nie rozumiem

[a4karo]

Nie rozumiem

Liczysz porządek \(\displaystyle{ (1,2,3,4,5,6,7)}\) czy nie? w końcu \(\displaystyle{ 1+2\neq 7}\)

[Majeskas]

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 --

Nie rozumiem

Liczysz porządek \(\displaystyle{ (1,2,3,4,5,6,7)}\) czy nie? w końcu \(\displaystyle{ 1+2\neq 7}\)

Tak, w tej permutacji żadne dwa kolejne wyrazy nie sumują się do \(\displaystyle{ 7}\), czyli taką permutację wliczamy do naszego zbioru \(\displaystyle{ A}\).

-- 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 --

\(\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

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}\).

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]

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:

Pozostaje\(\displaystyle{ (n-2i)}\) elementów do permutacji

a permutujemy ze sobą tak naprawdę \(\displaystyle{ n-i}\) - elementów

[Majeskas]

Masz rację, dzięki.

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.

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.