Wyniki wyszukiwania - BazTech

Ograniczanie wyników

5 Fundamenta Informaticae

5 2012

Znaleziono wyników: 5

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: lattice paths

Sortuj według:

Ogranicz wyniki do:

On Families of Weakly Cross-intersecting Set-pairs

Kiraly Z., Nagy Z. L., Palvölgyi D., Visontai M.

Fundamenta Informaticae

2012

Vol. 117, nr 1-4

189-198

Let F be a family of pairs of sets. We call it an (a, b)-set system if for every set-pair (A,B) in F we have that |A| = a, |B| = b, and A∩B = ∅. Furthermore, F is weakly crossintersecting if for any (Ai,Bi), (Aj ,Bj) ∈ F 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.

Generating Functions of Embedded Trees and Lattice Paths

Kuba M.

Fundamenta Informaticae

2012

Vol. 117, nr 1-4

215-227

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.

Bijective Counting of Involutive Baxter Permutations

Fusy E.

Fundamenta Informaticae

2012

Vol. 117, nr 1-4

179-188

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...[formula], a formula originally discovered by M. Bousquet-Melou 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.

A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths

Kotek T., Makowsky J. A.

Fundamenta Informaticae

2012

Vol. 117, nr 1-4

199-213

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 Precursive (holonomic) sequences in terms of counting certain lattice paths.

A Lattice Path Combinatorial Approach to Rothe Numbers and Related Convolution Results

Panny W.

Fundamenta Informaticae

2012

Vol. 117, nr 1-4

265-277

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.