О вычислении числа перестановок для заданной инверсии

[e7e5]

Заинтересовал вопрос:
Обозначим $(n,k)$ число перестановок чисел $1, 2, ..., n$, каждая из которых содержит ровно $k$ инверсий.

Число перестановок $i$ элементов, $i=1, 2, ..., n$
с $k_i$ или $k_{i-1}$ инверсиями равно $N_i$
Что можно сказать о числах $N_i$? ( например до $n=10$)

[VAL]

e7e5 в сообщении #353755 писал(а):

Заинтересовал вопрос:
Обозначим $(n,k)$ число перестановок чисел $1, 2, ..., n$, каждая из которых содержит ровно $k$ инверсий.

Число перестановок $i$ элементов, $i=1, 2, ..., n$
с $k_i$ или $k_{i-1}$ инверсиями равно $N_i$
Что можно сказать о числах $N_i$? ( например до $n=10$)

Процитирую Профессора Снэйпа:

Цитата:

Читал, размышлял, ничего не понял...

Вначале Вы вводите числа $(n,k)$, а затем спрашиваете про какие-то $N_i$, которые внятно не введены.

Про числа $(n,k)$ можно утверждать, например следующее:
$(n,0) =(n, C_n^2) = 1$;
$\sum_{k=0}^{\frac{n(n-1)}2}(n,k)=n!$.
Наверное, и явную формулу найти не сложно. Или хотя бы рекуррентную.

[AKM]

e7e5 в сообщении #353755 писал(а):

Заинтересовал вопрос:
Обозначим $(n,k)$ число перестановок чисел ...

Заинтересовал вопросик: зачем вводить обозначение, которое потом не используется?
Ну а с буквой $i$ вообще ничего не понял...

[e7e5]

Попробую пояснить на примере:
Число перестановок $2$ элементов с одной инверсией равно $1$
Число перестановок$3$ элементов с одной или двумя инверсимями равно $2$
Число перестановок $4$ элементов с одной инверсией равно $3$, с двумя инверсиями $5$, тремя инверсиями равно $6$, и.т.д
Число перестановок $5$ элементов с одной инверсией равно $4$, двумя инверсиями равно $9$ и.т.д

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

В приведенном примере при $n=3$: число перестановк трех элементов с двумя или тремя инверсиями равно $2$

Естественно перебирать не хочется. Где еще подобные эффекты в таблице чисел встретятся?

[Null]

Если $C^2_n$ - нечетно то $(n;(C_n^2-1)/2)=(n;(C_n^2+1)/2)$
Других вариантов нет.

[e7e5]

Null в сообщении #353829 писал(а):

Если $C^2_n$ - нечетно то $(n;(C_n^2-1)/2)=(n;(C_n^2+1)/2)$
Других вариантов нет.

Не понял, если продолжать строить таблицу ( а это крайне лень), то число перестановок шести элементов с семью или восьмью инверсиями равно 101.

Какое следующее число?

-- Сб сен 18, 2010 19:39:09 --

AKM в сообщении #353766 писал(а):

Заинтересовал вопросик: зачем вводить обозначение, которое потом не используется?
Ну а с буквой $i$ вообще ничего не понял...

Теперь я не могу уже исправить исходный пост, прихолится давать пояснения

[maxal]

e7e5 в сообщении #353845 писал(а):

Не понял, если продолжать строить таблицу ( а это крайне лень), то число перестановок шести элементов с семью или восьмью инверсиями равно 101.

Какое следующее число?

Таблица приведена в A008302. А все искомые $n\equiv 2,3\pmod{4}$ - для них средние элементы соответствующего ряда таблицы равны.

[e7e5]

maxal в сообщении #353872 писал(а):

e7e5 в сообщении #353845 писал(а):

Какое следующее число?

Таблица приведена в A008302. А все искомые $n\equiv 2,3\pmod{4}$ - для них средние элементы соответствующего ряда таблицы равны.

Получается ряд чисел: $2, 101, 573, 250749, $

