Избранные перестановки на конечном упорядоченном множестве.

[democrateur]

На конечном упорядоченном множестве $n$ отличных элементов осуществляется одна перестановка, переводящая первичный порядок во вторичный, в результате которой каждый элемент меняет позицию. Вопрос заключается в числе вариантов $V_n$ осуществления этой единственной перестановки, меняющей первичный порядок множества на вторичный.

Есть такой ответ: $V_n=[\frac{n!}{e}+\frac{1}{2}]$ , тут [ ] – целая часть числа, или, иначе говоря: $\frac{n!}{e}$ переходит в $V_n$ при точном целом приближении.

Есть другой ответ: $V_n=\frac{n!}{e}+\frac{(-1)^n}{n+2} \pm O(\frac{1}{(n+2)^2})$ .

Хотелось бы доказать.


* Работает для:

n = 1; Множество {1}. Изменить положение элементов нельзя.

$V_1=[\frac{1!}{e}+\frac{1}{2}]=0$,

$V_1=0=\frac{1!}{e}-\frac{1}{3} \pm O(\frac{1}{9})$ ;


n = 2; Множество {12}. Изменить положение элементов можно лишь одним способом: {21}.

$V_2=[\frac{2!}{e}+\frac{1}{2}]=1$,

$V_2=1=\frac{2!}{e}+\frac{1}{4} \pm O(\frac{1}{16})$ ;


n = 3; Множество {123}. Изменить положение можно двумя способоми: {231} и {312}.

$V_3=[\frac{3!}{e}+\frac{1}{2}]=2$,

$V_3=2=\frac{3!}{e}-\frac{1}{5} \pm O(\frac{1}{25})$ ;


n = 4; Множество {1234}. Изменить положение можно 9 способоми: {2143}, {2341}, {2413}, {3142}, {3412}, {3421}, {4123}, {4312} и {4321}.

$V_4=[\frac{4!}{e}+\frac{1}{2}]=9$,

$V_4=9=\frac{4!}{e}+\frac{1}{6} \pm O(\frac{1}{36})$ ;


n = 5; Множество {12345}. Изменить положение можно 44 способоми: перебрать на листке минут за 5–10 не составит труда.

$V_5=[\frac{5!}{e}+\frac{1}{2}]=44$,

$V_5=44=\frac{5!}{e}-\frac{1}{7} \pm O(\frac{1}{49})$ ;


** Для: n = 0; Множество {} пустое. Вопрос открытый, поскольку значения $V_0$ "кажутся" разными:

$V_0=[\frac{0!}{e}+\frac{1}{2}]=0$,

$V_0=\frac{0!}{e}+\frac{1}{2} \pm O(\frac{1}{4})=1$ ;

Переставлять при n = 0 вроде бы нечего, но и при одной воображаемой перестановке "ничего" в "ничём" ни у кого из ничего не возникнет проблем пересечений со своим первичным положением.


*** Кроме того, любопытно, что $V_n$ можно представить как $(n-1) \cdot z$ где $z \in Z$ :
$V_1 = 0 = (1-1)$ ;
$V_2 = 1 = (2-1) \cdot 1$ ;
$V_3 = 2 = (3-1) \cdot 1$ ;
$V_4 = 9 = (4-1) \cdot 3$ ;
$V_5 = 44 = (5-1) \cdot 11$ ;
$V_6 = 265 = (6-1) \cdot 53$ ;
$V_7 = 1854 = (7-1) \cdot 3 \cdot 103$ ;
$V_8 = 14 \ 833 = (8-1) \cdot 13 \cdot 163$ ;
$V_9 = 133 \ 496 = (9-1) \cdot 11 \cdot 37 \cdot 41$ ;
$V_{10} = 1 \ 334 \ 961 = (10-1) \cdot 3^2 \cdot 16 \ 481$ и т.д.

[wrest]

democrateur
Такая перестановка называется беспорядком, а их количество - субфакториалом (и обозначается так: $!n$).
См. например Википедию (там и асимптотические формулы есть, в т.ч. ваша). [url]https://ru.wikipedia.org/wiki/Беспорядок_(перестановка)[/url] и [url]https://ru.wikipedia.org/wiki/Субфакториал[/url]

Ещё много свойств, формул и фактов об этом: A000166

[democrateur]

Спасибо!

-- 20.11.2019, 11:26 --

Что вы думаете о количестве беспорядков в пустом множестве?
Их там нет, или там один беспорядок?

