Fundamenta Informaticae - Volume 117, issue 1-4

Authors: Mohanty, S.G. | Rinaldi, S. | Makowsky, J.

Article Type: Other

DOI: 10.3233/FI-2012-683

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. vii-vii, 2012

Authors: Mohanty, Sri Gopal

Article Type: Research Article

DOI: 10.3233/FI-2012-684

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. viii-ix, 2012

Authors: Archibald, Margaret | Knopfmacher, Arnold | Mansour, Toufik

Article Type: Research Article

Abstract: In this paper we consider the absolute variation statistics of a composition σ = σ1 ··· σm of n which is a measure of the sum of absolute differences between each consecutive pair of parts in a composition. This and some related statistics which we discuss, can also be interpreted within the context of bargraph polygons and bargraph walks of area n. In this context, absolute variation corresponds to the interior vertical perimeter of a bargraph polygon or to the interior vertical length of a bargraph walk.

DOI: 10.3233/FI-2012-685

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 1-17, 2012

Authors: Beaton, Nicholas R. | Flajolet, Philippe | Garoni, Timothy M. | Guttmann, Anthony J.

Article Type: Research Article

Abstract: We study the behaviour of prudent, perimeter and quasi-prudent self-avoiding walks and polygons in both two and three dimensions, as well as some solvable subsets. Our analysis combines exact solutions of some simpler cases, careful asymptotic analysis of functional equations which can be obtained in more complicated cases and extensive numerical studies based on exact series expansions for less tractable cases, augmented by long Monte Carlo runs in some cases.

DOI: 10.3233/FI-2012-686

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 19-33, 2012

Authors: Bilotta, Stefano | Merlini, Donatella | Pergola, Elisa | Pinzani, Renzo

Article Type: Research Article

Abstract: In this paper we study the enumeration and the construction of particular binary words avoiding the pattern 1j+1 0j . By means of the theory of Riordan arrays, we solve the enumeration problem and we give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words and then kills those containing the forbidden pattern.

Keywords: Binary words, pattern avoidance, succession rule, generating tree

DOI: 10.3233/FI-2012-687

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 35-55, 2012

Authors: Blondeau-Fournier, Olivier | Mathieu, Pierre | Welsh, Trevor A.

Article Type: Research Article

Abstract: We first briefly review the role of lattice paths in the derivation of fermionic expressions for the M(p, p′) minimal model characters of the Virasoro Lie algebra. We then focus on the recently introduced half-lattice paths for the M(p, 2p ± 1) characters, reformulating them in such a way that the two cases may be treated uniformly. That the generating functions of these half-lattice paths are indeed M(p, 2p ± 1) characters is proved by describing weight preserving bijections between them and the corresponding RSOS lattice paths. Here, the M(p, 2p − 1) case is derived for the first time. …We then apply the methods of Bressoud and Warnaar to these half-lattice paths to derive fermionic expressions for the Virasoro characters χp,2p±1 1,2 that differ from those obtained from the RSOS paths. This work is based on that presented by the third author at the “7th International Conference on Lattice Path Combinatorics and Applications”, Siena, Italy, July 2010. Show more

DOI: 10.3233/FI-2012-688

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 57-83, 2012

Authors: Bodini, Olivier | Gardy, Danièle | Roussel, Olivier

Article Type: Research Article

Abstract: Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient and easy-to-write algorithms for the random generation of combinatorial objects. This paper proposes to extend Boltzmann generators to a new field of applications by uniformly sampling a Hadamard product. Under an abstract real-arithmetic computation model, our algorithm achieves approximate-size sampling in expected time ${\cal O}$(n${\sqrt n}$) or ${\cal O}$(nσ) depending on the objects considered, with σ the standard deviation of smallest order for the component object sizes. This makes it possible to generate random objects of large size on a standard computer. The analysis heavily …relies on a variant of the so-called birthday paradox, which can be modelled as an occupancy urn problem. Show more

DOI: 10.3233/FI-2012-689

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 85-101, 2012

Authors: Böhm, Walter | Hornik, Kurt

Article Type: Research Article

Abstract: We consider the problem of testing whether r ≥ 2 samples are drawn from the same continuous distribution F(x). The test statistic we will study in some detail is defined as the maximum of the circular differences of the empirical distribution functions, a generalization of the classical 2-sample Kolmogorov-Smirnov test to r ≥ 2 independent samples. For the case of equal sample sizes we derive the exact null distribution by counting lattice paths confined to stay in the scaled alcove ${\cal A}$r of the affine Weyl group Ar−1 . This is done using a generalization of the classical reflection …principle. By a standard diffusion scaling we derive also the asymptotic distribution of the test statistic in terms of a multivariate Dirichlet series. When the sample sizes are not equal the reflection principle no longer works, but we are able to establish a weak convergence result even in this case showing that by a proper rescaling a test statistic based on a linear transformation of the circular differences of the empirical distribution functions has the same asymptotic distribution as the test statistic in the case of equal sample sizes. Show more

