×

zbMATH — the first resource for mathematics

Permutations of a multiset avoiding permutations of length 3. (English) Zbl 0988.05005
A sequence of numbers \(\alpha =(a_{1},\dots ,a_{m})\) is contained in a sequence of numbers \(\beta =(b_{1},\dots ,b_{n})\) if there is a subsequence \((b_{i_{1}},\dots,b_{i_{m}})\), \(i_{1}<\dots <i_{m},\) so that \(a_{s}\leq a_{t}\) iff \(b_{i_{s}}\leq b_{i_{t}}.\) In the paper the permutations of a multiset which do not contain certain subsequences of length \(3\) are considered, in many cases an enumeration of such permutations is given.

MSC:
05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Atkinson, M.D.; Walker, L.; Linton, S.A., Priority queues and multi-sets, Electron. J. comb., 2, Paper R24 (18 pp.), (1995)
[2] Atkinson, M.D., Generalised stack permutations, Comb. probab. comput., 7, 239-246, (1998) · Zbl 0917.05005
[3] Atkinson, M.D., Permutations which are the union of an increasing and a decreasing sequence, Electron. J. comb., 5, Paper R6 (13 pp.), (1998) · Zbl 0885.05011
[4] Bóna, M., Exact enumeration of 1342-avoiding permutations; a close link with labeled trees and planar maps, J. comb. theory, series A, 80, 257-272, (1997) · Zbl 0887.05004
[5] Bóna, M., The permutations classes equinumerous to the smooth class, Electron. J. comb., 5, Paper R31 (12 pp.), (1998)
[6] A. Burstein, 1998
[7] Even, S.; Itai, A., Queues, stacks and graphs, (), 71-86
[8] Pratt, V.R., Computing permutations with double-ended queues, parallel stacks and parallel queues, Proc. ACM symp. theory comput., 5, 268-277, (1973)
[9] Shapiro, L.; Stephens, A.B., Bootstrap percolation, the Schröder number, and the N -kings problem, SIAM J. discrete math., 2, 275-280, (1991) · Zbl 0736.05008
[10] Simion, R.; Schmidt, F.W., Restricted permutations, Europ. J. combinatorics, 6, 383-406, (1985) · Zbl 0615.05002
[11] Stanley, R., Enumerative combinatorics volume 2, Cambridge studies in advanced mathematics 62, (1999), Cambridge University Press UK
[12] Stankova, Z.E., Forbidden subsequences, Discrete math., 132, 291-316, (1994) · Zbl 0810.05011
[13] Stankova, Z.E., Classification of forbidden subsequences of length 4, Europ. J. combinatorics, 17, 501-517, (1996) · Zbl 0857.05007
[14] Tarjan, R.E., Sorting using networks of queues and stacks, J. ACM, 19, 341-346, (1972) · Zbl 0243.68004
[15] West, J., Generating trees and the Catalan and Schröder numbers, Discrete math., 146, 247-262, (1995) · Zbl 0841.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.