Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Expected Number of Distinct Consecutive Patterns in a Random Permutation
49
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 fixed 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
