Generalized stack permutations

被引：9

作者：

Atkinson, MD ^{[1
]}

机构：

[1] Sch Math & Computat Sci, St Andrews KY16 9SS, Fife, Scotland

来源：

COMBINATORICS PROBABILITY & COMPUTING | 1998年 / 7卷 / 03期

关键词：

D O I：

10.1017/S096354839800354X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Stacks which allow elements to be pushed into any of the top r positions and popped from any of the top s positions are studied. An asymptotic formula for the number u(n) of permutations of length n sortable by such a stack is found in the cases r = 1 or s = 1. This formula is found from the generating function of u(n). The sortable permutations are characterized if r = 1 or s = 1 or r = s = 2 by a forbidden subsequence condition.

引用

页码：239 / 246

页数：8

共 9 条

[1]

ATKINSON MD, 1992, TR210 CARL U SCH COM

[2]

BOSE P, 1993, LECT NOTES COMPUTER, V709, P200

[3]

KEZDY AE, 1996, J COMB THEORY, V74, P353

[4]

KNUTH DE, 1973, FUNDAMENTAL ALGORITH, V1

[5]

PRATT VR, 1973, P ACM S THEOR COMP, V5, P268

[6]

Simion R., 1985, European J. Combin., V6, P383, DOI 10.1016/S0195-6698(85)80052-4

[7] FORBIDDEN SUBSEQUENCES [J].

STANKOVA, ZE .

DISCRETE MATHEMATICS, 1994, 132 (1-3) :291-316

[8] SORTING USING NETWORKS OF QUEUES AND STACKS [J].

TARJAN, R .

JOURNAL OF THE ACM, 1972, 19 (02) :341-&

[9] GENERATING TREES AND THE CATALAN AND SCHRODER NUMBERS [J].

WEST, J .

DISCRETE MATHEMATICS, 1995, 146 (1-3) :247-262

← 1 →