1st Edition

Combinatorics of Set Partitions

By Toufik Mansour Copyright 2013
    516 Pages 38 B/W Illustrations
    by Chapman & Hall

    Focusing on a very active area of mathematical research in the last decade, Combinatorics of Set Partitions presents methods used in the combinatorics of pattern avoidance and pattern enumeration in set partitions. Designed for students and researchers in discrete mathematics, the book is a one-stop reference on the results and research activities of set partitions from 1500 A.D. to today.

    Each chapter gives historical perspectives and contrasts different approaches, including generating functions, kernel method, block decomposition method, generating tree, and Wilf equivalences. Methods and definitions are illustrated with worked examples and Maple™ code. End-of-chapter problems often draw on data from published papers and the author’s extensive research in this field. The text also explores research directions that extend the results discussed. C++ programs and output tables are listed in the appendices and available for download on the author’s web page.

    Introduction
    Historical Overview and Earliest Results
    Timeline of Research for Set Partitions
    A More Detailed Book

    Basic Tools of the Book
    Sequences
    Solving Recurrence Relations

    Generating Functions
    Lagrange Inversion Formula
    The Principle of Inclusion and Exclusion
    Generating Trees

    Preliminary Results on Set Partitions
    Dobiński’s Formula
    Different Representations

    Subword Statistics on Set Partitions
    Subword Patterns of Size Two: Rises, Levels and Descents
    Peaks and Valleys
    Subword Patterns: -Rises, -Levels, and -Descents
    Families of Subword Patterns
    Patterns of Size Three

    Nonsubword Statistics on Set Partitions
    Statistics and Block Representation
    Statistics and Canonical and Rook Representations
    Records and Weak Records
    Number of Positions between Adjacent Occurrences of a Letter
    The Internal Statistic
    Statistics and Generalized Patterns
    Major Index
    Number of Crossings, Nestings and Alignments

    Avoidance of Patterns in Set Partitions
    History and Connections
    Avoidance of Subsequence Patterns
    Generalized Patterns
    Partially Ordered Patterns

    Multi Restrictions on Set Partitions
    Avoiding a Pattern of Size Three and Another Pattern
    Pattern Avoidance in Noncrossing Set Partitions
    General Equivalences
    Two Patterns of Size Four
    Left Motzkin Numbers
    Sequence A054391
    Catalan and Generalized Catalan Numbers
    Pell Numbers
    Regular Set Partitions
    Distance Restrictions
    Singletons
    Block-Connected

    Asymptotics and Random Set Partition
    Tools from Probability Theory
    Tools from Complex Analysis
    Z-Statistics
    Set Partitions as Geometric Words
    Asymptotics for Set Partitions

    Gray Codes, Loopless Algorithms and Set Partitions
    Gray Code and Loopless Algorithms
    Gray Codes for Pn
    Loopless Algorithm for Generating Pn

    Set Partitions and Normal Ordering
    Preliminaries
    Linear Representation and N((aa)n)
    Wick’s Theorem and q-Normal Ordering
    p-Normal Ordering
    Noncrossing Normal Ordering

    Appendices

    Bibliography

    Index

    Exercises, Research Directions, and Open Problems appear at the end of each chapter.

    Biography

    Toufik Mansour is a professor in the Department of Mathematics at the University of Haifa. Dr. Mansour has authored/co-authored more than 200 papers and is a reviewer for many journals, including Advances in Applied Mathematics, Discrete Mathematics, Discrete Applied Mathematics, European Journal of Combinatorics, and the Journal of Combinatorial Theory Series A. His research focuses on pattern avoidance in permutations, colored permutations, set partitions, words, and compositions.

    "Containing 375 references, this book works best as an encyclopedia for researchers working in this topic. But it can also be effectively used by students who are interested in the combinatorics of set partitions and want to get a hand on researching them. … a very useful reference for researchers of the enumerative side of set partitions."
    Acta Sci. Math. (Szeged), 80, 2014

    "… a comprehensive account of the history and current research in the combinatorics of pattern enumeration and pattern avoidance in set partitions. … While it is aimed primarily at advanced undergraduate and graduate students in discrete mathematics with a focus on set partitions, its extensive bibliography, with 375 entries, and the variety of constructions and approaches used in the text make it a valuable reference for researchers in this field."
    —Ricardo Mamede, Zentralblatt MATH 1261

    "… a comprehensive account of recent and current research on the pattern-related aspects of set partitions."
    —David Callan, Mathematical Reviews, April 2013