𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Combinatorial Proof of the Log-Concavity of the Numbers of Permutations with k Runs

✍ Scribed by Miklós Bóna; Richard Ehrenborg

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
178 KB
Volume
90
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Combinatorial Proof of the Log-Concavity
Combinatorial Proof of the Log-Concavity of the Sequence of Matching Numbers
✍ C. Krattenthaler 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 145 KB

For k l we construct an injection from the set of pairs of matchings in a given graph G of sizes l&1 and k+1 into the set of pairs of matchings in G of sizes l and k. This provides a combinatorial proof of the log-concavity of the sequence of matching numbers of a graph. Besides, this injection impl

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

A lower bound on the number of spanning
A lower bound on the number of spanning trees with k end-vertices
✍ Katherine Heinrich; Guizhen Liu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 1 views

If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span