2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение18.09.2010, 14:59 
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!$.
Наверное, и явную формулу найти не сложно. Или хотя бы рекуррентную.

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение18.09.2010, 15:04 
Аватара пользователя
e7e5 в сообщении #353755 писал(а):
Заинтересовал вопрос:
Обозначим $(n,k)$ число перестановок чисел ...

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

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение18.09.2010, 15:28 
Попробую пояснить на примере:
Число перестановок $2$ элементов с одной инверсией равно $1$
Число перестановок$3$ элементов с одной или двумя инверсимями равно $2$
Число перестановок $4$ элементов с одной инверсией равно $3$, с двумя инверсиями $5$, тремя инверсиями равно $6$, и.т.д
Число перестановок $5$ элементов с одной инверсией равно $4$, двумя инверсиями равно $9$ и.т.д

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

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

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

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение18.09.2010, 18:04 
Если $C^2_n$ - нечетно то $(n;(C_n^2-1)/2)=(n;(C_n^2+1)/2)$
Других вариантов нет.

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение18.09.2010, 18:30 
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$ вообще ничего не понял...


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

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение18.09.2010, 20:05 
Аватара пользователя
e7e5 в сообщении #353845 писал(а):
Не понял, если продолжать строить таблицу ( а это крайне лень), то число перестановок шести элементов с семью или восьмью инверсиями равно 101.

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


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

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение18.09.2010, 21:08 
maxal в сообщении #353872 писал(а):
e7e5 в сообщении #353845 писал(а):
Какое следующее число?

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


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

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

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение19.09.2010, 09:26 
Аватара пользователя
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)$.

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение19.09.2010, 20:41 
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
На викепедии нашел описание французской программы. Какую бы работающую версию порекомендовали для скачивания?

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение19.09.2010, 21:07 
Аватара пользователя
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 у нас на форуме.

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение19.09.2010, 21:16 
Числа последовательности 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$

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение19.09.2010, 21:36 
Аватара пользователя
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.

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение24.09.2010, 19:44 
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$

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

 
 
 
 Re: О вычислении числа перестановок для заданной инверсии
Сообщение24.09.2010, 19:50 
Аватара пользователя
e7e5 в сообщении #355863 писал(а):
Вопрос, как выводить результаты в файл?

Перед выполнением дайте командочку типа:
Код:
\l mylogfile.log

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

 
 
 [ Сообщений: 19 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group