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

[Хость]

Задано рекуррентное отношение для нахождение числа инверсий:
$d_{n}=(n-1)\cdot(d_{n-1}+d_{n-2})$,
полученное следующими рассуждениями:
Возьмем множество $\mathbb{N}[1,n]$,
отображение 1 под определенной инверсией будет равным $f(1)=k_1\text{, где } k_1\ne1$;
Фиксируем $k_1$;
Возможны два случая:
1) $f(k_1)=1$;
2) $ f(k_1)\ne1$.
Для первого случая:
$f$ определяет инверсию на множестве $\mathbb{N}[1,n]\setminus\{1,k_1\}$.
число подобных инверсий будет равным $d_{n-2}$.
Для второго случая:
$\exists k_0 \in \mathbb{N}[1,n]\setminus\{1,k_1\}: f(k_0)=1$;
определим новую пермутацию (биективное отображение) g на $\mathbb{N}[2,n]$:
$g(k_0)=k_1$;
$g(k)=f(k), \forall k \ne k_0$.
g также является инверсией, но теперь на множестве $\mathbb{N}[2,n]$, число подобных инверсий будет равным $d_{n-1}$.
Из обоих случаев следует, что число инверсий для которых справедливо $f(1)=k_1$, где $k_1$ элемент из $\mathbb{N}[2,n]$ будет равным $d_{n-1}+d_{n-2}$.
Так как $k_1$ может быть выбранно $(n-1)$ способами, то получаем: $d_n=(n-1)\cdot(d_{n-1}+d_{n-2})$.

Вопрос: почему во втором случае исключается повторение первого? Что я упускаю?

Заголовок темы обновлён. Старый заголовок: "число инверсий в перестановке - рекуррентное отношение". // maxal

[george_spbsu]

Я, может, чего не понял... Речь идет об инверсиях или о перестановках? Если об инверсиях - неясно, где вы учитываете инверсии первого элемента в перестановке?

[Dan_Te]

А я, кажется, понял. Инверсией вы называете такую перестановку, при которой ни один элемент не остается на месте.
Второй случай исключает первый, поскольку в первом мы требуем $f(f(1))=f(k_1)=1$, а во втором - $f(f(1))=f(k_1)\ne 1$. Вы же сами это написали!

[george_spbsu]

А я всегда считал инверсией в перестановке - когда больший элемент стоит раньше меньшего...

[xolms]

Есть 5 человек. У каждого есть по подарку. Они дарят их друг другу. Сколько есть возможностей распределения подарков(сам себе подарок дарить нельзя)

[PAV]

Формулой включения-исключения можно посчитать легко

[Руст]

44=20+24. 20 - циклы 3+2, 24=4! циклы длины 5.

[Хорхе]

Руст писал(а):

44=20+24. 20 - циклы 3+2, 24=4! циклы длины 5.

Это если каждый получает ровно по одному подарку, что нигде не сказано. Я думаю, это $4^5=1024$.

[xolms]

Вообще каждому достается по одному.
А если не 5, а N?

[RIP]

Сказано же было, формула включения-исключения.

$$n!+\sum_{k=1}^n(-1)^k\binom nk(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$$

[Kristobal Hunta]

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

[Brukvalub]

Попробуйте применить формулу включений и исключений.

[Kristobal Hunta]

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

[Dan B-Yallay]

Берете число 1. Его нельзя оставлять на месте, а нужно куда-нить сдвинуть. Сколько возможностей у вас имеется?

Число 2 нежелательно оправлять туда, где уже находится единица, и оставлять на месте тоже незя. Сколько возможных вариантов теперь?

А сколько вариантов для числа 3?

.... Продолжаем до исчерпания N.

[Профессор Снэйп]

Dan B-Yallay писал(а):

Берете число 1. Его нельзя оставлять на месте, а нужно куда-нить сдвинуть. Сколько возможностей у вас имеется?

Число 2 нежелательно оправлять туда, где уже находится единица, и оставлять на месте тоже незя. Сколько возможных вариантов теперь?

А сколько вариантов для числа 3?

.... Продолжаем до исчерпания N.

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

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