Muutke küpsiste eelistusi

Combinatorics of Permutations 3rd edition [Kõva köide]

3.67/5 (4 hinnangut Goodreads-ist)
(University of Florida, Gainesville, USA)
  • Formaat: Hardback, 528 pages, kõrgus x laius: 234x156 mm, kaal: 453 g, 101 Line drawings, black and white; 101 Illustrations, black and white
  • Sari: Discrete Mathematics and Its Applications
  • Ilmumisaeg: 10-May-2022
  • Kirjastus: Chapman & Hall/CRC
  • ISBN-10: 0367222582
  • ISBN-13: 9780367222581
Teised raamatud teemal:
Combinatorics of Permutations 3rd editionSuurem pilt
  • Formaat: Hardback, 528 pages, kõrgus x laius: 234x156 mm, kaal: 453 g, 101 Line drawings, black and white; 101 Illustrations, black and white
  • Sari: Discrete Mathematics and Its Applications
  • Ilmumisaeg: 10-May-2022
  • Kirjastus: Chapman & Hall/CRC
  • ISBN-10: 0367222582
  • ISBN-13: 9780367222581
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780367222581.html
Märksõnad:
A CHOICE "Outstanding Academic Title," the first edition of this bestseller was lauded for its detailed yet engaging treatment of permutations. Providing more than enough material for a one-semester course, Combinatorics of Permutations, third edition continues to clearly show the usefulness of this subject for both students and researchers.

The research in combinatorics of permutations has advanced rapidly since this book was published in a first edition. Now the third edition offers not only updated results, it remains the leading textbook for a course on the topic.

Coverage is mostly enumerative, but there are algebraic, analytic, and topological parts as well, and applications.

Since the publication of the second edition, there is tremendous progress in pattern avoidance (Chapters 4 and 5). There is also significant progress in the analytic combinatorics of permutations, which will be incorporated.

A completely new technique from extremal combinatorics disproved a long-standing conjecture, and this is presented in Chapter 4.

The area of universal permutations has undergone a lot of very recent progress, and that has been noticed outside the academic community as well. This also influenced the revision of Chapter 5.

New results in stack sorting are added to Chapter 8.

Chapter 9 applications to biology has been revised.