maxal , а как вы поняли, что все искомые так находятся?
И как собственно следующее число в ряду найти? Могли бы привести пример?

[maxal]

e7e5 в сообщении #353881 писал(а):

maxal , а как вы поняли, что все искомые так находятся?

Для этого нужно доказать три свойства числа $T(n,k)$ перестановок с $k$ инверсиями:

• $T(n,k)$ принимает ненулевые значения для $0\leq k\leq \frac{n(n-1)}{2}$
• $T(n,k) = T(n,\frac{n(n-1)}{2}-k)$
• $T(n,k)$ возрастает при $0\leq k \leq \frac{n(n-1)}{4}$

Отсюда следует, что равные значения возможны тогда и только тогда, когда $\frac{n(n-1)}{2}$ нечётно, то есть, при $n\equiv 2,3\pmod{4}$. Причём при таком $n$ равные значения даются $T(n,\frac{n(n-1)-2}{4}) = T(n,\frac{n(n-1)+2}{4})$.

e7e5 в сообщении #353881 писал(а):

И как собственно следующее число в ряду найти? Могли бы привести пример?

Например, на PARI/GP так:

? T(n,m) = polcoeff( prod(k=1,n-1, (1-x^(k+1) + O(x^(m+1)))/(1-x) ), m      );
? for(n=1,40, if(n%4==2 || n%4==3, print1(T(n,(n*(n-1)-2)/4),", ") ))
1, 2, 101, 573, 250749, 2409581, 3727542188, 50626553988, 190418421447330, 3344822488498265, 24965661442811799655, 538134522243713149122, 7016726879654720868145951, 179258893496663655603046622, 3741163513205099419577155249749, 110520062557960229937518882573780, 3463861806507747133152591395448445166, 116168034299493079570776886639370348862, 5208610500144919495844659270116658786563011, 195497593731392734506873788376896938168104207, 

-- Sun Sep 19, 2010 01:34:38 --

Это, кстати, подпоследовательность последовательности A000140, дающей максимальное количество перестановок с фиксированным количеством инверсий, то есть, $T(n,\left\lfloor \frac{n(n-1)}4\right\rfloor)$.

[e7e5]

maxal в сообщении #353930 писал(а):

Отсюда следует, что равные значения возможны тогда и только тогда, когда $\frac{n(n-1)}{2}$ нечётно, то есть, при $n\equiv 2,3\pmod{4}$. Причём при таком $n$ равные значения даются $T(n,\frac{n(n-1)-2}{4}) = T(n,\frac{n(n-1)+2}{4})$.

Пытаюсь разобраться. Таблицу все-таки рисую. В ней действительно справа происходит заполнение нулями.
1) А вот доказательство равенства $T(n,k) = I(n,\frac{n(n-1)}{2}-k)$ не ясно совсем.
2) Также не понятен план доказательства:
$T(n,k)$ возрастает при $0\leq k \leq \frac{n(n-1)}{4}$
В моей таблице это видно, числа в строке $n$ возрастают, потом уменьшаются, потом идут нули.
Например
$n=4$
$1, 3, 5, 6, 5, 3, 1, 0, 0,$

3) как отсюда следует $n\equiv 2,3\pmod{4}$. Пожалуйста поясните в учебных целях.

-- Вс сен 19, 2010 21:46:33 --

maxal в сообщении #353930 писал(а):

Например, на PARI/GP так:

? T(n,m) = polcoeff( prod(k=1,n-1, (1-x^(k+1) + O(x^(m+1)))/(1-x) ), m      );
? for(n=1,40, if(n%4==2 || n%4==3, print1(T(n,(n*(n-1)-2)/4),", ") )) 

Поясните пожалуйста код программы. Первый раз встречаю PARI/GP
На викепедии нашел описание французской программы. Какую бы работающую версию порекомендовали для скачивания?

[maxal]

e7e5 в сообщении #354142 писал(а):

1) А вот доказательство равенства $T(n,k) = I(n,\frac{n(n-1)}{2}-k)$ не ясно совсем.

