Discrete Mathematics & Theoretical Computer Science |
We study a recurrence relation, originating in combinatorial problems, where the generating function, as a formal power series, satisfies a differential equation that can be solved in a suitable domain; this yields an analytic function in a domain, but the solution is singular at the origin and the generating function has radius of convergence 0. Nevertheless, the solution to the recurrence can be obtained from the analytic solution by finding an asymptotic series expansion. Conversely, the analytic solution can be obtained by summing the generating function by the Borel summation method. This is an explicit example, which we study detail, of a behaviour known to be typical for a large class of holonomic functions. We also express the solution using Bessel functions and Lommel polynomials.
Motivated by the recent refutation of information loss paradox in black hole by Hawking, we investigate the new concept of {\it non unitary random walks}. In a non unitary random walk, we consider that the state 0, called the {\it black hole}, has a probability weight that decays exponentially in $e^{-\lambda t}$ for some $\lambda>0$. This decaying probabilities affect the probability weight of the other states, so that the the apparent transition probabilities are affected by a repulsion factor that depends on the factors $\lambda$ and black hole lifetime $t$. If $\lambda$ is large enough, then the resulting transition probabilities correspond to a neutral random walk. We generalize to {\it non unitary gravitational walks} where the transition probabilities are function of the distance to the black hole. We show the surprising result that the black hole remains attractive below a certain distance and becomes repulsive with an exactly reversed random walk beyond this distance. This effect has interesting analogy with so-called dark energy effect in astrophysics.
We consider a general concept of composition and decomposition of objects, and discuss a few natural properties one may expect from a reasonable choice thereof. It will be demonstrated how this leads to multiplication and co-multiplication laws, thereby providing a generic scheme furnishing combinatorial classes with an algebraic structure. The paper is meant as a gentle introduction to the concepts of composition and decomposition with the emphasis on combinatorial origin of the ensuing algebraic constructions.
We give a new expression for the expected number of inversions in the product of n random adjacent transpositions in the symmetric group S_{m+1}. We then derive from this expression the asymptotic behaviour of this number when n scales with m in various ways. Our starting point is an equivalence, due to Eriksson et al., with a problem of weighted walks confined to a triangular area of the plane.
For 3 different versions of q-tangent resp. q-cotangent functions, we compute the continued fraction expansion explicitly, by guessing the relative quantities and proving the recursive relation afterwards. It is likely that these are the only instances with a ''nice'' expansion. Additional formulae of a similar type are also provided.
Following a question of J. Cooper, we study the expected number of occurrences of a given permutation pattern q in permutations that avoid another given pattern r. In some cases, we find the pattern that occurs least often, (resp. most often) in all r-avoiding permutations. We also prove a few exact enumeration formulae, some of which are surprising.
Asymptotics of the variances of many cost measures in random digital search trees are often notoriously messy and involved to obtain. A new approach is proposed to facilitate such an analysis for several shape parameters on random symmetric digital search trees. Our approach starts from a more careful normalization at the level of Poisson generating functions, which then provides an asymptotically equivalent approximation to the variance in question. Several new ingredients are also introduced such as a combined use of the Laplace and Mellin transforms and a simple, mechanical technique for justifying the analytic de-Poissonization procedures involved. The methodology we develop can be easily adapted to many other problems with an underlying binomial distribution. In particular, the less expected and somewhat surprising n (logn)(2)-variance for certain notions of total path-length is also clarified.
Using the saddle point method, we obtain from the generating function of the Stirling numbers of the first kind [n j] and Cauchy's integral formula, asymptotic results in central and non-central regions. In the central region, we revisit the celebrated Goncharov theorem with more precision. In the region j = n - n(alpha); alpha > 1/2, we analyze the dependence of [n j] on alpha.
A decomposable combinatorial structure consists of simpler objects called components which by thems elves cannot be further decomposed. We focus on the multi-set construction where the component generating function C(z) is of alg-log type, that is, C(z) behaves like c + d(1 -z/rho)(alpha) (ln1/1-z/rho)(beta) (1 + o(1)) when z is near the dominant singularity rho. We provide asymptotic results about the size of thes mallest components in random combinatorial structures for the cases 0 < alpha < 1 and any beta, and alpha < 0 and beta=0. The particular case alpha=0 and beta=1, the so-called exp-log class, has been treated in previous papers. We also provide similar asymptotic estimates for combinatorial objects with a restricted pattern, that is, when part of its factorization patterns is known. We extend our results to include certain type of integers partitions. partitions
We prove generating function identities producing fast convergent series for the sequences beta(2n + 1); beta(2n + 2) and beta(2n + 3), where beta is Dirichlet's beta function. In particular, we obtain a new accelerated series for Catalan's constant convergent at a geometric rate with ratio 2(-10); which can be considered as an analog of Amdeberhan-Zeilberger's series for zeta(3)
We find the asymptotic number of 2-orientations of quadrangulations with n inner faces, and of 3-orientations of triangulations with n inner vertices. We also find the asymptotic number of prime 2-orientations (no separating quadrangle) and prime 3-orientations (no separating triangle). The estimates we find are of the form c . n(-alpha)gamma(n), for suitable constants c, alpha, gamma with alpha = 4 for 2-orientations and alpha = 5 for 3-orientations. The proofs are based on singularity analysis of D-finite generating functions, using the Fuchsian theory of complex linear differential equations.
Let X(1),X(2),...,X(n) be independent, identically distributed uniform random variables on [0, 1]. We can observe the outcomes sequentially and must select online at least r of them, and, moreover, in expectation at least mu >= r. Here mu need not be integer. We see X(k) as the cost of selecting item k and want to minimize the expected total cost under the described combined (r, mu)-constraint. We will see that an optimal selection strategy exists on the set S(n) of all selection strategies for which the decision at instant k may depend on the value X(k), on the number N(k) of selections up to time k and of the number n - k of forthcoming observations. Let sigma(r,mu)(n) be the corresponding S(n)-optimal selection strategy and v(r,mu)(n) its value. The main goal of this paper is to determine these and to understand the limiting behavior of v(r,mu)(n). After discussion of the specific character of this combination of two types of constraints we conclude that the S(n)-problem has a recursive structure and solve it in terms of a double recursion. Our interest will then focus on the limiting behavior of nv(r,mu)(n) as n -> infinity. This sequence converges and its limit allows for the interpretation of a normalized limiting cost L (r, mu) of the (r, mu)-constraint. Our main result is that L(r, mu) = g(r) ((mu - r)(2)/(2)) where g(r) is the r(th) iterate of the function g(x) = 1 + x + root 1 + 2x. Our motivation to study mixed-constraints problems is indicated by several […]
We contribute to combinatorics and algorithmics of words by introducing new types of periodicities in words. A tiling period of a word w is partial word u such that w can be decomposed into several disjoint parallel copies of u, e.g. a lozenge b is a tiling period of a a b b. We investigate properties of tiling periodicities and design an algorithm working in O(n log (n) log log (n)) time which finds a tiling period of minimal size, the number of such minimal periods and their compact representation. The combinatorics of tiling periods differs significantly from that for classical full periods, for example unlike the classical case the same word can have many different primitive tiling periods. We consider also a related new type of periods called in the paper multi-periods. As a side product of the paper we solve an open problem posted by T. Harju (2003).
Cellular automata are usually associated with synchronous deterministic dynamics, and their asynchronous or stochastic versions have been far less studied although significant for modeling purposes. This paper analyzes the dynamics of a two-dimensional cellular automaton, 2D Minority, for the Moore neighborhood (eight closest neighbors of each cell) under fully asynchronous dynamics (where one single random cell updates at each time step). 2D Minority may appear as a simple rule, but It is known from the experience of Ising models and Hopfield nets that 2D models with negative feedback are hard to study. This automaton actually presents a rich variety of behaviors, even more complex that what has been observed and analyzed in a previous work on 2D Minority for the von Neumann neighborhood (four neighbors to each cell) (2007) This paper confirms the relevance of the later approach (definition of energy functions and identification of competing regions) Switching to the Moot e neighborhood however strongly complicates the description of intermediate configurations. New phenomena appear (particles, wider range of stable configurations) Nevertheless our methods allow to analyze different stages of the dynamics It suggests that predicting the behavior of this automaton although difficult is possible, opening the way to the analysis of the whole class of totalistic automata
This paper presents the first distributional analysis of both, a parking problem and a linear probing hashing scheme with buckets of size b. The exact distribution of the cost of successful searches for a b alpha-full table is obtained, and moments and asymptotic results are derived. With the use of the Poisson transform distributional results are also obtained for tables of size m and n elements. A key element in the analysis is the use of a new family of numbers, called Tuba Numbers, that satisfies a recurrence resembling that of the Bernoulli numbers. These numbers may prove helpful in studying recurrences involving truncated generating functions, as well as in other problems related with buckets.
Following the model of Bondesson, Nilsson, and Wikstrand, we consider randomly filled urns, where the probability of falling into urn i is the geometric probability (1-q)qi-1. Assuming n independent random entries, and a fixed parameter k, the interest is in the following parameters: Let T be the smallest index, such that urn T is non-empty, but the following k are empty, then: XT= number of balls in urn T, ST= number of balls in urns with index larger than T, and finally T itself..
We construct explicit solutions of a number of Stieltjes moment problems based on moments of the form ${\rho}_{1}^{(r)}(n)=(2rn)!$ and ${\rho}_{2}^{(r)}(n)=[(rn)!]^{2}$, $r=1,2,\dots$, $n=0,1,2,\dots$, \textit{i.e.} we find functions $W^{(r)}_{1,2}(x)>0$ satisfying $\int_{0}^{\infty}x^{n}W^{(r)}_{1,2}(x)dx = {\rho}_{1,2}^{(r)}(n)$. It is shown using criteria for uniqueness and non-uniqueness (Carleman, Krein, Berg, Pakes, Stoyanov) that for $r>1$ both ${\rho}_{1,2}^{(r)}(n)$ give rise to non-unique solutions. Examples of such solutions are constructed using the technique of the inverse Mellin transform supplemented by a Mellin convolution. We outline a general method of generating non-unique solutions for moment problems generalizing ${\rho}_{1,2}^{(r)}(n)$, such as the product ${\rho}_{1}^{(r)}(n)\cdot{\rho}_{2}^{(r)}(n)$ and $[(rn)!]^{p}$, $p=3,4,\dots$.