Handbook of Enumerative Combinatorics 1st Edition Miklós Bóna (Editor)

Handbook of Enumerative Combinatorics 1st
Edition Miklós Bóna (Editor) pdf download
https://ebookfinal.com/download/handbook-of-enumerative-
combinatorics-1st-edition-miklos-bona-editor/
Explore and download more ebooks or textbooks
at ebookfinal.com

Here are some recommended products for you. Click the link to
download, or explore more at ebookfinal
MacMillan Destination C1 C2 Grammar Vocabulary Malcolm
Mann
https://ebookfinal.com/download/macmillan-destination-c1-c2-grammar-
vocabulary-malcolm-mann/
Enumerative Combinatorics 1st Edition Charalambos A.
Charalambides
https://ebookfinal.com/download/enumerative-combinatorics-1st-edition-
charalambos-a-charalambides/
Annual Reports on NMR Spectroscopy Volume 83 1st Edition
Webb
https://ebookfinal.com/download/annual-reports-on-nmr-spectroscopy-
volume-83-1st-edition-webb/
Using the TI 83 Plus TI 84 Plus Christopher R. Mitchell
https://ebookfinal.com/download/using-the-ti-83-plus-ti-84-plus-
christopher-r-mitchell/

Introduction to Enumerative and Analytic Combinatorics
Second Edition Miklós Bóna
https://ebookfinal.com/download/introduction-to-enumerative-and-
analytic-combinatorics-second-edition-miklos-bona/
Vagabond Vol 29 29 Inoue
https://ebookfinal.com/download/vagabond-vol-29-29-inoue/
Handbook of Statistics_29B Volume 29 Sample Surveys
Inference and Analysis 1° Edition Danny Pfeffermann
https://ebookfinal.com/download/handbook-of-
statistics_29b-volume-29-sample-surveys-inference-and-
analysis-1-edition-danny-pfeffermann/
Handbook of Peripheral Neuropathy 1st Edition Mark B.
Bromberg
https://ebookfinal.com/download/handbook-of-peripheral-neuropathy-1st-
edition-mark-b-bromberg/
Combinatorics of Compositions and Words 1st Edition Silvia
Heubach
https://ebookfinal.com/download/combinatorics-of-compositions-and-
words-1st-edition-silvia-heubach/

Handbook of Enumerative Combinatorics 1st Edition
MiklÃ³s BÃ³na (Editor) Digital Instant Download
Author(s): MiklÃ³s BÃ³na (Editor)
ISBN(s): 9781482220865, 1482220857
Edition: 1
File Details: PDF, 8.07 MB
Year: 2015
Language: english

K22222
www.crcpress.com
DISCRETE MATHEMATICS AND ITS APPLICATIONS
DISCRETE MATHEMATICS AND ITS APPLICATIONS
HANDBOOK OF
ENUMERATIVE
COMBINATORICS
HANDBOOK OF ENUMERATIVE

COMBINATORICS
Edited by
Miklós Bóna
Bóna
6000 Broken Sound Parkway, NW
Suite 300, Boca Raton, FL 33487
711 Third Avenue
New York, NY 10017
2 Park Square, Milton Park
Abingdon, Oxon OX14 4RN, UK
an informa business
www.crcpress.com
Presenting the state of the art, the Handbook of Enumerative Combinatorics
brings together the work of today’s most prominent researchers. The contribu-
tors survey the methods of combinatorial enumeration along with the most
frequent applications of these methods.
This important new work is edited by Miklós Bóna of the University of Florida,
where he is a member of the Academy of Distinguished Teaching Scholars. He
received his Ph.D. in mathematics at Massachusetts Institute of Technology in
1997. Miklós is the author of four books and more than 65 research articles,
including the award-winning Combinatorics of Permutations. Miklós Bóna is
an editor-in-chief for the Electronic Journal of Combinatorics and Series Editor
of the Discrete Mathematics and Its Applications Series for CRC Press/Chap-
man and Hall.
The first two chapters provide a comprehensive overview of the most frequent-
ly used methods in combinatorial enumeration, including algebraic, geometric,
and analytic methods. These chapters survey generating functions, methods
from linear algebra, partially ordered sets, polytopes, hyperplane arrange-
ments, and matroids. Subsequent chapters illustrate applications of these
methods for counting a wide array of objects.
The contributors for this book represent an international spectrum of research-
ers with strong histories of results. The chapters are organized so readers ad-
vance from the more general ones, namely enumeration methods, towards the
more specialized ones.
Topics include coverage of asymptotic normality in enumeration, planar maps,
graph enumeration, Young tableaux, unimodality, log-concavity, real zeros,
asymptotic normality, trees, generalized Catalan paths, computerized enu-
meration schemes, enumeration of various graph classes, words, tilings,
pattern avoidance, computer algebra, and parking functions.
This book will be beneficial to a wide audience. It will appeal to experts on the
topic interested in learning more about the finer points, readers interested in a
systematic and organized treatment of the topic, and novices who are new to
the field.
Combinatorics & Discrete Mathematics

HANDBOOK OF
ENUMERATIVE COMBINATORICS

DISCRETE
MATHEMATICS
ITS APPLICATIONS
R. B. J. T. Allenby and Alan Slomson, How to Count: An Introduction to Combinatorics,
Third Edition
Craig P. Bauer, Secret History: The Story of Cryptology
Juergen Bierbrauer, Introduction to Coding Theory
Katalin Bimbó, Combinatory Logic: Pure, Applied and Typed
Katalin Bimbó, Proof Theory: Sequent Calculi and Related Formalisms
Donald Bindner and Martin Erickson, A Student’s Guide to the Study, Practice, and Tools of
Modern Mathematics
Francine Blanchet-Sadri, Algorithmic Combinatorics on Partial Words
Miklós Bóna, Combinatorics of Permutations, Second Edition
Miklós Bóna, Handbook of Enumerative Combinatorics
Jason I. Brown, Discrete Structures and Their Interactions
Richard A. Brualdi and Drago˘s Cvetkovi´c, A Combinatorial Approach to Matrix Theory and Its
Applications
Kun-Mao Chao and Bang Ye Wu, Spanning Trees and Optimization Problems
Charalambos A. Charalambides, Enumerative Combinatorics
Gary Chartrand and Ping Zhang, Chromatic Graph Theory
Henri Cohen, Gerhard Frey, et al., Handbook of Elliptic and Hyperelliptic Curve Cryptography
Charles J. Colbourn and Jeffrey H. Dinitz, Handbook of Combinatorial Designs, Second Edition
Abhijit Das, Computational Number Theory
Matthias Dehmer and Frank Emmert-Streib, Quantitative Graph Theory:
Mathematical Foundations and Applications
Martin Erickson, Pearls of Discrete Mathematics
Martin Erickson and Anthony Vazzana, Introduction to Number Theory

Titles (continued)
Steven Furino, Ying Miao, and Jianxing Yin, Frames and Resolvable Designs: Uses,
Constructions, and Existence
Mark S. Gockenbach, Finite-Dimensional Linear Algebra
Randy Goldberg and Lance Riek, A Practical Handbook of Speech Coders
Jacob E. Goodman and Joseph O’Rourke, Handbook of Discrete and Computational Geometry,
Second Edition
Jonathan L. Gross, Combinatorial Methods with Computer Applications
Jonathan L. Gross and Jay Yellen, Graph Theory and Its Applications, Second Edition
Jonathan L. Gross, Jay Yellen, and Ping Zhang Handbook of Graph Theory, Second Edition
David S. Gunderson, Handbook of Mathematical Induction: Theory and Applications
Richard Hammack, Wilfried Imrich, and Sandi Klavžar, Handbook of Product Graphs,
Second Edition
Darrel R. Hankerson, Greg A. Harris, and Peter D. Johnson, Introduction to Information Theory
and Data Compression, Second Edition
Darel W. Hardy, Fred Richman, and Carol L. Walker, Applied Algebra: Codes, Ciphers, and
Discrete Algorithms, Second Edition
Daryl D. Harms, Miroslav Kraetzl, Charles J. Colbourn, and John S. Devitt, Network Reliability:
Experiments with a Symbolic Algebra Environment
Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words
Leslie Hogben, Handbook of Linear Algebra, Second Edition
Derek F. Holt with Bettina Eick and Eamonn A. O’Brien, Handbook of Computational Group Theory
David M. Jackson and Terry I. Visentin, An Atlas of Smaller Maps in Orientable and
Nonorientable Surfaces
Richard E. Klima, Neil P. Sigmon, and Ernest L. Stitzinger, Applications of Abstract Algebra
with Maple™ and MATLAB®, Second Edition
Richard E. Klima and Neil P. Sigmon, Cryptology: Classical and Modern with Maplets
Patrick Knupp and Kambiz Salari, Verification of Computer Codes in Computational Science
and Engineering
William Kocay and Donald L. Kreher, Graphs, Algorithms, and Optimization
Donald L. Kreher and Douglas R. Stinson, Combinatorial Algorithms: Generation Enumeration
and Search
Hang T. Lau, A Java Library of Graph Algorithms and Optimization
C. C. Lindner and C. A. Rodger, Design Theory, Second Edition
San Ling, Huaxiong Wang, and Chaoping Xing, Algebraic Curves in Cryptography
Nicholas A. Loehr, Bijective Combinatorics
Toufik Mansour, Combinatorics of Set Partitions

Titles (continued)
Alasdair McAndrew, Introduction to Cryptography with Open-Source Software
Elliott Mendelson, Introduction to Mathematical Logic, Fifth Edition
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied
Cryptography
Stig F. Mjølsnes, A Multidisciplinary Introduction to Information Security
Jason J. Molitierno, Applications of Combinatorial Matrix Theory to Laplacian Matrices of Graphs
Richard A. Mollin, Advanced Number Theory with Applications
Richard A. Mollin, Algebraic Number Theory, Second Edition
Richard A. Mollin, Codes: The Guide to Secrecy from Ancient to Modern Times
Richard A. Mollin, Fundamental Number Theory with Applications, Second Edition
Richard A. Mollin, An Introduction to Cryptography, Second Edition
Richard A. Mollin, Quadratics
Richard A. Mollin, RSA and Public-Key Cryptography
Carlos J. Moreno and Samuel S. Wagstaff, Jr., Sums of Squares of Integers
Gary L. Mullen and Daniel Panario, Handbook of Finite Fields
Goutam Paul and Subhamoy Maitra, RC4 Stream Cipher and Its Variants
Dingyi Pei, Authentication Codes and Combinatorial Designs
Kenneth H. Rosen, Handbook of Discrete and Combinatorial Mathematics
Douglas R. Shier and K.T. Wallenius, Applied Mathematical Modeling: A Multidisciplinary
Approach
Alexander Stanoyevitch, Introduction to Cryptography with Mathematical Foundations and
Computer Implementations
Jörn Steuding, Diophantine Analysis
Douglas R. Stinson, Cryptography: Theory and Practice, Third Edition
Roberto Tamassia, Handbook of Graph Drawing and Visualization
Roberto Togneri and Christopher J. deSilva, Fundamentals of Information Theory and Coding
Design
W. D. Wallis, Introduction to Combinatorial Designs, Second Edition
W. D. Wallis and J. C. George, Introduction to Combinatorics
Jiacun Wang, Handbook of Finite State Based Models and Applications
Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Second Edition

DISCRETE MATHEMATICS AND ITS APPLICATIONS
HANDBOOK OF
ENUMERATIVE COMBINATORICS
Edited by
Miklós Bóna
University of Florida
Gainesville, Florida, USA

CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
© 2015 by Taylor & Francis Group, LLC
CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Version Date: 20150220
International Standard Book Number-13: 978-1-4822-2086-5 (eBook - PDF)
This book contains information obtained from authentic and highly regarded sources. Reasonable efforts
have been made to publish reliable data and information, but the author and publisher cannot assume
responsibility for the validity of all materials or the consequences of their use. The authors and publishers
have attempted to trace the copyright holders of all material reproduced in this publication and apologize to
copyright holders if permission to publish in this form has not been obtained. If any copyright material has
not been acknowledged please write and let us know so we may rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit-
ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented,
including photocopying, microfilming, and recording, or in any information storage or retrieval system,
without written permission from the publishers.
For permission to photocopy or use material electronically from this work, please access www.copyright.
com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood
Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and
registration for a variety of users. For organizations that have been granted a photocopy license by the CCC,
a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used
only for identification and explanation without intent to infringe.
Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com
and the CRC Press Web site at
http://www.crcpress.com

Contents
Foreword xix
Preface xxi
Acknowledgments xxiii
I Methods 1
1 Algebraic and Geometric Methods in Enumerative Combinatorics 3
Federico Ardila
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
PART 1. ALGEBRAIC METHODS 6
1.2 What is a good answer? . . . . . . . . . . . . . . . . . . . . . . .
1.3 Generating functions . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 The ring of formal power series . . . . . . . . . . . . . .
1.3.2 Ordinary generating functions . . . . . . . . . . . . . . .
1.3.2.1 Operations on combinatorial structures and
their generating functions . . . . . . . . . . .
1.3.2.2 Examples . . . . . . . . . . . . . . . . . . .
1.3.3 Exponential generating functions . . . . . . . . . . . . .
1.3.3.1 Operations on labeled structures and their ex-
ponential generating functions . . . . . . . .
1.3.3.2 Examples . . . . . . . . . . . . . . . . . . .
1.3.4 Nice families of generating functions . . . . . . . . . . .
1.3.4.1 Rational generating functions . . . . . . . . .
1.3.4.2 Algebraic and D-nite generating functions .
1.4 Linear algebra methods . . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Determinants in combinatorics . . . . . . . . . . . . . .
1.4.1.1 Preliminaries: Graph matrices . . . . . . . . .
1.4.1.2 Walks: the transfer matrix method . . . . . .
1.4.1.3 Spanning trees: the matrix-tree theorem . . .
1.4.1.4 Eulerian cycles: the BEST theorem . . . . . .
1.4.1.5 Perfect matchings: the Pfafan method . . . .
1.4.1.6 Routings: the Lindstr¨omGesselViennot
lemma . . . . . . . . . . . . . . . . . . . . .
1.4.2 Computing determinants . . . . . . . . . . . . . . . . .
vii

viii Contents
1.4.2.1 Is it known? . . . . . . . . . . . . . . . . . .
1.4.2.2 Row and column operations . . . . . . . . . .
1.4.2.3 Identifying linear factors . . . . . . . . . . .
1.4.2.4 Computing the eigenvalues . . . . . . . . . .
1.4.2.5 LU factorizations . . . . . . . . . . . . . . .
1.4.2.6 Hankel determinants and continued fractions .
1.5 Posets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1 Basic denitions and examples . . . . . . . . . . . . . .
1.5.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.3 Zeta polynomials and order polynomials . . . . . . . . .
1.5.4 The inclusion-exclusion formula . . . . . . . . . . . . .
1.5.5 M¨obius functions and M¨obius inversion . . . . . . . . .
1.5.5.1 The M¨obius function . . . . . . . . . . . . .
1.5.5.2 M¨obius inversion . . . . . . . . . . . . . . .
1.5.5.3 The incidence algebra . . . . . . . . . . . . .
1.5.5.4 Computing M¨obius functions . . . . . . . . .
1.5.6 Eulerian posets, agf-vectors, and agh-vectors . . . .
PART 2. DISCRETE GEOMETRIC METHODS 93
1.6 Polytopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.1 Basic denitions and constructions . . . . . . . . . . . .
1.6.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.3 Counting faces . . . . . . . . . . . . . . . . . . . . . . .
1.6.4 Counting lattice points: Ehrhart theory . . . . . . . . . .
1.7 Hyperplane arrangements . . . . . . . . . . . . . . . . . . . . . .
1.7.1 Basic denitions . . . . . . . . . . . . . . . . . . . . . .
1.7.2 The characteristic polynomial . . . . . . . . . . . . . . .
1.7.3 Properties of the characteristic polynomial . . . . . . . .
1.7.3.1 Deletion and contraction . . . . . . . . . . .
1.7.3.2 Sign alternation and unimodality . . . . . . .
1.7.3.3 Graphs and proper colorings . . . . . . . . .
1.7.3.4 Free arrangements . . . . . . . . . . . . . .
1.7.3.5 Supersolvability . . . . . . . . . . . . . . . .
1.7.4 Computing the characteristic polynomial . . . . . . . . .
1.7.5 Thecd-index of an arrangement . . . . . . . . . . . . . .
1.8 Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.8.1 Main example: Vector congurations and linear matroids
1.8.2 Basic denitions . . . . . . . . . . . . . . . . . . . . . .
1.8.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . .
1.8.4 Basic constructions . . . . . . . . . . . . . . . . . . . .
1.8.5 A few structural results . . . . . . . . . . . . . . . . . .
1.8.6 The Tutte polynomial . . . . . . . . . . . . . . . . . . .
1.8.6.1 Explicit denition . . . . . . . . . . . . . . .
1.8.6.2 Recursive denition and universality property
1.8.6.3 Activity interpretation . . . . . . . . . . . . .

Contents ix
1.8.6.4 Finite eld interpretation . . . . . . . . . . .
1.8.7 Tutte polynomial evaluations . . . . . . . . . . . . . . .
1.8.7.1 General evaluations . . . . . . . . . . . . . .
1.8.7.2 Graphs . . . . . . . . . . . . . . . . . . . . .
1.8.7.3 Hyperplane arrangements . . . . . . . . . . .
1.8.7.4 Algebras from arrangements . . . . . . . . .
1.8.7.5 Error-correcting codes . . . . . . . . . . . . .
1.8.7.6 Probability and statistical mechanics . . . . .
1.8.7.7 Other applications . . . . . . . . . . . . . . .
1.8.8 Computing the Tutte polynomial . . . . . . . . . . . . .
1.8.9 Generalizations of the Tutte polynomial . . . . . . . . .
1.8.10 Matroid subdivisions, valuations, and the Derksen-Fink
invariant . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Analytic Methods 173
Helmut Prodinger
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Combinatorial constructions and associated ordinary generating
functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Combinatorial constructions and associated exponential generating
functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Partitions andq-series . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Some applications of the adding a slice technique . . . . . . . . .
2.6 Lagrange inversion formula . . . . . . . . . . . . . . . . . . . . .
2.7 Lattice path enumeration: the continued fraction theorem . . . . .
2.8 Lattice path enumeration: the kernel method . . . . . . . . . . . .
2.9 Gamma and zeta function . . . . . . . . . . . . . . . . . . . . . .
2.10 Harmonic numbers and their generating functions . . . . . . . . .
2.11 Approximation of binomial coefcients . . . . . . . . . . . . . .
2.12 Mellin transform and asymptotics of harmonic sums . . . . . . . .
2.13 The Mellin-Perron formula . . . . . . . . . . . . . . . . . . . . .
2.14 Mellin-Perron formula: divide-and-conquer recursions . . . . . .
2.15 Rice's method . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.16 Approximate counting . . . . . . . . . . . . . . . . . . . . . . .
2.17 Singularity analysis of generating functions . . . . . . . . . . . .
2.18 Longest runs in words . . . . . . . . . . . . . . . . . . . . . . . .
2.19 Inversions in permutations and pumping moments . . . . . . . . .
2.20 The tree function . . . . . . . . . . . . . . . . . . . . . . . . . .
2.21 The saddle point method . . . . . . . . . . . . . . . . . . . . . .
2.22 Hwang's quasi-power theorem . . . . . . . . . . . . . . . . . . .
II Topics 253
3 Asymptotic Normality in Enumeration 255
E. Rodney Caneld

x Contents
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 The normal distribution . . . . . . . . . . . . . . . . . . . . . . .
3.3 Method 1: direct approach . . . . . . . . . . . . . . . . . . . . .
3.4 Method 2: negative roots . . . . . . . . . . . . . . . . . . . . . .
3.5 Method 3: moments . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Method 4: singularity analysis . . . . . . . . . . . . . . . . . . .
3.7 Local limit theorems . . . . . . . . . . . . . . . . . . . . . . . .
3.8 Multivariate asymptotic normality . . . . . . . . . . . . . . . . .
3.9 Normality in service to approximate enumeration . . . . . . . . .
4 Trees 281
Michael Drmota
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Basic notions . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Generating functions . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Generating functions and combinatorial constructions . .
4.3.2 The Lagrange inversion formula . . . . . . . . . . . . .
4.3.3 The dissymmetry theorem . . . . . . . . . . . . . . . . .
4.3.4 Asymptotics . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Unlabeled trees . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Binary trees . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2 Planted plane trees . . . . . . . . . . . . . . . . . . . . .
4.4.3 Unlabeled plane trees . . . . . . . . . . . . . . . . . . .
4.4.4 General unlabeled trees . . . . . . . . . . . . . . . . . .
4.4.5 Simply generated trees and Galton-Watson trees . . . . .
4.5 Labeled trees . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1 Cayley trees and related trees . . . . . . . . . . . . . . .
4.5.2 Recursive trees . . . . . . . . . . . . . . . . . . . . . . .
4.5.3 Well-labeled trees . . . . . . . . . . . . . . . . . . . . .
4.6 Selected topics on trees . . . . . . . . . . . . . . . . . . . . . . .
4.6.1 Spanning trees . . . . . . . . . . . . . . . . . . . . . . .
4.6.2k-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.3 Search trees . . . . . . . . . . . . . . . . . . . . . . . .
5 Planar Maps 335
Gilles Schaeffer
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 What is a map? . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 A few denitions . . . . . . . . . . . . . . . . . . . . .
5.2.2 Plane maps, rooted maps and orientations . . . . . . . .
5.2.3 Which maps shall we count? . . . . . . . . . . . . . . .
5.3 Counting tree-rooted maps . . . . . . . . . . . . . . . . . . . . .
5.3.1 Mullin's decomposition . . . . . . . . . . . . . . . . . .
5.3.2 Spanning trees and orientations . . . . . . . . . . . . . .
5.3.3 Vertex blowing and polyhedral nets . . . . . . . . . . . .