Замените каждый элемент $i$ перестановки на $n+1-i$.

e7e5 в сообщении #354142 писал(а):

2) Также не понятен план доказательства:
$T(n,k)$ возрастает при $0\leq k \leq \frac{n(n-1)}{4}$
В моей таблице это видно, числа в строке $n$ возрастают, потом уменьшаются, потом идут нули.
Например
$n=4$
$1, 3, 5, 6, 5, 3, 1, 0, 0,$

Нули рассматривать не нужно. Для $n=4$ индекс $k$ меняется от $0$ до $\frac{n(n-1)}2=6$, что дает ряд $1, 3, 5, 6, 5, 3, 1$, причем до середины он возрастает, а потом в виду симметрии убывает.

e7e5 в сообщении #354142 писал(а):

3) как отсюда следует $n\equiv 2,3\pmod{4}$. Пожалуйста поясните в учебных целях.

Это в точности, когда число $\frac{n(n-1)}2$ является нечетным, и поэтому в ряду $T(n,k)$ чётное количество элементов. Два средних в виду опять же симметрии должны быть равны.

e7e5 в сообщении #354142 писал(а):

Поясните пожалуйста код программы. Первый раз встречаю PARI/GP
На викепедии нашел описание французской программы. Какую бы работающую версию порекомендовали для скачивания?

См. Интерактивный курс: введение в программирование на PARI/GP у нас на форуме.

[e7e5]

Числа последовательности A000140 - числа Кендель-Мана ( по-русски так?): максимальное число перестановок $n$ элементов, имеющих такое же число инверсий.
$\begin{array}{l} 1, 1, 2, 6, 22, 101, 573, 3836, 29228, 250749, 2409581, 25598186, 296643390,\\ 3727542188, 50626553988, 738680521142, 11501573822788, 190418421447330,\\ 3344822488498265, 62119523114983224, 1214967840930909302 \end{array}$

Что то не понял определение этих чисел:
"Kendall-Mann numbers: the maximum number of permutations on n letters having the same number of inversions"

По таблице:
$n=1$, $k=0$, $1$
$n=2$, $k=1$, $1$
$n=3$, $k=2$, $2$
$n=4$, $k=3$, $6$
$n=5$, $k=5$, $22$
$n=6$, $k=7$, $101$

[maxal]

e7e5 в сообщении #354155 писал(а):

Что то не понял определение этих чисел:
"Kendall-Mann numbers: the maximum number of permutations on n letters having the same number of inversions"

Как я уже сказал выше, это просто $T(n,\left\lfloor \frac{n(n-1)}4\right\rfloor)$ в наших обозначениях, то есть средний (или один из двух средних) элементов каждой строки таблицы A008302.

[e7e5]

maxal в сообщении #353930 писал(а):

Например, на PARI/GP так:

? T(n,m) = polcoeff( prod(k=1,n-1, (1-x^(k+1) + O(x^(m+1)))/(1-x) ), m      );
? for(n=1,40, if(n%4==2 || n%4==3, print1(T(n,(n*(n-1)-2)/4),", ") ))
1, 2, 101, 573, 250749, 2409581, 3727542188, 50626553988, 190418421447330, 3344822488498265, 24965661442811799655, 538134522243713149122, 7016726879654720868145951, 179258893496663655603046622, 3741163513205099419577155249749, 110520062557960229937518882573780, 3463861806507747133152591395448445166, 116168034299493079570776886639370348862, 5208610500144919495844659270116658786563011, 195497593731392734506873788376896938168104207, 

По этому коду получил следующее в ряду число
$12070083447251883445035445745339207218984319722494$

Вопрос, как выводить результаты в файл? По справочной системе не очень понял, вернее идут ошибки..

[maxal]

e7e5 в сообщении #355863 писал(а):

Вопрос, как выводить результаты в файл?

Перед выполнением дайте командочку типа:

\l mylogfile.log

Тогда все, что печатается на экране, будет также сваливаться в файл mylogfile.log