Generalised Stack Permutations

Michael David Atkinson

doi:10.1017/S096354839800354X

Generalised Stack Permutations

Michael David Atkinson

School of Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	239-246
Number of pages	8
Journal	Combinatorics, Probability and Computing
Volume	7
Issue number	3
DOIs	https://doi.org/10.1017/S096354839800354X
Publication status	Published - Sept 1998

Access to Document

10.1017/S096354839800354X

Cite this

@article{f8a6ca5d22b648b08f6bf05e7dbf1fdc,

title = "Generalised Stack Permutations",

abstract = "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.",

author = "Atkinson, \{Michael David\}",

year = "1998",

month = sep,

doi = "10.1017/S096354839800354X",

language = "English",

volume = "7",

pages = "239--246",

journal = "Combinatorics, Probability and Computing",

issn = "1469-2163",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - Generalised Stack Permutations

AU - Atkinson, Michael David

PY - 1998/9

Y1 - 1998/9

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0032283257

U2 - 10.1017/S096354839800354X

DO - 10.1017/S096354839800354X

M3 - Article

SN - 1469-2163

VL - 7

SP - 239

EP - 246

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 3

ER -

Generalised Stack Permutations

Abstract

Access to Document

Other files and links

Fingerprint

Cite this