Contents xi
5.3.4 A summary and some observations . . . . . . . . . . . .
5.4 Counting planar maps . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 The exact number of rooted planar maps . . . . . . . . .
5.4.2 Unrooted planar maps . . . . . . . . . . . . . . . . . . .
5.4.3 Two bijections between maps and trees . . . . . . . . . .
5.4.4 Substitution relations . . . . . . . . . . . . . . . . . . .
5.4.5 Asymptotic enumeration and uniform random planar
maps . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.6 Distances in planar maps . . . . . . . . . . . . . . . . .
5.4.7 Local limit, continuum limit . . . . . . . . . . . . . . . .
5.5 Beyond planar maps, an even shorter account . . . . . . . . . . .
5.5.1 Patterns and universality . . . . . . . . . . . . . . . . . .
5.5.2 The bijective canvas and master bijections . . . . . . . .
5.5.3 Maps on surfaces . . . . . . . . . . . . . . . . . . . . .
5.5.4 Decorated maps . . . . . . . . . . . . . . . . . . . . . .
6 Graphs 397
Marc Noy
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Graph decompositions . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Graphs with given connectivity . . . . . . . . . . . . . .
6.2.2 Graphs with given minimum degree . . . . . . . . . . . .
6.2.3 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . .
6.3 Connected graphs with given excess . . . . . . . . . . . . . . . .
6.4 Regular graphs . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4.1 The pairing model . . . . . . . . . . . . . . . . . . . . .
6.4.2 Differential equations . . . . . . . . . . . . . . . . . . .
6.5 Monotone and hereditary classes . . . . . . . . . . . . . . . . . .
6.5.1 Monotone classes . . . . . . . . . . . . . . . . . . . . .
6.5.2 Hereditary classes . . . . . . . . . . . . . . . . . . . . .
6.6 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.7 Graphs on surfaces and graph minors . . . . . . . . . . . . . . . .
6.7.1 Graphs on surfaces . . . . . . . . . . . . . . . . . . . .
6.7.2 Graph minors . . . . . . . . . . . . . . . . . . . . . . .
6.7.3 Particular classes . . . . . . . . . . . . . . . . . . . . .
6.8 Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.8.1 Acyclic digraphs . . . . . . . . . . . . . . . . . . . . . .
6.8.2 Strongly connected digraphs . . . . . . . . . . . . . . .
6.9 Unlabeled graphs . . . . . . . . . . . . . . . . . . . . . . . . . .
6.9.1 Counting graphs under symmetries . . . . . . . . . . . .
6.9.2 Asymptotics . . . . . . . . . . . . . . . . . . . . . . . .
7 Unimodality, Log-concavity, Real-rootedness and Beyond 437
Petter Br¨and´en
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xii Contents
7.2 Probabilistic consequences of real-rootedness . . . . . . . . . . .
7.3 Unimodality andg-nonnegativity . . . . . . . . . . . . . . . . . .
7.3.1 An action on permutations . . . . . . . . . . . . . . . . .
7.3.2g-nonnegativity ofh-polynomials . . . . . . . . . . . . .
7.3.3 Barycentric subdivisions . . . . . . . . . . . . . . . . . .
7.3.4 Unimodality ofh

-polynomials . . . . . . . . . . . . . .
7.4 Log-concavity and matroids . . . . . . . . . . . . . . . . . . . .
7.5 Innite log-concavity . . . . . . . . . . . . . . . . . . . . . . . .
7.6 The NeggersStanley conjecture . . . . . . . . . . . . . . . . . .
7.7 Preserving real-rootedness . . . . . . . . . . . . . . . . . . . . .
7.7.1 The subdivision operator . . . . . . . . . . . . . . . . .
7.8 Common interleavers . . . . . . . . . . . . . . . . . . . . . . . .
7.8.1s-Eulerian polynomials . . . . . . . . . . . . . . . . . .
7.8.2 Eulerian polynomials for nite Coxeter groups . . . . . .
7.9 Multivariate techniques . . . . . . . . . . . . . . . . . . . . . . .
7.9.1 Stable polynomials and matroids . . . . . . . . . . . . .
7.9.2 Strong Rayleigh measures . . . . . . . . . . . . . . . . .
7.9.3 The symmetric exclusion process . . . . . . . . . . . . .
7.9.4 The GraceWalshSzego theorem, and the proof of The-
orem 7.5.1 . . . . . . . . . . . . . . . . . . . . . . . . .
7.10 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 Words 485
Dominique Perrin and Antonio Restivo
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2.1 Generating series . . . . . . . . . . . . . . . . . . . . .
8.2.2 Automata . . . . . . . . . . . . . . . . . . . . . . . . .
8.3 Conjugacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3.1 Periods . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3.2 Necklaces . . . . . . . . . . . . . . . . . . . . . . . . .
8.3.3 Circular codes . . . . . . . . . . . . . . . . . . . . . . .
8.4 Lyndon words . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4.1 The factorization theorem . . . . . . . . . . . . . . . . .
8.4.2 Generating Lyndon words . . . . . . . . . . . . . . . . .
8.5 Eulerian graphs and de Bruijn cycles . . . . . . . . . . . . . . .
8.5.1 The BEST theorem . . . . . . . . . . . . . . . . . . . .
8.5.2 The Matrix-tree theorem . . . . . . . . . . . . . . . . . .
8.5.3 Lyndon words and de Bruijn cycles . . . . . . . . . . .
8.6 Unavoidable sets . . . . . . . . . . . . . . . . . . . . . . . . . .
8.6.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . .
8.6.2 Unavoidable sets of constant length . . . . . . . . . . . .
8.6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . .
8.7 The BurrowsWheeler transform . . . . . . . . . . . . . . . . . .
8.7.1 The inverse transform . . . . . . . . . . . . . . . . . . .

Contents xiii
8.7.2 Descents of a permutation . . . . . . . . . . . . . . . . .
8.8 The Gessel-Reutenauer bijection . . . . . . . . . . . . . . . . . .
8.8.1 Gessel-Reutenauer bijection and de Bruijn cycles . . . .
8.9 Sufx arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.9.1 Sufx arrays and BurrowsWheeler transform . . . . . .
8.9.2 Counting sufx arrays . . . . . . . . . . . . . . . . . . .
9 Tilings 541
James Propp
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.2 The transfer matrix method . . . . . . . . . . . . . . . . . . . . .
9.3 Other determinant methods . . . . . . . . . . . . . . . . . . . . .
9.3.1 The path method . . . . . . . . . . . . . . . . . . . . . .
9.3.2 The permanent-determinant and Hafnian-Pfafan method
9.3.3 The spanning tree method . . . . . . . . . . . . . . . . .
9.4 Representation-theoretic methods . . . . . . . . . . . . . . . . .
9.5 Other combinatorial methods . . . . . . . . . . . . . . . . . . . .
9.6 Related topics, and an attempt at history . . . . . . . . . . . . . .
9.7 Some emergent themes . . . . . . . . . . . . . . . . . . . . . . .
9.7.1 Recurrence relations . . . . . . . . . . . . . . . . . . . .
9.7.2 Smoothness . . . . . . . . . . . . . . . . . . . . . . . .
9.7.3 Non-periodic weights . . . . . . . . . . . . . . . . . . .
9.7.4 Other numerical patterns . . . . . . . . . . . . . . . . .
9.7.5 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . .
9.8 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.9 Frontiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10 Lattice Path Enumeration 589
Christian Krattenthaler
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2 Lattice paths without restrictions . . . . . . . . . . . . . . . . . .
10.3 Linear boundaries of slope 1 . . . . . . . . . . . . . . . . . . . .
10.4 Simple paths with linear boundaries of rational slope, I . . . . . .
10.5 Simple paths with linear boundaries with rational slope, II . . . .
10.6 Simple paths with a piecewise linear boundary . . . . . . . . . . .
10.7 Simple paths with general boundaries . . . . . . . . . . . . . . .
10.8 Elementary results on Motzkin and Schr¨oder paths . . . . . . . .
10.9 A continued fraction for the weighted counting of Motzkin paths .
10.10 Lattice paths and orthogonal polynomials . . . . . . . . . . . . .
10.11 Motzkin paths in a strip . . . . . . . . . . . . . . . . . . . . . . .
10.12 Further results for lattice paths in the plane . . . . . . . . . . . . .
10.13 Non-intersecting lattice paths . . . . . . . . . . . . . . . . . . . .
10.14 Lattice paths and their turns . . . . . . . . . . . . . . . . . . . . .
10.15 Multidimensional lattice paths . . . . . . . . . . . . . . . . . . .
10.16 Multidimensional lattice paths bounded by a hyperplane . . . . .

xiv Contents
10.17 Multidimensional paths with a general boundary . . . . . . . . . .
10.18 The reection principle in full generality . . . . . . . . . . . . . .
10.19q-Counting of lattice paths and Rogers-Ramanujan identities . . .
10.20 Self-avoiding walks . . . . . . . . . . . . . . . . . . . . . . . . .
11 Catalan Paths andq;t-enumeration 679
James Haglund
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.2 Introduction toq-analogues and Catalan numbers . . . . . . . . .
11.2.1 Permutation statistics and Gaussian polynomials . . . . .
11.2.2 The Catalan numbers and Dyck paths . . . . . . . . . . .
11.2.3 Theq-Vandermonde convolution . . . . . . . . . . . . .
11.2.4 Symmetric functions . . . . . . . . . . . . . . . . . . . .
11.2.4.1 The basics . . . . . . . . . . . . . . . . . . .
11.2.4.2 Tableaux and Schur functions . . . . . . . . .
11.2.4.3 Statistics on tableaux . . . . . . . . . . . . .
11.2.5 Representation theory . . . . . . . . . . . . . . . . . . .
11.2.5.1 The ring of coinvariants and the space of diag-
onal harmonics . . . . . . . . . . . . . . . .
11.3 Theq;t-Catalan numbers . . . . . . . . . . . . . . . . . . . . . .
11.3.1 The bounce statistic . . . . . . . . . . . . . . . . . . . .
11.3.2 The special valuest=1 andt=1=q. . . . . . . . . . .
11.3.3 The symmetry problem and the dinv statistic . . . . . . .
11.3.4q-Lagrange inversion . . . . . . . . . . . . . . . . . . .
11.4 Parking functions and the Hilbert series . . . . . . . . . . . . . .
11.4.1 Extension of the dinv statistic . . . . . . . . . . . . . . .
11.4.2 An explicit formula . . . . . . . . . . . . . . . . . . . .
11.4.3 The statistic area
0
. . . . . . . . . . . . . . . . . . . . .
11.4.4 The pmaj statistic . . . . . . . . . . . . . . . . . . . . .
11.4.5 The cyclic-shift operation . . . . . . . . . . . . . . . . .
11.4.6 Tesler matrices . . . . . . . . . . . . . . . . . . . . . . .
11.5 Theq;t-Schr¨oder polynomial . . . . . . . . . . . . . . . . . . . .
11.5.1 The Schr¨oder bounce and area statistics . . . . . . . . . .
11.5.2 Recurrences and explicit formulae . . . . . . . . . . . .
11.5.3 The special valuet=1=q. . . . . . . . . . . . . . . . .
11.5.4 A Schr¨oder dinv-statistic . . . . . . . . . . . . . . . . .
11.5.5 The shufe conjecture . . . . . . . . . . . . . . . . . . .
11.6 Rational Catalan combinatorics . . . . . . . . . . . . . . . . . . .
11.6.1 The superpolynomial invariant of a torus knot . . . . . .
11.6.2 Tesler matrices and the superpolynomial . . . . . . . . .
12 Permutation Classes 753
Vincent Vatter
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12.1.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . .

