Results 1 to 10 of about 48 (48)
The number of distinct adjacent pairs in geometrically distributed words: a probabilistic and combinatorial analysis [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 The analysis of strings of $n$ random variables with geometric distribution has recently attracted renewed interest: Archibald et al. consider the number of distinct adjacent pairs in geometrically distributed words.
Guy Louchard +2 more
doaj +1 more source
A note on limits of sequences of binary trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 We discuss a notion of convergence for binary trees that is based on subtree sizes. In analogy to recent developments in the theory of graphs, posets and permutations we investigate some general aspects of the topology, such as a characterization of the ...
Rudolf Grübel
doaj +1 more source
Bounded affine permutations I. Pattern avoidance and enumeration [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 We introduce a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We study pattern avoidance in bounded affine permutations.
Neal Madras, Justin M. Troyka
doaj +1 more source
Cosine polynomials with few zeros
Bulletin of the London Mathematical Society, Volume 53, Issue 3, Page 877-892, June 2021., 2021 Abstract In a celebrated paper, Borwein, Erdélyi, Ferguson and Lockhart constructed cosine polynomials of the form fA(x)=∑a∈Acos(ax),with A⊆N, |A|=n and as few as n5/6+o(1) zeros in [0,2π], thereby disproving an old conjecture of Littlewood. Here we give a sharp analysis of their constructions and, as a result, prove that there exist examples with as ...
Tomas Juškevičius, Julian Sahasrabudhe
wiley +1 more source
On an alternative sequence comparison statistic of Steele [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 The purpose of this paper is to study a statistic that is used to compare the similarity between two strings, which is first introduced by Michael Steele in 1982.
Ümit Işlak, Alperen Y. Özdemir
doaj +1 more source
EXPECTED MEAN WIDTH OF THE RANDOMIZED INTEGER CONVEX HULL
Mathematika, Volume 67, Issue 2, Page 422-433, April 2021., 2021 Abstract Let K⊂Rd be a convex body, and assume that L is a randomly rotated and shifted integer lattice. Let KL be the convex hull of the (random) points K∩L. The mean width W(KL) of KL is investigated. The asymptotic order of the mean width difference W(λK)−W((λK)L) is maximized by the order obtained by polytopes and minimized by the order for smooth ...
Binh Hong Ngoc, Matthias Reitzner
wiley +1 more source
Expected size of a tree in the fixed point forest [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 We study the local limit of the fixed-point forest, a tree structure associated to a simple sorting algorithm on permutations. This local limit can be viewed as an infinite random tree that can be constructed from a Poisson point process configuration on
Samuel Regan, Erik Slivken
doaj +1 more source
Asymptotic distribution of fixed points of pattern-avoiding involutions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 For a variety of pattern-avoiding classes, we describe the limiting distribution for the number of fixed points for involutions chosen uniformly at random from that class.
Samuel Miner +2 more
doaj +1 more source
Expected Number of Distinct Subsequences in Randomly Generated Binary Strings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 When considering binary strings, it's 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
Yonah Biers-Ariel +2 more
doaj +1 more source
Pattern Avoidance for Random Permutations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 Using techniques from Poisson approximation, we prove explicit error bounds on the number of permutations that avoid any pattern. Most generally, we bound the total variation distance between the joint distribution of pattern occurrences and a ...
Harry Crane, Stephen DeSalvo
doaj +1 more source