Keywords: Kolmogorov-Smirnovtest, lattice path counting, reflection principle, affine Weyl groups, asymptotics distrubution

DOI: 10.3233/FI-2012-690

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 103-125, 2012

Authors: Brennan, Charlotte | Mavhungu, Simon

Article Type: Research Article

Abstract: A Dyck path is a non-negative lattice path in $\mathbb{N}^2$ starting at the origin, where only two types of steps are allowed: the diagonal up step (1, 1) and the diagonal down step (1, −1). The length of the path is the total number of unit steps. We consider paths of length n, ending at the point (n, i). A path is considered to be closed if i = 0 and open if i ≥ 0. This aim of this paper is to find asymptotic expressions for the first and second moments of the number of visits to a certain …level r a Dyck path makes. We investigate open and closed paths separately where we investigate the two different cases r > 0 and r = 0. We use generating functions which are found using recursions. These recursions are solved using matrix algebra. Asymptotic expressions for the expected value and variance are obtained using singularity analysis where the generating functions are expanded around the dominant singularities. Show more

DOI: 10.3233/FI-2012-691

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 127-145, 2012

Authors: Charalambides, Charalambos A.

Article Type: Research Article

Abstract: Consider a queue of particles that are required to cross a field containing a random number of absorption points (traps) acting independently. Suppose that if a particle clashes with (contacts) any of the absorption points, it is absorbed (trapped) with probability p and non absorbed with probability q = 1 − p. Let Xn be the number of absorbed particles from a queue of n particles and Tk the number of particles required to cross the field until the absorption of k particles. Assuming that the number Y of absorption points in the field obeys a q-Poisson distribution …(Heine or Euler distribution), the distributions of Xn and Tk are obtained as q-binomial and q-Pascal distributions, respectively. Inversely, assuming that Xn obeys a q-binomial distribution (or, equivalently, assuming that Tk obeys a q-Pascal distribution), the distribution of Y is obtained as a q-Poisson distribution (Heine or Euler distribution). Show more

Keywords: Absorption distribution, Euler distribution, Heine distribution, Inverse absorption distribution, q-binomial distribution, q-Pascal distribution

DOI: 10.3233/FI-2012-692

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 147-154, 2012

Authors: Chuang, Wan-Chen | Eu, Sen-Peng | Fu, Tung-Shan | Pan, Yeh-Jong

Article Type: Research Article

Abstract: A permutation σ ∈ $\frak{S}_n$ is simsun if for all k, the subword of σ restricted to {1, . . . , k} does not have three consecutive decreasing elements. The permutation σ is double simsun if both σ and σ−1 are simsun. In this paper, we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.

Keywords: Simsun permutation, double-simsun, pattern-avoiding, increasing 1-2 tree

DOI: 10.3233/FI-2012-693

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 155-177, 2012

Authors: Fusy, Éric

Article Type: Research Article

Abstract: We enumerate bijectively the family of involutive Baxter permutations according to various parameters; in particular we obtain an elementary proof that the number of involutive Baxter permutations of size 2n with no fixed points is ${3\cdot2^{n-1}\over (n+1)(n+2)} \big({2n \atop n}\big)$, a formula originally discovered by M. Bousquet-Mélou using generating functions. The same coefficient also enumerates planar maps with n edges, endowed with an acyclic orientation having a unique source, and such that the source and sinks are all incident to the outer face.

Keywords: Bipolar orientations, bijections, planar maps, lattice paths

DOI: 10.3233/FI-2012-694

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 179-188, 2012

Authors: Király, Zoltán | Nagy, Zoltán L. | Pálvölgyi, Dömötör | Visontai, Mirkó

Article Type: Research Article

Abstract: Let ℱ be a family of pairs of sets. We call it an (a, b)-set system if for every set-pair (A,B) in ℱ we have that |A| = a, |B| = b, and A ∩ B = Ø. Furthermore, ℱ is weakly cross-intersecting if for any (Ai , Bi ), (Aj , Bj ) ∈ ℱ with i ≠ j we have that Ai ∩ Bj and Aj ∩ Bi are not both empty. We investigate the maximum possible size of weakly cross-intersecting (a, b)-set systems. We give an explicit construction for the best known asymptotic …lower bound. We introduce a fractional relaxation of the problem and prove that the best known upper bound is optimal for this case. We also provide the exact value for the case when a = b = 2. Show more

