𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Enumeration of Permutations with a Prescribed Number of “Forbidden” Patterns

✍ Scribed by John Noonan; Doron Zeilberger

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
219 KB
Volume
17
Category
Article
ISSN
0196-8858

No coin nor oath required. For personal study only.

✦ Synopsis

We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of ''forbidden'' patterns that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns ''abc, '' ''cab,'' and ''abcd.'' ᮊ 1996 Academic Press, Inc.

The reduced form of a permutation on a set j , j , . . . , j , where 1 2 n j -j -иииj is the permutation g S obtained by renaming the

objects of the permutation in the obvious way, so that j is renamed 1 1 and j is renamed 2 and so on. Thus the reduced form of the permutation 2 25734 is 14523 and the reduced form of 579 is 123.

To simplify things, when discussing a particular pattern, we will use its alphabetic equivalent. Thus an increasing subsequence of length 3 is an abc pattern, an inversion is a ba pattern, and a decreasing subsequence of length 4 is a dcba pattern. Other patterns we will discuss include abcd, bac, and cab.

📜 SIMILAR VOLUMES

On the Number of Permutations Avoiding a
On the Number of Permutations Avoiding a Given Pattern
✍ Noga Alon; Ehud Friedgut 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 118 KB

Let \_ # S k and { # S n be permutations. We say { contains \_ if there exist Stanley and Wilf conjectured that for any \_ # S k there exists a constant c=c(\_) such that F(n, \_) c n for all n. Here we prove the following weaker statement: For every fixed \_ # S k , F(n, \_) c n#\* (n) , where c=c

Exact Enumeration of 1342-Avoiding Permu
Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar Maps
✍ Miklós Bóna 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 318 KB

Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating function H(x) of all 1342-avoiding permutations of length n as well as an exact formula for their number S n (1342). While achieving this, we bijectively prove that the number of ind

The Number of Permutations with Exactlyr
The Number of Permutations with Exactlyr132-Subsequences IsP-Recursive in the Size!
✍ Miklós Bóna 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 152 KB

Proving a first nontrivial instance of a conjecture of Noonan and Zeilberger we Ž . show that the number S n of permutations of length n containing exactly r r subsequences of type 132 is a P-recursive function of n. We show that this remains true even if we impose some restrictions on the permutati