DISCRETE MATHEMATICS AND ITS APPLICATIONS

By M. GIORU

CONTENTS NO WAY AROUND IT INTRODUCTION 1 IN ONE LINE AND CLOSE PERMUTATIONS AS LINEAR ORDERS RUNS DESCENTS THE DEFINITION OF DESCENTS EULERIAN NUMBERS STIRLING NUMBERS AND EULERIAN NUMBERS GENERATING FUNCTIONS AND EULERIAN NUMBERS THE SEQUENCE OF EULERIAN NUMBERS ALTERNATING RUNS EXERCISES PROBLEMS PLUS SOLUTIONS TO PROBLEMS PLUS 2 IN ONE LINE AND ANYWHERE PERMUTATIONS AS LINEAR ORDERS INVERSIONS INVERSIONS THE GENERATING FUNCTION OF PERMUTATIONS BY INVERSIONS MAJOR INDEX AN APPLICATION: DETERMINANTS AND GRAPHS INVERSIONS IN PERMUTATIONS OF MULTISETS INVERSIONS AND GAUSSIAN COEFFICIENTS MAJOR INDEX AND PERMUTATIONS OF MULTISETS 3 IN MANY CIRCLES PERMUTATIONS AS PRODUCTS OF CYCLES DECOMPOSING A PERMUTATION INTO CYCLES AN APPLICATION: SIGN AND DETERMINANTS AN APPLICATION: GEOMETRIC TRANSFORMATIONS TYPE AND STIRLING NUMBERS THE TYPE OF A PERMUTATION AN APPLICATION: CONJUGATE PERMUTATIONS AN APPLICATION: TREES AND TRANSPOSITIONS PERMUTATIONS WITH A GIVEN NUMBER OF CYCLES GENERATING FUNCTIONS FOR STIRLING NUMBERS AN APPLICATION: REAL ZEROS AND PROBABILITY CYCLE DECOMPOSITION VERSUS LINEAR ORDER THE TRANSITION LEMMA APPLICATIONS OF THE TRANSITION LEMMA PERMUTATIONS WITH RESTRICTED CYCLE STRUCTURE THE EXPONENTIAL FORMULA THE CYCLE INDEX AND ITS APPLICATIONS 4 IN ANY WAY BUT THIS PATTERN AVOIDANCE THE BASICS THE NOTION OF PATTERN AVOIDANCE PATTERNS OF LENGTH THREE MONOTONE PATTERNS PATTERNS OF LENGTH FOUR THE PATTERN THE PROOF OF THE STANLEY-WILF CONJECTURE THE FÜREDI-HAJNAL CONJECTURE AVOIDING MATRICES VS AVOIDING PERMUTATIONS THE PROOF OF THE FÜREDI-HAJNAL CONJECTURE 5 IN THIS WAY, BUT NICELY PATTERN AVOIDANCE FOLLOWUP POLYNOMIAL RECURSIONS POLYNOMIALLY RECURSIVE FUNCTIONS CLOSED CLASSES OF PERMUTATIONS ALGEBRAIC AND RATIONAL POWER SERIES THE P-RECURSIVENESS OF SN,R(132) CONTAINING A PATTERN MANY TIMES PACKING DENSITIES LAYERED PATTERNS CONTAINING A PATTERN A GIVEN NUMBER OF TIMES A CONSTRUCTION WITH A GIVEN NUMBER OF COPIES 6 MEAN AND INSENSITIVE RANDOM PERMUTATIONS THE PROBABILISTIC VIEWPOINT STANDARD YOUNG TABLEAUX EXPECTATION LINEARITY OF EXPECTATION VARIANCE AND STANDARD DEVIATION AN APPLICATION: LONGEST INCREASING SUBSEQUENCES 7 PERMUTATIONS VS EVERYTHING ELSE ALGEBRAIC COMBINATORICS OF PERMUTATIONS THE ROBINSON-SCHENSTED-KNUTH CORRESPONDENCE POSETS OF PERMUTATIONS 7 2 1 POSETS ON SN 7 2 2 POSETS ON PATTERN AVOIDING PERMUTATIONS 7 2 3 AN INFINITE POSET OF PERMUTATIONS SIMPLICIAL COMPLEXES OF PERMUTATIONS 7 3 1 A SIMPLICIAL COMPLEX OF RESTRICTED PERMUTATIONS 7 3 2 A SIMPLICIAL COMPLEX OF ALL N-PERMUTATIONS 8 GET THEM ALL ALGORITHMS AND PERMUTATIONS GENERATING PERMUTATIONS GENERATING ALL N-PERMUTATIONS GENERATING RESTRICTED PERMUTATIONS STACK SORTING PERMUTATIONS 2-STACK SORTABLE PERMUTATIONS T-STACK SORTABLE PERMUTATIONS UNIMODALITY VARIATIONS OF STACK SORTING DO NOT LOOK JUST YET SOLUTIONS TO ODD-NUMBERED EXERCISES SOLUTIONS FOR CHAPTER REFERENCES