✦ LIBER ✦

On the Number of Permutations Avoiding a Given Pattern

✍ Scribed by Noga Alon; Ehud Friedgut

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 118 KB
Volume: 89
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1999.3002

No coin nor oath required. For personal study only.

✦ Synopsis

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(_) and #*(n) is an extremely slow growing function, related to the Ackermann hierarchy.

📜 SIMILAR VOLUMES

The number of labeled graphs placeable b

The number of labeled graphs placeable by a given permutation

✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 370 KB 👁 2 views

Let S be a finite set and u a permutation on S. The permutation u\* on the set of 2-subsets of S is naturally induced by u. Suppose G is a graph and V(G), €(G) are the vertex set, the edge set, respectively. Let V(G) = S. If €(G) and u\*(€(G)), the image of €(G) by u\*, have no common element, then

The Number of Permutation Polynomials of

The Number of Permutation Polynomials of a Given Degree Over a Finite Field

✍ Pinaki Das 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 139 KB

We relate the number of permutation polynomials in F q ½x of degree d q À 2 to the solutions ðx 1 ; x 2 ; . . . ; x q Þ of a system of linear equations over F q , with the added restriction that x i =0 and x i =x j whenever i=j. Using this we find an expression for the number of permutation polynomi

The Enumeration of Permutations with a P

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

✍ John Noonan; Doron Zeilberger 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 219 KB

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 ''

On the Number of Permutations onnObjects

On the Number of Permutations onnObjects with Greatest Cycle Lengthk

✍ Solomon W. Golomb; Peter Gaal 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 144 KB

On the number of vertices of given degre

On the number of vertices of given degree in a random graph

✍ Zbigniew Palka 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

This note can be treated a s a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G E ?An, p) asymptotically has a nor

On Pairs of Lattice Paths with a Given N

On Pairs of Lattice Paths with a Given Number of Intersections

✍ Markus Fulmek 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 307 KB

This formula was proved in [2] by means of generating functions. ## 2. INTERPRETATION OF THE FORMULA'S SUMMANDS Our bijection is based on an appropriate lattice-path-interpretation for the formula's summands (pointed out by Krattenthaler [4]): Clearly, we article no. TA962754 154 0097-3165Â97 25.0