число беспорядков - рекуррентное отношение

[antbez]

Да, тут, видимо, не простое кол-во перестановок.

[нг]

Профессор Снэйп писал(а):

Допустим, мы "отправили" единицу в тройку. Тогда для двойки будет $N-2$ возможности. А если единицу отправить в двойку, то для двойки окажется $N-1$ возможность

Трудно, но проходимо.

[--mS--]

Kristobal Hunta писал(а):

Я не вижу способа как её применить.

Например, посчитать по формуле включения-исключения число ненужных перестановок - тех, при которых хотя бы один номер совпадает с соответствующим числом.

[bot]

Угу, а потом ещё увидеть разложение $e^{-1}$, чтобы компактизировать ответ.
Это классическая задача о беспорядках.

[Kristobal Hunta]

Понял наконец, как использовать правила включений, исключений. Ответ:

$$ n!-\sum_k^n (-1)^{(k-1)}*C_n^k*(n-k)! $$

Всем спасибо. Что-то я тормозил, позор мне.

[ddn]

Kristobal Hunta писал(а):

Помогите разобраться с такой задачей. Сколькими способами можно пронумеровать натуральне числа от 1 до N так, чтобы ни один номер не совпадал с соответствующим ему числом?

Задачу эту я решал. Приведу вывод формулы (будет много формализма!)

Предв. обозначения
Def: $\overline{n} =\{i|i\in\mathbb{N}\wedge i\leqslant n\}$
сужение отношения $\phi\in A\times B$ на множество аргуметнов $A'\subseteq A$:
$\phi|_{A'}=\{(a,b)|a\in A'\wedge\exists b\in B((a,b)\in \phi)\}$
тождественное отображение на множестве $A$:
Def: $id_A=\{(a,a)|a\in A\}$
Если $\phi\in (A\to B)$, $\phi' \in (A' \to B')$ и $A\cap A'=\{\}$, то объединение отображений будет
$f=\phi\cup\phi' \in(A\cup A' \to B\cup B')$, т.е. такое что $f|_A=\phi$ и $f|_{A'}=\phi'$.

множества отображений из $A$ в $B$ и т.т.:
Def: $(A\to B)=\{C|C\subseteq A\times B\wedge \forall a\in A\exists! b\in B((a,b)\in C)\}$
Def: $(A\gets B)=\{C|C\subseteq A\times B\wedge \forall b\in B\exists! a\in A((a,b)\in C)\}$
Def: $(A\leftrightarrow B)=(A\to B)\cap(A\gets B)$
множество перестановок множества $A$:
Def: $\mathcal{S}(A)=(A\leftrightarrow A)$
их число
$card(\mathcal{S}(A))=card(A)!$
множество перестановок с $k$ неподвижными точками ($0\leqslant k\leqslant N$):
Def: $\mathcal{S}_k(A)=\{\phi|\phi\in\mathcal{S}(A)\wedge card(\{a|a\in A\wedge(\phi(a)=a)\})=k\}$
множество перестановок без неподвижных точек:
Def: $\mathcal{S}_0(A)=\{\phi|\phi\in\mathcal{S}(A)\wedge\forall a\in\A(\phi(a)\not =a)\}$



число перестановок:
Def: $F_k(N)=card(\mathcal{S}_k(\overline{N}))$
искомое же число $F_0(N)$

Очевидно, что $\mathcal{S}_k(\overline{N})=\bigcup\limits_{\begin{array}{c} C\subseteq \overline{N} \\ (card(C)=k) \end{array}}\bigcup\limits_{\phi\in\mathcal{S}_0(\overline{N}/C)} \{\phi\cup id_C\}$

