RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 1994, том 6, выпуск 1, страницы 83–99 (Mi dm618)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

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

В. А. Ватутин


Аннотация: Для файла $\mathcal F$, содержащего $n$ записей, помеченных ключами $F_1,\ldots,F_n$, принадлежащими линейно упорядоченному множеству ключей
$$ \mathcal K_m=\{K_j, 1\le j\le m\colon K_1<K_2<\ldots<K_m\} $$
рассматривается перестановка (сортировка) записей $\sigma=\sigma(1)\ldots\sigma(n)$ такая, что
$$ F_{\sigma(1)}\leq F_{\sigma(2)}\le\ldots\le F_{\sigma(n)}, $$
и для любого $i=1,2,\ldots,n-1$ соотношение $F_{\sigma(i)}=F_{\sigma(i+1)}$ влечет неравенство $\sigma(i)<\sigma(i+1)$. В предположении, что ключ $F_i$ для $i$-й записи выбирается случайно и равновероятно из множества ключей $\mathcal K_m$, доказаны предельные теоремы о распределении числа отрезков возрастания в перестановке $\sigma$ при $n,m\to\infty$. Вид этих теорем зависит от асимптотического поведения величины $ne^{-n/m}$ при $n,m\to\infty$.

Полный текст: PDF файл (970 kB)

Англоязычная версия:
Discrete Mathematics and Applications, 1994, 4:1, 31–44

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.2
Статья поступила: 16.02.1993

Образец цитирования: В. А. Ватутин, “Предельные теоремы для числа отрезков возрастания в случайных перестановках, порождаемых алгоритмами сортировки”, Дискрет. матем., 6:1 (1994), 83–99; Discrete Math. Appl., 4:1 (1994), 31–44

Цитирование в формате AMSBIB
\RBibitem{Vat94}
\by В.~А.~Ватутин
\paper Предельные теоремы для числа отрезков возрастания в~случайных перестановках, порождаемых алгоритмами сортировки
\jour Дискрет. матем.
\yr 1994
\vol 6
\issue 1
\pages 83--99
\mathnet{http://mi.mathnet.ru/dm618}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1273235}
\zmath{https://zbmath.org/?q=an:0801.60003}
\transl
\jour Discrete Math. Appl.
\yr 1994
\vol 4
\issue 1
\pages 31--44


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm618
  • http://mi.mathnet.ru/rus/dm/v6/i1/p83

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Д. В. Шуваев, “Вычисление распределения одной комбинаторной статистики, заданной на последовательностях с фиксированным составом знаков”, Матем. вопр. криптогр., 2:3 (2011), 99–109  mathnet  crossref
    2. Chatterjee S. Diaconis P., “A Central Limit Theorem For a New Statistic on Permutations”, Indian J. Pure Appl. Math., 48:4 (2017), 561–573  crossref  isi
    3. В. А. Ватутин, “Асимптотические свойства числа инверсий в раскрашенных деревьях”, Матем. вопр. криптогр., 10:4 (2019), 9–24  mathnet  crossref  mathscinet
  • Дискретная математика
    Просмотров:
    Эта страница:199
    Полный текст:96
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020