Consecutive patterns in permutations

被引：94

作者：

Elizalde, S

Noy, M

机构：

[1] Univ Politecn Catalunya, Dept Matemat Aplicada 2, Barcelona 08028, Spain

[2] MIT, Dept Math, Cambridge, MA 02139 USA

来源：

ADVANCES IN APPLIED MATHEMATICS | 2003年 / 30卷 / 1-2期

关键词：

D O I：

10.1016/S0196-8858(02)00527-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we study the distribution of the number of occurrences of a permutation Q as a subword among all permutations in S-n. We solve the problem in several cases depending on the shape of sigma by obtaining the corresponding bivariate exponential generating functions as solutions of certain linear differential equations with polynomial coefficients. Our method is based on the representation of permutations as increasing binary trees and on symbolic methods. (C) 2003 Elsevier Science (USA). All rights reserved.

引用

页码：110 / 125

页数：16

共 14 条

[1]

[Anonymous], ADV COMBINATORICS

[2]

[Anonymous], 1983, COMBINATORIAL ENUMER

[3]

Babson E., 2000, Sem. Lothar. Combin., V44, P18

[4] ENUMERATION OF PERMUTATIONS BY RISES, FALLS, RISING MAXIMA AND FALLING MAXIMA [J].

CARLITZ, L ;

SCOVILLE, R .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1974, 25 (3-4) :269-277

[5] Generalized pattern avoidance [J].

Claesson, A .

EUROPEAN JOURNAL OF COMBINATORICS, 2001, 22 (07) :961-971

[6] LIMIT LAWS FOR LOCAL COUNTERS IN RANDOM BINARY SEARCH-TREES [J].

DEVROYE, L .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) :303-315

[7]

Flajolet P, 1997, RANDOM STRUCT ALGOR, V11, P223, DOI 10.1002/(SICI)1098-2418(199710)11:3<223::AID-RSA2>3.0.CO

[8]

2-2

[9] Analytic combinatorics of non-crossing configurations [J].

Flajolet, P ;

Noy, M .

DISCRETE MATHEMATICS, 1999, 204 (1-3) :203-229

[10]

FLAJOLET P, 1998, ANAL COMBINATORICS

← 1 2 →