значит $F_k(N)=\sum\limits_{\begin{array}{c} C\subseteq \overline{N} \\ (card(C)=k) \end{array}}\sum\limits_{\phi\in\mathcal{S}_0(\overline{N}/C)} 1=\frac{N!}{k!(N-k)!}\cdot F_0(N-k)$
Учитывая, что $\mathcal{S}(A)=\bigcup\limits_{k=0}^{N}\mathcal{S}_k(A)$ получим $N!=\sum\limits_{k=0}^{N}F_k(N)=\sum\limits_{k=0}^{N}\frac{N!}{k!(N-k)!}\cdot F_0(N-k)$,
откуда уже можно получить рекуррентную формулу
$F_0(N)=N!-\sum\limits_{k=0}^{N-1}\frac{N!}{k!(N-k)!}\cdot F_0(k)$
Но есть формула проще.


Возмем $\psi$ проекцию $\mathcal{S}(\overline{N})$ на $\mathcal{S}(\overline{N-1})$;
определим ее для $\phi\in\mathcal{S}(\overline{N})$ так:
$\psi(\phi)=\{(i,\phi(i))|i\in\overline{N-1}\wedge\phi(i)\not = N\}\cup\{(\phi^{-1}(N),\phi(N))\}=$

$=\phi|_{\overline{N-1}/\{\phi^{-1}(N)\}}\cup\{(\phi^{-1}(N),\phi(N))\}$, при $\phi(N)\not =N$ (тогда и $\phi^{-1}(N)\not =N$ ) и