Contents xv
12.1.2 Avoiding a permutation of length three . . . . . . . . . .
12.1.3 Wilf-equivalence . . . . . . . . . . . . . . . . . . . . . .
12.1.4 Avoiding a longer permutation . . . . . . . . . . . . . .
12.2 Growth rates of principal classes . . . . . . . . . . . . . . . . . .
12.2.1 Matrices and the interval minor order . . . . . . . . . . .
12.2.2 The number of light matrices . . . . . . . . . . . . . . .
12.2.3 Matrices avoidingJkare light . . . . . . . . . . . . . . .
12.2.4 Dense matrices contain many permutations . . . . . . . .
12.2.5 Dense matrices avoidingJk. . . . . . . . . . . . . . . .
12.3 Notions of structure . . . . . . . . . . . . . . . . . . . . . . . . .
12.3.1 Merging and splitting . . . . . . . . . . . . . . . . . . .
12.3.2 The substitution decomposition . . . . . . . . . . . . . .
12.3.3 Atomicity . . . . . . . . . . . . . . . . . . . . . . . . .
12.4 The set of all growth rates . . . . . . . . . . . . . . . . . . . . . .
12.4.1 Monotone grid classes . . . . . . . . . . . . . . . . . . .
12.4.2 Geometric grid classes . . . . . . . . . . . . . . . . . . .
12.4.3 Generalized grid classes . . . . . . . . . . . . . . . . . .
12.4.4 Small permutation classes . . . . . . . . . . . . . . . . .
13 Parking Functions 835
Catherine H. Yan
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13.2 Parking functions and labeled trees . . . . . . . . . . . . . . . . .
13.2.1 Labeled trees with Pr¨ufer code . . . . . . . . . . . . . .
13.2.2 Inversions of labeled trees . . . . . . . . . . . . . . . . .
13.2.3 Graph searching algorithms . . . . . . . . . . . . . . . .
13.2.4 External activity of labeled trees . . . . . . . . . . . . .
13.2.5 Sparse connected graphs . . . . . . . . . . . . . . . . . .
13.3 Many faces of parking functions . . . . . . . . . . . . . . . . . .
13.3.1 Hashing and linear probing . . . . . . . . . . . . . . . .
13.3.2 Lattice of noncrossing partitions . . . . . . . . . . . . .
13.3.3 Hyperplane arrangements . . . . . . . . . . . . . . . . .
13.3.4 Allowable input-output pairs in a priority queue . . . . .
13.3.5 Two variations of parking functions . . . . . . . . . . .
13.4 Generalized parking functions . . . . . . . . . . . . . . . . . . .
13.4.1u-parking functions . . . . . . . . . . . . . . . . . . . .
13.4.2 A parking polytope . . . . . . . . . . . . . . . . . . . .
13.4.3 Theory of Goncarov polynomials . . . . . . . . . . . . .
13.4.4 Classical parking functions . . . . . . . . . . . . . . . .
13.5 Parking functions associated with graphs . . . . . . . . . . . . . .
13.5.1G-parking functions . . . . . . . . . . . . . . . . . . . .
13.5.2 Abelian sandpile model . . . . . . . . . . . . . . . . . .
13.5.3 Multiparking functions, graph searching, and the Tutte
polynomial . . . . . . . . . . . . . . . . . . . . . . . . .
13.6 Final remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xvi Contents
14 Standard Young Tableaux 895
Ron Adin and Yuval Roichman
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.1.1 Appetizer . . . . . . . . . . . . . . . . . . . . . . . . .
14.1.2 General . . . . . . . . . . . . . . . . . . . . . . . . . .
14.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.2.1 Diagrams and tableaux . . . . . . . . . . . . . . . . . .
14.2.2 Connectedness and convexity . . . . . . . . . . . . . . .
14.2.3 Invariance under symmetry . . . . . . . . . . . . . . . .
14.2.4 Ordinary, skew and shifted shapes . . . . . . . . . . . . .
14.2.5 Interpretations . . . . . . . . . . . . . . . . . . . . . . .
14.2.5.1 The Young lattice . . . . . . . . . . . . . . .
14.2.5.2 Ballot sequences and lattice paths . . . . . . .
14.2.5.3 The order polytope . . . . . . . . . . . . . .
14.2.5.4 Other interpretations . . . . . . . . . . . . .
14.2.6 Miscellanea . . . . . . . . . . . . . . . . . . . . . . . .
14.3 Formulas for thin shapes . . . . . . . . . . . . . . . . . . . . . .
14.3.1 Hook shapes . . . . . . . . . . . . . . . . . . . . . . . .
14.3.2 Two-rowed shapes . . . . . . . . . . . . . . . . . . . . .
14.3.3 Zigzag shapes . . . . . . . . . . . . . . . . . . . . . . .
14.4 Jeu de taquin and the RS correspondence . . . . . . . . . . . . . .
14.4.1 Jeu de taquin . . . . . . . . . . . . . . . . . . . . . . . .
14.4.2 The Robinson-Schensted correspondence . . . . . . . . .
14.4.3 Enumerative applications . . . . . . . . . . . . . . . . .
14.5 Formulas for classical shapes . . . . . . . . . . . . . . . . . . . .
14.5.1 Ordinary shapes . . . . . . . . . . . . . . . . . . . . . .
14.5.2 Skew shapes . . . . . . . . . . . . . . . . . . . . . . . .
14.5.3 Shifted shapes . . . . . . . . . . . . . . . . . . . . . . .
14.6 More proofs of the hook length formula . . . . . . . . . . . . . .
14.6.1 A probabilistic proof . . . . . . . . . . . . . . . . . . .
14.6.2 Bijective proofs . . . . . . . . . . . . . . . . . . . . . .
14.6.3 Partial difference operators . . . . . . . . . . . . . . . .
14.7 Formulas for skew strips . . . . . . . . . . . . . . . . . . . . . .
14.7.1 Zigzag shapes . . . . . . . . . . . . . . . . . . . . . . .
14.7.2 Skew strips of constant width . . . . . . . . . . . . . . .
14.8 Truncated and other non-classical shapes . . . . . . . . . . . . . .
14.8.1 Truncated shifted staircase shape . . . . . . . . . . . . .
14.8.2 Truncated rectangular shapes . . . . . . . . . . . . . . .
14.8.3 Other truncated shapes . . . . . . . . . . . . . . . . . .
14.8.4 Proof approaches for truncated shapes . . . . . . . . . .
14.9 Rim hook and domino tableaux . . . . . . . . . . . . . . . . . . .
14.9.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . .
14.9.2 Ther-quotient andr-core . . . . . . . . . . . . . . . . .
14.10q-Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . .
14.10.1 Permutation statistics . . . . . . . . . . . . . . . . . . .

Contents xvii
14.10.2 Statistics on tableaux . . . . . . . . . . . . . . . . . . .
14.10.3 Thin shapes . . . . . . . . . . . . . . . . . . . . . . . .
14.10.3.1 Hook shapes . . . . . . . . . . . . . . . . . .
14.10.3.2 Zigzag shapes . . . . . . . . . . . . . . . . .
14.10.3.3 Two-rowed shapes . . . . . . . . . . . . . . .
14.10.4 The general case . . . . . . . . . . . . . . . . . . . . . .
14.10.4.1 Counting by descents . . . . . . . . . . . . .
14.10.4.2 Counting by major index . . . . . . . . . . .
14.10.4.3 Counting by inversions . . . . . . . . . . . .
14.11 Counting reduced words . . . . . . . . . . . . . . . . . . . . . .
14.11.1 Coxeter generators and reduced words . . . . . . . . . .
14.11.2 Ordinary and skew shapes . . . . . . . . . . . . . . . . .
14.11.3 Shifted shapes . . . . . . . . . . . . . . . . . . . . . . .
14.12 Appendix 1: Representation theoretic aspects . . . . . . . . . . .
14.12.1 Degrees and enumeration . . . . . . . . . . . . . . . . .
14.12.2 Characters andq-enumeration . . . . . . . . . . . . . . .
14.13 Appendix 2: Asymptotics and probabilistic aspects . . . . . . . .
15 Computer Algebra 975
Manuel Kauers
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.2 Computer algebra essentials . . . . . . . . . . . . . . . . . . . .
15.2.1 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . .
15.2.1.1 Integers and rational numbers . . . . . . . . .
15.2.1.2 Algebraic numbers . . . . . . . . . . . . . .
15.2.1.3 Real and complex numbers . . . . . . . . . .
15.2.1.4 Finite elds and modular arithmetic . . . . .
15.2.1.5 Lattice reduction . . . . . . . . . . . . . . .
15.2.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . .
15.2.2.1 Arithmetic and factorization . . . . . . . . .
15.2.2.2 Evaluation and interpolation . . . . . . . . .
15.2.2.3 Gr¨obner bases . . . . . . . . . . . . . . . . .
15.2.2.4 Cylindrical algebraic decomposition . . . . .
15.2.3 Formal power series . . . . . . . . . . . . . . . . . . . .
15.2.3.1 Truncated power series . . . . . . . . . . . .
15.2.3.2 Lazy power series . . . . . . . . . . . . . . .
15.2.3.3 Generalized series . . . . . . . . . . . . . . .
15.2.3.4 The multivariate case . . . . . . . . . . . . .
15.2.4 Operators . . . . . . . . . . . . . . . . . . . . . . . . .
15.2.4.1 Ore algebras . . . . . . . . . . . . . . . . . .
15.2.4.2 Actions and solutions . . . . . . . . . . . . .
15.3 Counting algorithms . . . . . . . . . . . . . . . . . . . . . . . .
15.3.1 Special purpose algorithms . . . . . . . . . . . . . . . .
15.3.2 Combinatorial species . . . . . . . . . . . . . . . . . . .
15.3.2.1 Formal denition and associated series . . . .

xviii Contents
15.3.2.2 Standard constructions . . . . . . . . . . . . 1000
15.3.2.3 Recursive specications . . . . . . . . . . . . 1002
15.3.3 Partition analysis . . . . . . . . . . . . . . . . . . . . . 1003
15.3.3.1W-Calculus . . . . . . . . . . . . . . . . . . 1003
15.3.3.2 Ehrhart theory . . . . . . . . . . . . . . . . . 1005
15.3.4 Computational group theory . . . . . . . . . . . . . . . . 1007
15.3.4.1 Permutation groups . . . . . . . . . . . . . . 1007
15.3.4.2 Finitely presented groups . . . . . . . . . . . 1008
15.3.5 Software . . . . . . . . . . . . . . . . . . . . . . . . . . 1010
15.4 Symbolic summation . . . . . . . . . . . . . . . . . . . . . . . . 1011
15.4.1 Classical algorithms . . . . . . . . . . . . . . . . . . . . 1011
15.4.1.1 Hypergeometric terms . . . . . . . . . . . . . 1011
15.4.1.2 Gosper's algorithm . . . . . . . . . . . . . . 1012
15.4.1.3 Zeilberger's algorithm . . . . . . . . . . . . . 1013
15.4.1.4 Petkovsek's algorithm . . . . . . . . . . . . . 1014
15.4.2PS-Theory . . . . . . . . . . . . . . . . . . . . . . . . . 1015
15.4.2.1PS-Expressions and difference elds . . . . . 1015
15.4.2.2 Indenite summation . . . . . . . . . . . . . 1017
15.4.2.3 Creative telescoping . . . . . . . . . . . . . . 1019
15.4.2.4 D'Alembertian solutions . . . . . . . . . . . 1020
15.4.2.5 Nested denite sums . . . . . . . . . . . . . 1021
15.4.3 The holonomic systems approach . . . . . . . . . . . . . 1021
15.4.3.1 D-nite and holonomic functions . . . . . . . 1022
15.4.3.2 Closure properties . . . . . . . . . . . . . . . 1023
15.4.3.3 Summation and integration . . . . . . . . . . 1025
15.4.3.4 Nested sums and integrals . . . . . . . . . . . 1026
15.4.4 Implementations and current research topics . . . . . . . 1027
15.5 The guess-and-prove paradigm . . . . . . . . . . . . . . . . . . . 1028
Index 1047

