Fundamenta Informaticae - Volume 117, issue 1-4

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