اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Expected Number of Distinct Consecutive Patterns in a Random Permutation
49
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $pi_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, we show that the expected number of distinct consecutive patterns in $pi_n$ is $frac{n^2}{2}(1-o(1))$. This exhibits the fact that random permutations pack consecutive patterns near-perfectly.
قيم البحث
اقرأ أيضاً
When considering binary strings, its natural to wonder how many distinct subsequences might exist in a given string. Given that there is an existing algorithm which provides a straightforward way to compute the number of distinct subsequences in a fi
xed string, we might next be interested in the expected number of distinct subsequences in random strings. This expected value is already known for random binary strings where each letter in the string is, independently, equally likely to be a 1 or a 0. We generalize this result to random strings where the letter 1 appears independently with probability $alpha in [0,1]$. Also, we make some progress in the case of random strings from an arbitrary alphabet as well as when the string is generated by a two-state Markov chain.
We determine the average number of distinct subsequences in a random binary string, and derive an estimate for the average number of distinct subsequences of a particular length.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process
, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
Call a permutation $k$-inflatable if the sequence of its tensor products with uniform random permutations of increasing lengths has uniform $k$-point pattern densities. Previous work has shown that nontrivial $k$-inflatable permutations do not exist
for $k geq 4$. In this paper, we derive a general formula for the limit densities of patterns in the sequence of tensor products of a fixed permutation with each permutation from a convergent sequence. By applying this result, we completely characterize $3$-inflatable permutations and find explicit examples of $3$-inflatable permutations with various lengths, including the shortest examples with length $17$.
We settle the existence of certain anti-magic cubes using combinatorial block designs and graph decompositions to align a handful of small examples.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