Foreword
When I rst became seriously interested in enumerative combinatorics around 1967,
the subject did not really existper se. There were numerous results and methods,
beginning with Euler (with some hints of even earlier work), scattered throughout the
literature, but there was little systematic attempt to bring some order to this chaos.
It is remarkable that enumerative combinatorics has progressed so far that we now
need over 1000 pages just to present a basic overview of techniques and results.
Numerous topics such as pattern avoidance and parking functions existed in only
very rudimentary form 4050 years ago but are now ourishing subjects in their own
right. The seventeen authors of the present volume, in addition to being world leaders
in the area of their contribution, are also superb writers. Their fteen chapters are a
combination of broad surveys of major areas and techniques, together with more
specialized expositions of many of the most active research topics in enumerative
combinatorics today.
A prominent reason why practitioners of enumerative combinatorics nd it so ap-
pealing is its unexpected connections with other areas of mathematics. These connec-
tions have grown increasingly sophisticated over the years. It is no longer sufcient
to know some rudimentary algebraic topology, say, to give a signicant connection
with enumerative combinatorics. The papers in this handbook do an exemplary job
of explaining deep connections with such areas as complex analysis, probability the-
ory, linear algebra, commutative algebra, representation theory, algebraic geometry,
algebraic topology, and computer science. Just this list of topics gives an idea of the
breadth and depth of modern enumerative combinatorics. Readers from neophytes to
experts have much to look forward to when they peruse the riches that follow.
Richard Stanley
Cambridge, MA
December 2014
xix

Discovering Diverse Content Through
Random Scribd Documents

De ha tudtam volna, sem akartam volna most az időt alvással
vesztegetni. Drágábbak ezek az órák. Nem az életből a tetszhalálba,
hanem a tetszhalálból az életbe átkelésre vannak ezek adva.
Fogjunk hozzá vakmerő munkánkhoz!
Első kisérletem az volt, hogy a nagy üvegprizma lapjait, melyben
a leányalak be volt zárva, egy másik szabadon fekvő kristálydarabbal
el kezdtem dörzsölni, hogy villanyosságba hozzam.
Ez sikerült. A prizma átvillanyosult a dörzsöléstől. Világítani
kezdett, csúcshegyéből villanyszikrák pattogtak elő. Hanem aztán a
kisérlet másik része egészen haszontalanná tette eddigi
működésemet. A villanyozott prizmának hideg vízzel leöntése
legkisebb hatással sem volt a kristályra. Egy repedés sem támadt
rajta.
Másként kellett hozzá fognom.
Foganatosítottam én már elégszer azt a feladatot, hogyan kell
egy elcsorbult üvegből pusztán tűz által a csorbarészt simára
leválasztani?
Előhoztam egyet azokból a szívós idegekből, a mik a cachelot
agyától a farkáig végig nyulnak, azt két felé vágtam, egyikkel
szorosan körülkötöttem azt a kristályoszlopot, mely a leányt zárta
körül; másikkal azt, melyben a férfi rejlett: egészen a talajnál, az
alakok lábain alul.
Akkor halzsírral körülöntöttem a két prizmát, betömve a réseket a
velem hozott éghetlen asbest-csomagokkal.
Azzal meggyújtottam a halzsirt.
Kezem tapintásával ügyeltem rá, hogy a hőség, mely az égő
halzsírtól támad, nem terjed-e tulságosan a prizma felső részeire. A
míg azt a kezem elállhatta, addig az a bennlakókra nézve sem
lehetett veszélyes. A kristály rossz melegvezető. Míg az alsó része
izzó, a felső hideg marad.

Mikor aztán a halzsir egészen ellángolt, akkor hirtelen oda
öntöttem a vizet a prizma alsó áthevitett részére.
És arra hangzott, mint a czitera-pengés, a kristály össze-vissza
repedezése mind a két kristály-oszlopnál. Sajátságos zenéjük van
ezeknek az ősvilági halottaknak, a hogy koporsójukat hangolják!
Mikor aztán egy pokrócz-darabbal siettem letörülni a füstöt az
egyik prizmáról, mely azt körül befeketítette, örültem is, nem is, a
kivívott eredménynek.
Az eddig tiszta átlátszó jegecz most egészen átlátszatlan lett.
Olyan volt, mint a kősó a só-kristályhoz képest: apróra össze-vissza
volt pattogva, s ez új törés ragyogott mint a fekete opál, mint a
köszörült halyotis csigahéj, mintha az egész tömeg egy darabokra
tört szivárvány volna; hanem a benne rejlő alakot most már egészen
eltakarta előlem.
Én tehát a műtétemmel csak azt nyertem, hogy a gyönyörű
bálványt, kit eddig legalább szemeimmel birtam, most már egészen
elvesztettem. Többé nem is láthatom már.
Hasonlóul járt a másik prizma is. A tűzvilágnál ezernyi ezer kék,
zöld, rózsaszín és viola sugár ragyogott át belőle; de emberarcz nem
látszott ki többé.
Én aztán megkisértém rést nyitni vésővel, kalapácscsal az
összepattogzott prizmán. (Természetesen az öregnél kezdtem.)
Hasztalan kisérlet volt az. A prizma azért egy darab maradt, egyetlen
felbonthatlan tömeg. Szétrepedezett alkatrészei úgy összefüggenek,
hogy azokat emberi hatalom szét nem választhatja.
De hát nem vagyok-e én szövetkezve emberen tuli hatalmakkal
is?
Mennyi idő van még hátra az ötven órából?
Csak az utolsó óra.

Leültem a kristálykoporsó lábához, s chronometeremet kezembe
véve, számláltam a perczeket.
A kénzsinegből csak az utolsó négy méternyi van hátra.
Annak már csak a fele számít. Mert a mint a tűz a sziklafokig
terjed a zsinegen, melyhez az kötve van, ott már az égő fonalat
elszakítja a lefüggő töltény súlya.
Tehát az utolsó arasznyi járja már csak.
Mikor annak vége, akkor a robbanó töltény aláhull a mélységbe s
a legelső sziklafokon, melyhez hozzá ütődik, szétdurran, s azzal azt
az egész üreget, mely naphthagázzal van megtöltve, fellobbantja. A
gyulladás kitör a jég alá, mely mérföldnyire alá van aknázva
kőolajjal. Millió és millió hektoliterei a petroleumnak robbannak szét
nehány percz lefolyása alatt. És én itt várom azt a rettengő ég-,
föld-, hegy-, víz-, jégösszeszakadást nyugodt lélekkel.
Nem! Nem nyugodt lélekkel. Mentől közelebb jött a válságos
óranegyed, szivem annál nyugtalanabbul dobogott. Fejem fölé
nehezült az a gondolat, hogy én most vakmerő kézzel felzavarok egy
világot, melyet a teremtő az örökalvók számára rendezett el!
Reszketés fogott el. Nyugtalan állati ösztön vett rajtam erőt. Az
utolsó óranegyedben szerettem volna megakadályozni, a mit
elkezdettem: odafutni, eloltani a kanóczot, visszavenni a mélység
fölött függő röppentyűt. De már késő volt.
Ekkor aztán a halálos rettegés egyesült bennem azzal az örjöngő
vágygyal, mely vakmerő tettemre lázított; odarohantam ahhoz a
prizmához, melybe az a csábító nő-alak volt bezárva, azt átöleltem
két karommal: «ha összeomlik fölöttem a világ, a te koporsód zúzzon
engem agyon!»
… Ettől fogva örökkévalóságnak tetszettek előttem a perczek. A
vadállat is meglapult lábamnál s még nyöszörögni sem mert.

Hallgatóztam, lélekzetem is visszafojtva. Talán nem sült el a
töltény? Talán kialudt a hozzávezető kénzsineg? Talán meg sem
gyújtotta azt a gyutacs?
Egyszerre aztán megrendült alattam az egész kristálybarlang!
A rázkódás hamarább ideért, mint a kitörés hangja.
Oly rázkódás volt ez, a minőt leirni lehetetlen. Apró és sűrű, de
folytonosan növekedő erőszakos zökkentések, melyek érzékeimet
káprázatba hozták.
És annak a rázkódásnak is volt hangja. Csendes, kisértetes,
kimagyarázhatlan hang; hasonló azon ritkán hallott zengéshez, mit
az észak-fény hallat, vagy a mit a Memnon szobrok kisugárzanak; a
mit a földindulást megelőző szél mint fütyülés kisér, vagy nagy
madárszárnyak suhogása. A döngő kristályok életrekelő hangja az:
külön tán nem is hallható, mint a mozgó falevél zizegése, de együtt
egyetemesen: felzendülő hang, mint mikor egy egész erdő falevele
zúg.
Nemsoká tartott az: nehány másodpercz mulva elnyomták azt az
irtóztató csattanások és dörgések a föld felett és a föld alatt.
Most van az, hogy felrobbant az egész gáztömeg a nagy
kőszénüregben s a kráter torkán kilövellő lángoszlop vitássá teszi az
északfénynek a mennyországot s egyszerre leolvasztja a hegyről az
örök jeget, hogy a leomló zuhatagok egy új özönvíz rétegével
temetik be a völgyeket, még egyszer összekeverve egymással a már
többször is eltemetett őslények csontjait.
Most a kapott taszítástól végig rendül az egész szárazföld. A
czethal barlangja a boltozatáig telik meg egy percz alatt tengervízzel.
A jégtorlaszok összetörnek, s a szárazföld elválik a jég-continenstől.
Most a petroleum-forrás felgyújtja az egymásra épült jégtorlaszok
üregeiben rejlő naphtát, mely nem fagy meg együtt a vízzel. Nem
egyszerre gyullad meg az: mérföldről mérföldre terjed odább. A
jégpaloták, a jégvárromok, zegzugos tornyaikkal, előrefüggő

félboltozataikkal, a tündérek Alhambrái, mennydörögve omlanak
egymásra, s a fölöttük összecsapó hullám lángokkal boritja be
tornyaikat, miket ki nem olt sem víz, sem jég. S a lezuhanó
jéghegyeket odacsapkodja a felháborított tenger a szárazföld
előfokaihoz, sziklapartjaihoz. A gázvolkán üvölt, a föld üregei
bömbölnek, a tenger harsog, a jég mennydörög, a bazaltok
ropognak. A tűz és jég közé szorult fókák, czethalak halálos
rémülettől ordítanak, s ez itéletnapi karzenének rettenetes accordjait
sírbolti rémzengéssel kiséri az engemet rejtő kristály-pinczegömb,
ezernyi ezer csengő orgonasípjával, a kristály tömeg hangot ád a
rázkodásban, mint a hegedűvonóval megvont üveglap, s a
szabadonlevő kristályok tánczra kerekednek benne, szabályos
mértani alakzatokba csoportosulva.
S egy erős hang néha képes szét is törni az üveget, kivált ha az
hirtelen van kihütve.
Egyszerre csak e szörnyű rázkodástól szétomlott a karjaimmal
átölelve tartott kristályprizma, millió darabra hullott, szikraesőként
rugva szét csengő morzsáit. S karjaim között maradt az ősvilági lény.
Épen, sértetlenül, a hogy æonok előtt a kristály magába zárta.
Ez a pillanat elfeledteté velem az egész itéletnapi zajt, mely
körülem zengett és ropogott: nem érzettem mást, mint azt a
villanyütést, mely minden idegemet átjárta, midőn ez alak karjaimba
hullott.
Nem volt halott. Tagjai még hajlottak.
Mit éreztem? Egy leányt a karjaim között, ki két év óta nem
láttam női arczot. Egy alvó leányt, ki a világtörténet kezdete előtt
hunyta le álomra szemeit.
Talán ez ősférfi itt e másik prizmában maga az őspatriarcha,
«Lámekh,» s ez a hajadon nem más, mint a szép «Czilla» leánya:
«Naháma».
Elneveztem őket Lámekhnak és Nahámának.