[wrest]

democrateur в сообщении #1426868 писал(а):

Что вы думаете о количестве беспорядков в пустом множестве?
Их там нет, или там один беспорядок?

Помойму это вопрос соглашений, так же как с факториалом нуля.

[democrateur]

wrest в сообщении #1426869 писал(а):

democrateur в сообщении #1426868 писал(а):

Что вы думаете о количестве беспорядков в пустом множестве?
Их там нет, или там один беспорядок?

Помойму это вопрос соглашений, так же как с факториалом нуля.

Ясно, что соглашения. Локализация абсурда.
Ну, по идее, если число перестановок порядка в пустом множестве равно одному. Т.е. $0!=1$, или, что можно устроить порядок ничего в ничём лишь одним способом. То тогда, продолжая логику, количество беспорядков, которые можно устроить из ничего в ничём тоже должно быть единицей, т.е. $!0=1$.

О. У немцев нашёл:
http://de.wikipedia.org/wiki/Subfakult%C3%A4t

[Aritaborian]

wrest в сообщении #1426869 писал(а):

Помойму это вопрос соглашений, так же как с факториалом нуля.

Кто-то считает, что факториал нуля это вопрос соглашения, а кто-то считает, что без этого гамма-функцию фиг определишь...

[arseniiv]

wrest в сообщении #1426869 писал(а):

Помойму это вопрос соглашений, так же как с факториалом нуля.

Значение факториала нуля — не вопрос соглашений. Это единица ровно по определению: существует ровно одна биекция из пустого множества в пустое. Субфакториалом потому тоже будет единица, потому что любой элемент пустого множества она переводит в отличный.

-- Ср ноя 20, 2019 18:14:39 --

Странно, что обычно у людей не возникает вопросов, сколько сочетаний из нуля по ноль: все смотрят на треугольник Паскаля и говорят «1», а между тем это число нульэлементных подмножеств пустого множества.

[wrest]

Виноградов, Математическая энциклопедия


Терминологические споры беспощадные, я самоустраняюсь :)

[mihaild]

arseniiv в сообщении #1426918 писал(а):

Это единица ровно по определению: существует ровно одна биекция из пустого множества в пустое.

wrest в сообщении #1426921 писал(а):

Терминологические споры беспощадные

Есть несколько эквивалентных определений. Например:
1. Факториал - функция $\mathbb{N} \to \mathbb{N}$, такая что $f(0) = 1$, $f(n + 1) = (n + 1) \cdot f(n)$. Тогда $f(0) = 1$ именно из определения. Правда если определять иначе - будет неудобно.
2. $n!$ - число биекций на $n$-элементном множестве. Отсюда автоматически $0! = 1$.
3. $n! = \Gamma(n + 1)$. Отсюда опять же автоматически $0! = 1$.
Но вообще вопрос о том, прописано ли в определении явно значение для нуля, или нет, мне тоже не кажется интересным. Считать факториал и субфакториал нуля чем-то отличным от $1$ - в любом случае очень странная идея.

[arseniiv]

Вместо (1) кстати можно определять факториал как $\prod_{a=1}^n a$, значение в нуле делегируется произведению, которое тоже для пустого множества определять иначе чем 1 очень странно.

wrest в сообщении #1426921 писал(а):

Терминологические споры беспощадные, я самоустраняюсь :)

Интересно, сами начали и потом «устраняюсь».

[wrest]

arseniiv в сообщении #1426928 писал(а):

Интересно, сами начали и потом «устраняюсь».

Сорри. Я написал вам длинный ответ. Но стёр. Кратко: да, вы правы, по определению. Но ноль (в случае Гаммы - единица) оговаривается отдельно. Это и есть "соглашение". Это пояснение, почему я использовал слово "соглашение". Но я не настаиваю.
Уже всё было:
«Факториал нуля»

[arseniiv]

(Оффтоп)

wrest
Не, всё нормально, правда та тема не из лучших, потому что целую первую страницу Sicker себя ведёт, ну, как он любит себя вести. Сейчас вспомним, что там было на остальных…

UPD: потом там было успокоение FomaNeverov, потом бред Levy, потом Sicker’а доводили до понимания пустой функции полторы страницы… В общем тема-то хорошая тем, что все основные вещи приведены, но в ПРР её поминать немного опасно, потому что там есть и бардак. Хотя в удачном случае этот бардак наоборот заострит ум («почему там ошибки? ах вот почему!»), но всё равно риск.