Keywords: Cross-intersecting set-pairs, Lattice paths

DOI: 10.3233/FI-2012-695

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 189-198, 2012

Authors: Kotek, Tomer | Makowsky, Johann A.

Article Type: Research Article

Abstract: Using a theorem of N. Chomsky and M. Schützenberger one can characterize sequences of integers which satisfy linear recurrence relations with constant coefficients (C-finite sequences) as differences of two sequences counting words in regular languages. We prove an analog for P-recursive (holonomic) sequences in terms of counting certain lattice paths.

DOI: 10.3233/FI-2012-696

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 199-213, 2012

Authors: Kuba, Markus

Article Type: Research Article

Abstract: Bouttier, Di Francesco and Guitter introduced a method for solving certain classes of algebraic recurrence relations arising the context of maps and embedded trees. The aim of this note is to apply their method, consisting of a suitable ansatz and (computer assisted) guessing, to three problems, all related to the enumeration of lattice paths. First, we derive the generating function of a family of embedded binary trees, unifying some earlier results in the literature. Second, we show that several enumeration problems concerning so-called simple families of lattice paths can be solved without using the kernel method. Third, we use their …method to (re-)derive the length generating function of three vicious walkers and osculating walkers. Show more

Keywords: Embedded trees, Binary Trees, Lattice Paths, Vicious walkers, Osculating walkers

DOI: 10.3233/FI-2012-697

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 215-227, 2012

Authors: Kyriakoussis, Andreas | Vamvakari, Malvina

Article Type: Research Article

Abstract: In this paper, we establish the families of terminating and non-terminating q-Gauss hypergeometric series discrete distributions and we associate them with defined classes of generalized q-Hahn and big q-Jacobi orthogonal polynomials, respectively. Also, we give the q-factorial moments and the usual moments for these two families of q-Gauss hypergeometric series distributions. Moreover, we present their probabilistic interpretation as q-steady-state distributions from Markov chains and we designate the generalized q-Hahn processes and generalized big q-Jacobi processes emerged by these q-Markov chains. As special cases the q-hypergeometric, the negative q-hypergeometric distributions and their inverses are presented.

Keywords: q-Gauss hypergeometric series distributions, q-factorial moments, q-Hahn and big q-Jacobi orthogonal polynomials, Birth-abort-death processes, q-hypergeometric distribution, inverse q-hypergeometric distribution, negative and inverse negative q-hypergeometric distributions, q-Hahn and big q-Jacobi processes

DOI: 10.3233/FI-2012-698

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 229-248, 2012

Authors: Nakano, Fumihiko | Sadahiro, Taizo

Article Type: Research Article

Abstract: This paper studies the dimer model on the dual graph of the square-octagon lattice, which can be viewed as the domino tilings with impurities in some sense. In particular, under a certain boundary condition where only one impurity is contained, we give an exact formula representing the probability of finding an impurity at a given site in a uniformly random dimer configuration in terms of simple random walks on the square lattice.

DOI: 10.3233/FI-2012-699

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 249-264, 2012

Authors: Panny, Wolfgang

Article Type: Research Article

Abstract: Rothe numbers (aka generalized Catalan numbers) have a natural interpretation in terms of lattice paths. Making use of this interpretation this paper aims at showing how some classical convolution identities involving Rothe numbers can also be proved conveniently using lattice path combinatorics.

Keywords: Lattice paths, Rothe numbers, generalized Catalan numbers, Rothe's identity, Hagen-Rothe formula

DOI: 10.3233/FI-2012-700

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 265-277, 2012

Authors: Prodinger, Helmut

Article Type: Research Article

Abstract: Stanley and Callan considered Dyck paths where the lengths of the run to the origin is always odd resp. the last one even, and the other ones odd. These subclasses are also enumerated by (shifted) Catalan numbers. We study the (average) height of these objects, assuming all such Dyck paths of length 2n to be equally likely, and find that it behaves like ~ $\sqrt{\pi n}$, as in the unrestricted case. This classic result for unrestricted Dyck paths is from de Bruijn, Knuth and Rice [2], and to this day, there are no simpler proofs for this, although more general …results have been obtained by Flajolet and Odlyzko [4]. Show more

Keywords: Dyck paths, height, generating functions, asymptotic equivalent

DOI: 10.3233/FI-2012-701

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 279-285, 2012

Authors: Sullivan, Shaun

Article Type: Research Article

DOI: 10.3233/FI-2012-702

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 287-309, 2012

Article Type: Other

Citation: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 311-312, 2012