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