$\psi(\phi)=\{(i,\phi(i))|i\in\overline{N-1}\}=\phi|_{\overline{N-1}}$, при $\phi(N)=N$
Тогда, фактор-множества аргументов $\phi$ из $\mathcal{S}(\overline{N})$ по одинаковым $\phi'$ из $\mathcal{S}(\overline{N-1})$ будут:
$\psi^{-1}[\phi']=\bigcup\limits_{i=1}^{N-1} \{(\phi|_{\overline{N-1}/\{i\}})\cup\{(i,N),(N,\phi(i))\}\}\cup\{\phi\cup\{(N,N)\}\}$,
разные $\phi$ из одного $\psi^{-1}[\phi']$ отличаются $i$, при котором $\phi(i)=N$.
Значит $card(\psi^{-1}[\phi'])=(N-1)+1=N$

Для $\phi\in\mathcal{S}_0(\overline{N})$ (что дает $\phi^{-1}(N)\not =N\not =\phi(N)$) проекция будет обладать свойством $\psi(\phi)(\phi^{-1}(N))=\phi(N)$ и будет:

$\psi(\phi)\in\mathcal{S}_0(\overline{N-1})$ при $\phi^{-1}(N)\not =\phi(N)$ и
$\psi(\phi)\in\mathcal{S}_1(\overline{N-1})$ при $\phi^{-1}(N)=\phi(N)$

Притом, для $\phi'\in\mathcal{S}_0(\overline{N-1})$ будет
$card(\psi^{-1}[\phi']\cap\mathcal{S}_0(\overline{N}))=N-1$ и $card(\psi^{-1}[\phi']\cap\mathcal{S}_1(\overline{N}))=1$,

а для $\phi'\in\mathcal{S}_1(\overline{N-1})$ будет
$card(\psi^{-1}[\phi']\cap\mathcal{S}_0(\overline{N}))=1$ и $card(\psi^{-1}[\phi']\cap\mathcal{S}_1(\overline{N}))=N-1$,

откуда $F_0(N)=(N-1)\cdot F_0(N-1)+1\cdot F_1(N-1)=(N-1)\cdot (F_0(N-1)+F_0(N-2))$ - рекуррентная формула при начальных условиях $F_0(0)=1$, $F_0(1)=0$, (кто сомневается в значении $F_0(0)=1$, смотрим $F_0(2)=1\cdot (F_0(1)+F_0(0))=1\cdot (1+0)=1$).

С помощью формальных рядов можно найти, что
$F_0(N)=N!\sum\limits_{k=0}^{N}\frac{(-1)^k}{k!}$,
что в ассимтотике дает $F_0(N)\sim\frac{N!}{e}$ (при $N\to\infty$).
Формулу легко проверить по индукции.
Начало индукции:
$F_0(0)=0!\sum\limits_{k=0}^{0}\frac{(-1)^k}{k!}=0!\cdot (1)=1$,
$F_0(1)=1!\sum\limits_{k=0}^{1}\frac{(-1)^k}{k!}=1!\cdot (1-1)=1\cdot 0=0$,
Шаг индукции: пусть верно для $N'<N$ (где $2\leqslant N$), тогда
$F_0(N)=(N-1)\cdot (F_0(N-1)+F_0(N-2))=$
$=(N-1)\cdot\left((N-1)!\sum\limits_{k=0}^{N-1}\frac{(-1)^k}{k!}+(N-2)!\sum\limits_{k=0}^{N-2}\frac{(-1)^k}{k!}\right)=$
$=(N-1)!\cdot\left((N-1)\sum\limits_{k=0}^{N-1}\frac{(-1)^k}{k!}+\sum\limits_{k=0}^{N-2}\frac{(-1)^k}{k!}\right)=$
$=(N-1)!\cdot\left(N\sum\limits_{k=0}^{N-1}\frac{(-1)^k}{k!}-\frac{(-1)^{N-1}}{(N-1)!}\right)=$
$=N!\cdot\left(\sum\limits_{k=0}^{N-1}\frac{(-1)^k}{k!}+\frac{(-1)^N}{N\cdot(N-1)!}\right)=$
$=N!\sum\limits_{k=0}^{N}\frac{(-1)^k}{k!}$ - верно и для $N$.
Значит верно для всех $N$.

[Dan B-Yallay]

Профессор Снэйп писал(а):

Что-то мне сильно не нравится в этом рассуждении.

Допустим, мы "отправили" единицу в тройку. Тогда для двойки будет $N-2$ возможности. А если единицу отправить в двойку, то для двойки окажется $N-1$ возможность

Пойду я учить матчасть

[antbez]

А это случайно не равно субфакториалу n?
$!n=[(n!+1)/e]$

[bot]

Почти - это ближайшее целое к $n!/e$.
Просто посмотрите остаток в разложении $e^{-1}$ и сопоставьте с тем, что ответ должен быть целым. При чётном n округлить надо вверх, а при нечётном - вниз.

[antbez]

Субфакториал nпо определению равен числу перестановок n элементов, при которых ни один элемент не остаётся на своём месте. Тут же подобная задача!

[bot]

Не подобная, а ровно эта задача. Не имел претензий к определению, вызвала сомнение формула - не сообразил сразу, что округление можно выразить таким образом.

[antbez]

Ну вот, значит, я правильно вспомнил!

[TOTAL]

нг писал(а):

Профессор Снэйп писал(а):

Допустим, мы "отправили" единицу в тройку. Тогда для двойки будет $N-2$ возможности. А если единицу отправить в двойку, то для двойки окажется $N-1$ возможность

Трудно, но проходимо.

Ускорить проходимость можно так.
Единицу отправим в

$$k$$

(всего

$$n-1$$

вариантов).
Теперь

$$k$$

отправим в единицу (дает

$$X_{n-2}{$$

вариантов),
либо

$$k$$

отправим не в единицу (дает

$$X_{n-1}{$$

вариантов).
Итого рекуррентная формула

$$X_n=(n-1)(X_{n-1}+X_{n-2})$$

.

[maxal]

Dan_Te в сообщении #3453 писал(а):

Инверсией вы называете такую перестановку, при которой ни один элемент не остается на месте.

Такие перестановки называются беспорядками (derangement)

[AndriyMarevich]

Зачем ещё какое-то рекурентное соотношение, когда, как сказал bot, есть простое решение:
1.[n!/e], если n нечётное
2.[n!/e]+1, если n чётное