Nem halott, nem hulla, nem mumia volt az karjaim között: egy
«elrejtőzött» szűz. «Az elrejtőzés» mysteriuma az ősmagyarok előtt
is ismeretes volt. Vallásukban volt az. Fiatal szűzek átmentek a
halálba, s visszatértek a túlvilágról s nyilvánításokat hoztak onnan
magukkal.
Nem halt meg a leány, csak alszik.
Odavittem őt az elkészített fekhelyre.
Birtokában voltam a legősrégibb halálélesztő szernek. Ez az
ambra.
Már a chaldæiak ismerték ezt, mint élethosszító szert, s a
máguszok halálból feltámasztó csodatételei ennek a segélyével
mentek végbe. Jugurtha meghalt leányát egy évvel halála után
ambrával hozták ismét életre. Baruch Hageb öcscsét, Szeimet,
trónját féltve tőle, élve záratá el koporsóba, de máguszai csak
elaltatták azt s Baruch Hageb halála után előhozták, ambrával
föléleszték s úgy ültették trónra. Szolejmán császárt az ulémák
Szigetvár ostromakor ambrával költötték fel halálából, hogy a
csüggeteg hadseregnek még egyszer élve mutassa meg magát.
Cleopatra örök fiatalságát az ambrának köszönheté. Az ambra
minden életerőt felfokoz. Ifjuvá tesz és boldoggá. Richelieu késő
vénségeig ambra-pastilleokat rágott. Az ambra mindent feltámaszt, a
mi csak elrejtőzött, de még feloszlásba nem ment.
Hanem az ambra életfeltámasztása «uraknak való». Egy egész
emberi test bedörzsöléséhez kell négy uncia ambraolaj, s az száz
uncia ambrából izzasztható ki.
Nekem volt benne módom. Nyolczszáz uncia ambrát találtam a
physeter gyomrában s ez még nyers volt. Izzasztás nélkül, puszta
nyomással ki lehetett belőle sajtolni az ambra-olajat, mely az igazi
ambrából egy gombostűszúrásra szokott megjelenni.
Valami leirhatatlan édes balzsamillat az, a mit az ambraolaj
terjeszt; mely az idegeket kéjesen csiklandozza, hogy az ember

megittasul a lélekzetén keresztül. Valóban mámorosnak kellett
lennem, midőn elkezdtem énekelni. A XLVI. zsoltár zsolozsmája jött
ajkaimra:

«Azért az én szivem nem félne
Bár az egész föld megrendülne,
Bár a hegyek a tengernek.
Közepébe bedülnének!»
Körülem reng a talaj a boltozattal együtt: a sziklák harczot
viselnek egymással, a tűz a jéggel, – és én itt a föld mélységeiben
énekelek! Ez a földdarab, melynek terhe vagyok, elsülyedéssel
fenyeget minden perczben s én akkor indulok neki, hogy az ő
halottait föltámaszszam.
– Oh Ábrahámnak, Jákobnak, Izsáknak Istene, szentséges
Jehova, kölcsönözd nekem életadó lehelletedet!
Térdre roskadtam élő-halott bálványom előtt.
Egyesülnie kellett a vakmerő műtéthez az isteni csodatétel
jelenségeivel a prózai gyógykezelés minden fogásainak.
Legelőször is, hogy bedörzsölhessem a bőr felhámjába az ambra-
olajat, kénytelen voltam a körül betakaró sűrű hajzatot lebontani a
halálalvó tagjairól. Egy márványszobor bársonytapintattal!
Reményem fokozódott.
Alulról, a lábtól kezdve, és háttal fordítva kellett az ambra-olajjal
bedörzsölést intéznem.
Először, kisérletül egy folton erősen feldörzsöltem a bőr
felhámját, s az a folt piros lett. Ez az élet színe.
Legutoljára került a sor az arczra, a halántékokra.
A beszívott ambraillat, a hevítő munka, a bűbájos alak látása
minden érzékemet a csodáig magasztosítá fel.
A mi körülvesz is, mind oly bámulatraméltó!
A földrengés folytonos vibratiója által az egész kristálybarlang
minden prizmája villanyossá lesz s elkezd világítani. Az egyetemes

kisúgárzás sokszorozott szivárvány karikákat kezd képezni
köröskörül, a mik lassankint közelítenek felém s az alvó lényhez,
mint egy pávafark fényrétegei, mik körülvesznek bennünket, mint
egy holdudvar, mint egy glória. A roppant nagyságú
hegykristálytömbök villanynyal túltelve, gyémántvillámokat lövelnek
a boltozat felé, s e vakító színpompa közepett csendesen libeg végig
egy fehér felleg: az elégett halolaj füstje, mely kijárást nem találva a
boltüregből, mint egy hófehér szellem szállong, vonzva és eltaszítva
a delejvillanyos falaktól.
S a vibratiónak hangja, mint a távol mennyország karzenéje kél
titokteljesen az örök kristályokból, leirhatatlan, emberi érzékektől
elviselhetetlen hangösszesség; csodálatos harmoniája a zengő
köveknek, mely az emberi ideget együtt érezni készti, s a szemekből
a könyet kicsordítja.
És közbe-közbe felharsan a volcán torkából az itéletnap hirdető
angyalok sírbontó trombitája s a mennydörgés rettentő dobütése.
Szivem, lelkem reszket, minden érzékem emberfölötti titkok
közellétét érzi, fényben, hangban, illatban, delejerőben.
– Ébredj fel! Ébredj fel! Ébredj fel! kiáltok elragadtatással a
karjaim között tartott alaknak.
Még a vadállat is érzi e jelenet elvarázsló igézetét.
Az a felmagasztaló bűbáj, mely belőlem, emberből, églakót
csinál: őt, a fenevadot az ember magaslatáig emeli. Két lábra áll;
első lábait összetéve mellén, mintha tudna imádkozni, s felnyitott
szája az emberi síráshoz, jajszóhoz, nyögéshez hasonló hangokban
válogat.
– Támadj fel!
… Most odatartottam fülemet szívgödrére s úgy tetszett, mintha
hallanám azt a neszt, a minek a neve még nem szívdobogás, csak
szívhang.

A mint végre arczát és szemehéját is bedörzsöltem az
ambraolajjal, egyszerre csendesen megnyíltak ajkai; olyan volt az,
mint egy rózsa titokteljes kinyílása a hajnalsugárnál.
Én felsikoltottam az üdvösséghez hasonló örömtől.
Zengjétek dalaitokat kristályok tovább, harsogtassátok
trombitáitokat angyalok odafenn: az ember diadalmaskodik!
Folytattam az ambrabedörzsölést a hónaljak alatt, s erre a két
felemelt kar, mely imára kulcsolt kezekkel folyvást fejére volt
szorítva, csendesen aláhanyatlott, úgy, hogy a két összekulcsolt kéz
az én fejemet takarta be.
Most már megdicsőülve éreztem magamat egészen. Szájamat
ajkaira tettem, hogy levegőt fújjak tüdejébe s a lélekzetvételt
megindítsam benne, míg kezemmel a szívdobbanás megindulását
kémleltem.
Ez oly ünnepélyes percz volt, hogy még a sziklatömegek is
megszüntek rázkódni nehány pillanatig, mintha azt lesnék, hogyan
tér vissza a földre egy lélek, a ki már az égben meghonosult?
hogyan születik meg a kristály közepett a szívdobbanás?
És megszületett!
Az első szívdobbanás.
Nem akartam hinni kezemnek, fülemet tartottam oda.
Ismét egy szívdobbanás. Számláltam. Öt percz mulva ismét egy,
s aztán minden öt perczben egy.
Két imára kulcsolt keze most a keblén nyugodott.
Szája mindjobban felnyilt.
Megkisértém nehány csepp vízzel higított borszeszt, melyben
ambra volt felolvasztva, tölteni a szájába s féloldalt fordítám, hogy a
nyelv ne gátolja a nedv lecsuszását.

Erre lassan felnyitá szemeit. Nagy sötétkék szemek voltak,
egészen kitágult pupillákkal, de még merően néztek maguk elé. Még
nem láttak, csak meredtek.
Ekkor balkezemet feje alá tettem, azt fölemelve, s jobb kezem
tenyerével fölfelé a szívig dörzsöltem tagjait.
Erre ismét lehunyta szemeit, de észrevehetően elkezdett
lélekzeni.
Tagjai hajlékonyak lettek, de nem mozdultak.
Most az utolsó kisérletet vettem elő.
Jéghideg vizet locscsantottam arczára.
Ez, mint egy galvanicus ütés hatott az alvóra; karjai és lábszárai
egyszerre fölrándultak és szemei felnyiltak.
Fölébredt. Ez már élet volt. Ez már látás volt. Ez már eszmélet
volt.
S a legelső, a mit látott, egy férfi volt, s a legelső eszmélet, a mit
érzett, a szemérem volt, a legelső mozdulat, a mit kezeivel tett, az
volt, hogy a mint gyönyörü hajpalástja szétterítve hevert ott
mellette, azt két kezével hirtelen felkapta, és betakarta vele magát.
Aztán összeborzadt, s egész teste ludbőrössé vált. Most már
fázott!
Én aztán egy mennyezetet csináltam számára egy darab
cachelot-bőrből, mit két jégoszlopra vetettem, hogy eltakarja a
világosságot előle. Azután odahuztam Bábit; megértettem vele, hogy
neki oda kell feküdni a leány fejéhez.
Akkor aztán a szép szemérmetes Nahámát felöleltem s oda
fektettem a medve ölébe, ki mint egy roppant szultáni kerevet terült
el alatta. A leány nem félt tőle, odabujt hozzá. S a kerevet meleget is
ád. Az állatmeleg gyógyerővel bir. És a hű vadállat megértett engem.
Hiszen végignézte egész küzködésemet. Nyüzsögve, nyihogva

hizelkedett neki, mint a hogy az anyamedve szokta magához
csalogatni a kölykét. Talán az ősvilágban, mielőtt Tubalkain (épen a
szép Naháma bátyja) feltalálta a fegyverkovácsolást, az emberek és
vadállatok nem éltek oly nagy ellenségeskedésben, mint most. Bábi
elértette, hogy mit várok tőle? Addig ölelgette magához a
gyermekien félénk emberi teremtést, míg egészen megnyerte annak
a bizalmát s elvégre annyira magához édesgette, hogy az lett rá
nézve, a mi volt Romulus és Remusnak az anyafarkas. Bábi beállt
szoptatós dajkának az újszülött gyermekem mellé. S annak valóban
anyatej kellett; minden más étel elölte volna újraébredő
életszervezetét.
Azután lehajtá a gyermek szép fejét csodálatos dajkája ölébe,
betakarózott a hajával és elaludt.
Még szavát nem hallottam, nem tudtam, mi nyelven beszél?
A kristályok tömege tovább zengte az alvó csecsemő felett a
túlvilági dajkazenét.
A KŐBE NŐTT APÓS.
Naháma valóban csodálatos teremtés volt. Valami középlény a
ma született gyermek, a vadállat és a szemérmes szűz között. A
gyanutlanság és félénkség, a szelidség és makacsság keveréke.
Minden indulat kezdetleges nála. Lehet belőle egész nőt s egész
vadállatot csinálni. S tanulmányozni kell a szeszélyeit, mint egy
anyának a csecsemőét, a ki még nem tud beszélni, a ki csak a
hanglejtésből ért, és csak különböző hangú sírással, nyüzsgéssel,
nyafogással, gyügyögéssel tudja kifejezni akaratát, s ezerféle
makrancza van, s a mellett elpirul a férfiszem nézésétől s hiu
tetszelgéssel illesztgeti a halhártya-peplumot magára, mely bájait
eltakarja. Mintha két lelke volna; egyik a tegnap született öntudatlan
csecsemő-lélek, másik a visszaemlékező, a hajadon
szívdobbanásaival együtt élő szellem.