The authors other works include Introduction to Enumerative and Analytic Combinatorics, second edition (CHOICE "Outstanding Academic Title") and Handbook of Enumerative Combinatorics, published by CRC Press. The author also serves as Series Editor for CRCs Discrete Mathematics and Its Applications.
Foreword xi
Preface to the First Edition xiii
Preface to the Third Edition xv
Acknowledgments xvii
No Way around It. Introduction xix
1 In One Line and Close. Permutations as Linear Orders
1(52)
1.1 Descents
1(23)
1.1.1 Definition of Descents
1(2)
1.1.2 Eulerian Numbers
3(6)
1.1.3 Stirling Numbers and Eulerian Numbers
9(4)
1.1.4 Generating Functions and Eulerian Numbers
13(2)
1.1.5 Sequences of Eulerian Numbers
15(9)
1.2 Alternating Runs
24(6)
1.3 Alternating Subsequences
30(5)
1.3.1 Definitions and a Recurrence Relation
30(3)
1.3.2 Alternating Runs and Alternating Subsequences
33(1)
1.3.3 Alternating Permutations
34(1)
Exercises
35(7)
Problems Plus
42(4)
Solutions to Problems Plus
46(7)
2 In One Line and Anywhere. Permutations as Linear Orders. Inversions
53(32)
2.1 Inversions
53(15)
2.1.1 Generating Function of Permutations by Inversions
53(10)
2.1.2 Major Index
63(3)
2.1.3 Application: Determinants and Graphs
66(2)
2.2 Inversions in Permutations of Multisets
68(7)
2.2.1 Application: Gaussian Polynomials and Subset Sums
70(1)
2.2.2 Inversions and Gaussian Coefficients
71(2)
2.2.3 Major Index and Permutations of Multisets
73(2)
Exercises
75(4)
Problems Plus
79(3)
Solutions to Problems Plus
82(3)
3 In Many Circles. Permutations as Products of Cycles
85(64)
3.1 Decomposing a Permutation into Cycles
85(6)
3.1.1 Application: Sign and Determinants
87(3)
3.1.2 An Application: Geometric Transformations
90(1)
3.2 Type and Stirling Numbers
91(18)
3.2.1 Cycle Type of a Permutation
91(1)
3.2.2 Application: Conjugate Permutations
92(1)
3.2.3 Application: Trees and Transpositions
93(4)
3.2.4 Permutations with a Given Number of Cycles
97(7)
3.2.5 Generating Functions for Stirling Numbers
104(4)
3.2.6 Application: Real Zeros and Probability
108(1)
3.3 Cycle Decomposition versus Linear Order
109(5)
3.3.1 Transition Lemma
109(2)
3.3.2 Applications of the Transition Lemma
111(3)
3.4 Permutations with Restricted Cycle Structure
114(17)
3.4.1 Exponential Formula
114(9)
3.4.2 Cycle Index and Its Applications
123(8)
Exercises
131(7)
Problems Plus
138(4)
Solutions to Problems Plus
142(7)
4 In Any Way but This. Pattern Avoidance. The Basics
149(66)
4.1 Notion of Pattern Avoidance
149(1)
4.1.1 Permutation classes
150(1)
4.2 Patterns of Length Three
150(5)
4.3 Monotone Patterns
155(3)
4.4 Patterns of Length Four
158(30)
4.4.1 Pattern 1324
160(13)
4.4.2 Pattern 1342
173(15)
4.4.3 Pattern 1234
188(1)
4.5 Proof of the Stanley-Wilf Conjecture
188(7)
4.5.1 Fiiredi--Hajnal Conjecture
189(1)
4.5.2 Avoiding Matrices versus Avoiding Permutations
189(1)
4.5.3 Proof of the Fiiredi--Hajnal Conjecture
190(5)
Exercises
195(7)
Problems Plus
202(5)
Solutions to Problems Plus
207(8)
5 In This Way, but Nicely, Pattern Avoidance, Follow-Up
215(42)
5.1 Polynomial Recurrences
215(19)
5.1.1 Polynomially Recursive Functions
215(1)
5.1.2 Permutation classes again
216(1)
5.1.3 Algebraic and Rational Power Series
217(4)
5.1.4 The Generating Function Of Most Principal Classes Is Nonrational
221(3)
5.1.5 Polynomial Recursiveness of Sn,r(132)
224(10)
5.2 Containing a Pattern Many Times
234(6)
5.2.1 Packing Densities
234(1)
5.2.2 Layered Patterns
235(5)
5.3 Containing a Pattern a Given Number of Times
240(6)
5.3.1 Construction with a Given Number of Copies
241(1)
5.3.2 Sequence {kn}n≥0
242(4)
Exercises
246(3)
Problems Plus
249(2)
Solutions to Problems Plus
251(6)
6 Mean and Insensitive. Random Permutations
257(52)
6.1 Probabilistic Viewpoint
257(16)
6.1.1 Standard Young Tableaux
259(14)
6.2 Expectation
273(5)
6.2.1 Application: Finding the Maximum Element of a Sequence
274(1)
6.2.2 Linearity of Expectation
275(3)
6.3 Application: Rank in Decreasing Binary Trees
278(10)
6.3.1 Two simple initial cases
279(1)
6.3.2 Higher values of k
280(3)
6.3.3 A System of Differential Equations
283(5)
6.4 Variance and Standard Deviation
288(6)
6.4.1 Application: Asymptotically Normal Distributions
292(2)
6.5 Application: Longest Increasing Subsequences
294(2)
Exercises
296(4)
Problems Plus
300(3)
Solutions to Problems Plus
303(6)
7 Permutations and the Rest. Algebraic Combinatorics of Permutations
309(38)
7.1 Robinson Schensted Knuth Correspondence
309(10)
7.2 Posets of Permutations
319(12)
7.2.1 Posets on Sn
319(9)
7.2.2 Posets on Pattern-Avoiding Permutations
328(2)
7.2.3 Infinite Poset of Permutations
330(1)
7.3 Simplicial Complexes of Permutations
331(4)
7.3.1 Simplicial Complex of Restricted Permutations
332(1)
7.3.2 Simplicial Complex of All n-Permutations
333(2)
Exercises
335(4)
Problems Plus
339(2)
Solutions to Problems Plus
341(6)
8 Get Them All. Algorithms and Permutations
347(48)
8.1 Generating Permutations
347(4)
8.1.1 Generating All n-Permutations
347(1)
8.1.2 Generating Restricted Permutations
348(3)
8.2 Stack-Sorting Permutations
351(17)
8.2.1 2-Stack-Sortable Permutations
353(2)
8.2.2 t-Stack-Sortable Permutations
355(10)
8.2.3 Unimodality
365(3)
8.3 Pop-stack sorting
368(5)
8.4 Variations of Stack-Sorting
373(7)
Exercises
380(4)
Problems Plus
384(3)
Solutions to Problems Plus
387(8)
9 How Did We Get Here? Permutations as Genome Rearrangements
395(28)
9.1 Introduction
395(1)
9.2 Block Transpositions
396(4)
9.3 Block Interchanges
400(16)
9.3.1 Average Number of Block Interchanges Needed to Sort
407(9)
Exercises
416(2)
Problems Plus
418(2)
Solutions to Problems Plus
420(3)
10 Do Not Look Just Yet. Solutions to Odd-Numbered Exercises
423(56)
10.1 Solutions for
Chapter 1
423(7)
10.2 Solutions for
Chapter 2
430(4)
10.3 Solutions for
Chapter 3
434(11)
10.4 Solutions for
Chapter 4
445(11)
10.5 Solutions for
Chapter 5
456(4)
10.6 Solutions for
Chapter 6
460(8)
10.7 Solutions for
Chapter 7
468(3)
10.8 Solutions for
Chapter 8
471(5)
10.9 Solutions for
Chapter 9
476(3)
References 479(22)
List of Frequently Used Notation 501(2)
Index 503
Miklós Bóna received his Ph.D in mathematics from the Massachusetts Institute of Technology in 1997. Since 1999, he has taught at the University of Florida, where, in 2010, he was inducted into the Academy of Distinguished Teaching Scholars. Professor Bóna has mentored numerous graduate and undergraduate students. He is the author of four books and more than 65 research articles, mostly focusing on enumerative and analytic combinatorics. His book, Combinatorics of Permutations, won a 2006 Outstanding Title Award from Choice, the journal of the American Library Association. He is also an editor-in-chief for the Electronic Journal of Combinatorics, and for two book series at CRC Press.