Nagyon kényesen kellett vele bánnom.
Ahhoz hamar hozzászokott, hogy Bábival úgy bánjék, mint
anyjával; szavakat annak sem mondott, csupán annak a hangjait
utánozta. De ha én közelítettem felé, a kényelmetlenség jelei
látszottak arczán, s bár megkisértém a gyöngédség minden
hanglejtésén keresztül egyes szavakat mondani el előtte, azokat nem
mondta el utánam.
Pedig azért kiváncsi volt rám.
Mikor lefeküdtem aludni, a medve tulsó oldalára, úgy tettem,
mintha már aludnám, odahajolt a medvén át fölém, és elnézett
hosszan; mikor pedig egy dörzsgyufát elgyujtottam, olyankor
leborult előttem arczczal a földre, azt hitte, én vagyok az, a ki
villámlani tud.
Odaadtam neki vas- és réz-eszközeimet, mik számára játékszerek
voltak, s bemutattam, hogy mit tudok a furulyán. A dal nagyon
tetszett neki. Azon nevetett.
Heteket töltöttünk már együtt a kristálypinczében. Élelmi szerem
elég volt. Sajt, füstölt nyelv, veseconserve. Naháma pedig még
mindig szopott.
Elhagyni a kristálybarlangot még mindig nem volt tanácsos. A
barlang folyvást gyönge rázkódás alatt volt, s azt koronkint egyes
heves lökések szakíták félbe.
Naháma ezt mind bölcső-ringatásnak vette.
Lassankint mégis annyira mentem vele, hogy a kezét meghagyta
fogni. Erre nagy szükség volt, hogy a körmeit levághassam, a mik
időtlen idők óta annyira megnőttek, mintha sas-karmok volnának.
Ennek a nagy nyereménynek valami ára volt,
Iszákomból elővettem a velem hozott amianthot. A gyönyörü
csillogó kőselyem, mely motringokat képez termés alakban, nagyon

megnyerte a tetszését. Azután guzsalyt, orsót faragtam neki
cachelot-inakból. S megmutattam, hogyan kell az asbestet megfonni.
Ez nagyon megtetszett neki. De a fonásban gátul vannak a nagy
körmök. Azokat hát feláldozta ennek a kedvtöltésének s azután font
egyre vékony fonalat, a míg csak az asbestben tartott.
Akkor azután négy halszálkából készítettem neki kötőtűket s
megtanítottam harisnyát kötni.
Ez nem nevetni való tréfa!
Nekünk azokra az asbest-harisnyákra nagy szükségünk lesz majd.
Egyszer már megkisértettem, mikor a földrengés szünetet tartott,
kiindulni kémszemlészetre a kristálybarlangból. Meg akartam tudni,
hogy vajjon nem rekedtem-e ide?
Az út palarétegeken keresztül most a nagy rázkódás után még
jobban nyitva állt. Sokkal közelebb folyosón jutottam el a bazalt-
barlangig.
Ott azonban arra a megdöbbentő tapasztalatra jutottam, hogy
most már épen nehéz lesz rajta keresztülhatolni.
A barlang hőmérséke már nem lett volna oly elviselhetetlen.
Leszállt az egész ötven fokra, s fenn az oszlopok közt rés támadt,
melyen át a külső hideg lég szállt alá.
Hanem más baj támadt. Az, hogy a nagy földrendülés a szélső
bazaltoszlopok közül egy egész sort aládöntött s az most, mint egy
óriási dobogó, hidalja át a barlangot.
De köszönöm én az ilyen arany hidat. A bazaltoszlopok még most
is oly forrók, hogy azokon Bábi tán keresztül tud szaladni, a ki alig ér
a lábával a talajhoz; de a ki embermódra jár, minden lépésnél jól
odanyomva a talpát, az vargát ránt, mire a túlpartra ér.
Tehát azért kellett, hogy Naháma mindkettőnk számára asbest-
harisnyákat kössön. Az éghetlen kőselyem-lábtyüvel bizton keresztül

mehetünk majd az izzó hidon.
Hogy az öreg Lámekh benne maradt a kristályban, azt ugyan
sajnáltam nagyon, de valamennyi jelenlevő kovarcz legyen a tanum,
hogy nem tehetek róla. Én az ő koporsóját is megporhanyítottam, ha
az nem omlott szét, az a prædestinatio dolga.
Egyszer azonban, a midőn mindhárman álomnak adtuk
magunkat, egy újabb földrendítő lökés úgy megmozdította az egész
barlangunkat, hogy az egy tömegben, a hogy gömbbé volt
kandirozva, hintálni kezdett, úgy, hogy mi fekhelyünkből ki jobbra, ki
balra gurultunk széjjel.
A lökés rövid ideig tartott s aztán ismét csend lett. Én
meggyujtottam elébb a Davy-lámpámat, hogy bizonyossá legyek
felőle, vajjon nem tört-e be valahol a barlang boltozatja; midőn a
rögtön támadó világosságnál egy új, bámulatos látvány lepett meg.
Azon prizma, melybe Lámekh volt elzárva, az újabb földlökés
alatt összeomlott, s az ősapa alakja ott volt a prizma helyén, de nem
felállva mint eddig, se nem lefekve, hanem ülve.
A prizma nem omlott szét tökéletesen; egy repedés volt rajta
keresztben, odáig morzsává lett, ott élesen elvált s az alsó része
megmaradt tömör darabnak, s abban, mint egy kalodában maradt
fogva az emberi alak. Mindene kiszabadult, csak térdeitől lefelé
maradt összenőve a kristálylyal; termete aztán ülő helyzetben
roskadt a kristálytönkre.
– Nézz oda! mondám Nahámának, kezét megragadva s a
kristályban ülő alakra mutatva.
A leány erre éles sikoltással rohant az ülő alakhoz s megragadva
annak ökölre szorított kezeit, elkezdte azokat csókolni, s most már
kiabált hozzá valamit, de a zokogás érthetetlenné tette szavait.
Hanem a szavak hangja elmondá, hogy a gyermek örül a feltaláltnak
és siratja az elvesztettet, a ki élettelenül ült előtte.
Én odasiettem hozzá s azt mondám neki:

– Akarod, hogy föléleszszem őt?
Megértette szándékomat, lábaimhoz borult és térdeimet
átkarolta.
– Jól van, tehát segíts!
Nem gondoltam hirtelen arra, hogy minő bolond helyzet lesz
abból, ha fölelevenítek egy embert, a kinek a két lába térdig bele
van nőve egy kristály-csonkba, a miből soha sem lehet kiszabadítani.
Elővettem sikerkoronázta tudományomat. Bőven bántam az
ambrával. De az öregnél nem olajat használtam, hanem spiritusban
felolvasztott ambrát, az jobban behatolt lompos gyapjuhordó bőrén,
a mit nagyobb siker végett keresztül is szurkáltam tűvel, a szájába is
nagyobb adag ambraszeszt töltöttem s karjait mozgatva, mechanice
erőszakoltam nála a lélekzetvétel újra megkezdését, bevégezve a
műtételt a fejére öntött hideg vizzel; mire a fehér gyapjas alak
egyszerre elkezdett egy nagyot prüszszenteni, és aztán prüszszentett
egymásután nem tudom én hányat? Nem értem rá azt számlálni,
mert abban a pillanatban, a midőn az öreg életre támadt, a leány
felugrott mellőlem, hol addig guggolva bámulva ült, és azzal rohant
– nem az életrekölthöz, hanem hozzám a feltámasztóhoz; leveté
magát előttem arczra, átkarolta térdeimet s aztán hozzáfogott
csókolni, a lábaim hegyén kezdve, fel egész a homlokomig, folyvást
ölelve kebléhez és önkivületben lihegve.
Nem számláltam én sem a prüszszentést, sem a csókot.
Utoljára aztán ott maradt, karjait a nyakam körül füzve és
zokogott.
Ezt már értettem.
LEÁNYKÉRÉS ÖZÖNVÍZELŐTTI MÓDON.

A föléledt patriarcha is szavához jött ezalatt, bár szava olyan volt,
mintha a föld alól jönne; ércztelen, rekedt suttogás volt az inkább,
csuklórikácsolással vegyítve.
Az első szava ez volt hozzám:
«Amhááretz!»
Megörültem neki.
Hisz ez érthető nyelven volt mondva. Valaha, míg a theologiából
meg nem szöktem, engem is tápláltak a héber nyelvvel. Ez zsidóul
van. Egy pár szót most is értek belőle. Ezt az elsőt például mindjárt.
Az ugyan nem igen hizelgő megszólítás, mert azt teszi, hogy «te
bolond!»
Következett még több is.
Az öreg, alig hogy mumiából emberré lett megint, egész hajdani
aristocraticus hajlamát visszanyerte, elhalmozott rekedt hangja
gunyszavakkal, a mikből leginkább megértettem azt, hogy
«Neszierim!» (rabszolga), «Keraim!» (hitetlen).
Egy párszor «mamszer»-nek is nevezett, a mi csunya megbántás.
Sejtettem, hogy azért szid, a miért a leányával ily bizalmas lábon
merek állani, s többször ütögetett a mellére, azt kiáltotta, hogy ő egy
«Cohen!»
Most már bántam nagyon, hogy a Zichyföldön tettem ezt a
felfedezési merényletet, itt még nem hivatkozhatom a polgári
házasságra, ez csak a Ferencz-Józsefföld Lajthán-túli részére nézve
érvényes.
A szép Naháma segélyemre kelt.
Egy kezét vállamra tevé, másik kezének mutatóujját homlokához
emelte s ünnepélyes hangon e szóval mutatott be az öregnek:

– Jore deah. (Tudós.)
– Ssed! (Ördög szava) kiálta a húszezer éves apó.
– Ed! (Tanu) felelt a leány, önkeblére mutatva.
– Makkót mardót! hörgé az öreg a bősz átokkiáltást, melylyel a
becstelen leányokat, kik egy idegen férfit megcsókoltak, szokták a
korbácsbüntetésnek átadni. (Az özönvíz előtt.) Makkót mardót!
süvölté még egyszer az öreg, mire a leány engedelmesen lehajolt a
lábainál heverő czethalidegért, hogy azt korbácsul nyujtsa az
öregnek, és meghagyja vele ostorozni magát. Én elvettem tőle a
korbácsot s odadtam az öregapámnak, de a lányt nem eresztettem
hozzá közel, hogy megverje. Az öreg aztán a kristálytönköt verte a
korbácscsal. Azt lehet.
Ekkor én is megakartam mutatni, hogy értek a nyelvén s
mellemre ütve mondám magamról:
– Reach! (fejedelem) s azzal megfogva a leány kezét, kimondám
nagy ünnepélyesen a Chalizeh alkalmából ellesett végzetes jelszót,
de tagadó ige nélkül.
– Le kachta! (Nőül veszem.)
«Meachssow!» felelt rá hirtelen a leány, kezemet visszaszorítva
mind a két kezével.
«Almanath!» hörgé a tetőtől talpig megőszült ember.
«Meachssow!» ismétlé a leány.
«Almanath!»
Ötször-hatszor elmondták egymásnak ezt a két fatalis szót, mely
a rögtöni, vagy későbbi házasságkötés volt, a «Meachssow» azt
jelenti: «mátulfogva», az «almanath» azt, hogy «attulfogva».
Végre az öreg özönvizelőtti haragra gerjedve, kiáltá e rettentő
igét, kezét leánya felé kinyujtva:

«Erwah!»
A leány elsápadt ennél a szónál; egészen elváltozott a szine, ajkai
elkékültek, arczát eltakarta hosszú hajával.
Ez a szó olyan nő jelent, a kinek tiltva van férjhez menni.
Én elszántan léptem az öreg elé s szemébe néztem a XIX-ik
századbeli bátorsággal.
Erre az öreg plyocenei ravasz vigyorgással szőrös ábrázatján
morzsolá ki e szót fogai alól:
«Katlánneth!»
E szóra a leány leesett a földre, szétzilálta a haját és
kristályhomokot szórva a fejére, elkezdett jajgatni keservesen.
A Katlánneth olyan szűzet jelent, a kinek már több vőlegénye
egymásután a menyegző előtt elhalt: Katlánneth azt jelenti, hogy
«férfiölő!» az ilyen szűznek többé férjhez igérkezni nem szabad.
«Bánom is én, ha Katlánneth vagy is, rubintom!» mondék már
most a magam nyelvén a leánynak s odasiettem őt felvenni a földről.
Ketten vagyunk az egész világon, nincs a mi számunkra törvény! s
ha csak törvény kell, majd hozunk. Magam vagyok itt alsóház,
felsőház és király. De bizony elveszlek, ha hozzám jösz.
Erre aztán az öreg elkezdett sirni keservesen. Tenyereivel a
kristálytönkre ütögetett s többször mondá e szót: «Galóth».
(Fogság.)
Ez azt jelenti, hogy a míg a családfő fogságban van, addig a
család leányának menyegzőt ülni nem szabad.
Szegény öreg! Azon volt hát megijedve, hogy ha a leányát
elveszem, ő itt marad magára, a kristályba befoglalva.
Az iránt megvigasztaltam. Előhoztam vésőmet, kalapácsomat,
oda térdeltem elé, s mutattam neki, hogy én azzal a két eszközzel ki

tudom őt a kényszerhelyzetből szabadítani. Egy darabot próbául le is
zúztam a kristály széléből.
Erre elérzékenyült és megáldott e szókkal, a mik a házasságba
beleegyezést jelentik.
«Beer hetibb!» (örvendetes hir!)
A mint azonban e szónál Naháma is odajött mellém, hirtelen
megfogta a patriarcha a leány karját csontujjaival s oda vonta őt
maga mellé a kristálytuskóra, nekem pedig azt sugta:
«Keszubba!»
«Keszubba!» De hát ki az ördög látta hogy az özönviz előtti
emberek is keszubbáról beszéljenek? Én azt gondoltam, hogy az
özönviz előtt ingyen adták a leányt!
De az öreg csak a fejét rázta s ismételte, a markát tartva elém:
«Keszubba! – Keszubba!»
(Ez, a mit mi móringnak, nászajándéknak nevezünk.)
«No hát itt van, nesze: fogjad.»
Ezzel előkerestem neki azt a gyönyörű labrador kristályt az
iszákomból. Nagyon megörült neki s a markába szorította. Hanem
azt mondta rá:
«Kájim li.»
«Kájim li!» Hát ezt is tudod? Hiszen te csak kiadod magadat
özönvizelőtti embernek! Nem vagy te homo primigenius! Hiszen te
úgy tudod a Schulchán Áruchot könyv nélkül!»
«Kájim li» szóval szokta az após megtartani magának a leányért
kapott ajándékot, s ha a leányának adja azt, akkor annak a neve
«parnasza». Ezzel a szóval takargatta azt bele az öreg Naháma
chlamysának szögletébe s akkor megint felém fordult ezzel a szóval:

«Sekukim!»
«Oh mi a tüzes patkószeg? Még Sekukim? Ennek ezüst is kell!»
Mit volt mit tennem. Volt egy ezüst óralánczom, azt levettem a
nyakamból s átnyujtám neki.
Ez egészen megnyerte a tetszését, az ezüst lánczot Naháma
karja körül fonta, mingyárt a válla alatt s azzal gyönyörködve nézett
rajta végig, s végül ráadta a hét áldást.
Csak azután következett a «Chupa», a mit az öreg el nem
engedett.
A chupa a mennyezet, mely a házasságot szentesíti. Azt hamar
kiállítottam a czethalbőrből, melyet négy kristályoszlopra
kifeszítettem. E nélkül nem lehettem «hoszen» (vőlegény).
E mennyezet alatt keltem össze a szép «Kálémmal», kinek azért
nem kellett levágni a haját, szerencsére az özönvíz előtt még nem
levén feltalálva az olló.
Mindezeket az ügyeket elébb rendén el kellett végeznem, mielőtt
arra gondolhattam volna, hogy az életrehozott embernek valami
üdítő italt adjak, a mire pedig nagy szüksége lehetett. Énokh
patriarcha idejétől mostanáig szomjazni: nem tréfa dolog.
Sejtettem, hogy ősi szokásai között az is meglesz, hogy a saját
ivóedényén kivül másból nem iszik. Azért vésővel kifeszítettem a
kristály közül az emlitett dinornistojás héját, mely maga is apró
kristályok rétegével volt bevonva. Az még akkor is tele volt valami
apró, gombostűfej nagyságú barna ocsuval. Én azt szemétnek
néztem s kiöntöttem. Naháma azonban odajött s szépen felszedte az
öltönyébe az elszórt szemetet, türelmesen. (Most már feleségem
volt.)
Én aztán tele töltöttem a féltojáshéjat friss vizzel, a mi közé egy
kevés czethaltejet kevertem s nehány csepp ambraszeszt adtam

hozzá. Az öreg mohón ivott belőle s háladatosan forgatta szemeit az
ég felé.
Azután nekem nyujtotta a kelyhet az ivásra, tőlem Nahámára
köszöntötte azt s mikor üres lett a dinornis tojáshéj, akkor, hogy
semmi se maradjon el a házassági szertartásból, a földhöz csapta azt
mindkét kézzel.
Szerencsére a dinornis tojáshéjnak volt annyi esze, hogy nem
törött szét; ruganyos volt. S ez nem a tojáshéj szerencséje volt,
hanem ipam uramé; mert különben nem tudom, miből adtam volna
neki ezentul inni, miután ő az én bádogedényemtől irtózott. Az
ételektől pedig, a miket kináltam neki, még jobban.
Nem kellett annak se medvegulyáshús, se cachelot nyelv, se
czethalsajt, csak egy kivánsága volt:
«Parperoth!»
Ez a hagyományos növényétel, mely nélkül meg nem történhetik
lakodalom az özönvíz előtti emberek között. Parperoth nélkül nincs
áldás a házasságon, parperoth nélkül ünnepelt menyegzőből
amhaáretz utódok származnak, parperoth nélkül Asmódi
garázdálkodik a házastársak között.
De hát hol vegyem én a parperothot? Azt sem tudom, hogy mi az
a parperoth? De ha tudnám is, hogy mi az a parperoth? Nem terem
ebben az országban semmiféle növény. Ennek az egész botanicai
gazdagsága: moha és zuzmó. Ha te itt növénynyel akarsz élni öreg,
felkopik az állad.
Az öreg pedig türelmetlen volt. Bizonyosan király lehetett valaha,
a ki e szót «lehetetlen» nem ismeré. Szidott és hadonászott a
pálczájával. Szerencsénkre úgy oda volt nőve a trónjához, hogy nem
szállhatott le róla.
Naháma az alatt, mint csendes, engedelmes, parancsfogadó
alattvaló, nem szólt semmit, letérdelt ős apja mellé, vizet öntött a

tojáshéjba, s aztán a kötényéből egy csipetet kivett abból a
haszontalan szemétből, a mit én kiöntöttem s belekeverte a vizbe.
Néhány percz mulva bámulva láttam, hogy azok a gombostűfej
apróságok elkezdenek duzzadni, egyre nőnek, megdagadnak
mogyoró nagyságura, a rájuk öntött víz egészen eltünik s a helyén
egy rezgő, kocsonyás átlátszó tömeg marad, melynek lila kékes szine
van.
Mikor ez meglett, akkor két tenyerére tette a természetes edényt
s azzal az utánozhatlan édes mosolylyal, a mi a nőkkel veleszületik,
odanyujtá azt az öreg elé.
Az öregnek reszketett a szakálla az örömtől: szemeit
gyönyörteljesen hunyta le, mikor az istenadta ételhez hozzá nyult.
Ez a manna!
Most már rá ismertem.
Ez a Lecanora esculenta, melylyel az Ararát sziklái fedve vannak,
s melyet néha roppant csoportokban ragad fel a zivatar, s száz
mértföldnyi messzeségre eső pusztákban elszórja azt. A zuzmó a
fellegek nedvétől feldagad kocsonyává s mikor lehull, kész terített
asztalt ad a pusztában bujdosónak; arasznyi vastagon takarva a
földet.
Ez a puszták mannája! Ezzel lát el még most is egész vidékeket
az ég, a hogy ezt a tudós Thenard a párisi tudományos akadémiában
előadta.
És ezt mi, ujkori emberek, nem vettük eddig figyelembe: pedig ez
egy oly élelmi szer, melyből egy maroknyi egy egész hajó
népségének elég.
Megizlelém a maradékot. Igen kellemes jó izű kocsonya volt az,
kevés kesernyésséggel. Naháma látta, hogy izlik, s aztán
mindkettőnk számára készített új fogást.

Welcome to our website – the ideal destination for book lovers and
knowledge seekers. With a mission to inspire endlessly, we offer a
vast collection of books, ranging from classic literary works to
specialized publications, self-development books, and children's
literature. Each book is a new journey of discovery, expanding
knowledge and enriching the soul of the reade
Our website is not just a platform for buying books, but a bridge
connecting readers to the timeless values of culture and wisdom. With
an elegant, user-friendly interface and an intelligent search system,
we are committed to providing a quick and convenient shopping
experience. Additionally, our special promotions and home delivery
services ensure that you save time and fully enjoy the joy of reading.
Let us accompany you on the journey of exploring knowledge and
personal growth!
ebookfinal.com

Handbook of Enumerative Combinatorics 1st Edition Miklós Bóna (Editor)

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Handbook of Enumerative Combinatorics 1st Edition Miklós Bóna (Editor)

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

TLE-9-Prepare-Salad-and-Dressing.pptxkkk

LESSON 1 ABOUT MEDIA AND INFORMATION.pptx

GRADE-8-AQUACULTURE-WEEKQ1.pdfdfawgwyrsewru

Feelings PP Game FOR CHILDREN IN ELEMENTARY SCHOOL.pptx

Jeopardy_Figures_of_Speech_Template.pptx [Autosaved].pptx

Jeopardy_Figures_of_Speech.pptxvdsvdsvsdvsd