Combinatorics and Number Theory of Counting Sequences (Discrete Mathematics and Its Applications)

Cover
Half Title
Series Page
Title Page
Copyright Page
Dedication
Contents
Foreword
About the Author
Part I: Counting sequences related to set partitions and permutations
	1. Set partitions and permutation cycles
		1.1 Partitions and Bell numbers
		1.2 Partitions with a given number of blocks and the Stirling numbers of the second kind
		1.3 Permutations and factorials
		1.4 Permutation with a given number of cycles and the Stirling numbers of the first kind
		1.5 Connections between the first and second kind Stirling numbers
		1.6 Some further results with respect to the Stirling numbers
			1.6.1 Rhyme schemes
			1.6.2 Functions on finite sets
		1.7 d-regular partitions
		1.8 Zigzag permutations
			1.8.1 Zigzag permutations and trees
		Exercises
		Outlook
	2. Generating functions
		2.1 On the generating functions in general
		2.2 Operations on generating functions
			2.2.1 Addition and multiplication
			2.2.2 Some additional transformations
			2.2.3 Differentiation and integration
			2.2.4 Where do the name generating functions come from?
		2.3 The binomial transformation
		2.4 Applications of the above techniques
			2.4.1 The exponential generating function of the Bell numbers
			2.4.2 Dobi´nski’s formula
			2.4.3 The exponential generating function of the second kind Stirling numbers
			2.4.4 The ordinary generating function of the second kind Stirling numbers
			2.4.5 The generating function of the Bell numbers and a formula for {n, k}
			2.4.6 The exponential generating function of the first kind Stirling numbers
			2.4.7 Some particular lower parameters of the first kind Stirling numbers
		2.5 Additional identities coming from the generating functions
		2.6 Orthogonality
		2.7 Horizontal generating functions and polynomial identities
			2.7.1 Special values of the Stirling numbers of the first kind - second approach
		2.8 The Lah numbers
			2.8.1 The combinatorial meaning of the Lah numbers
		2.9 The total number of ordered lists and the horizontal sum of the Lah numbers
		2.10 The Hankel transform
			2.10.1 The Euler-Seidel matrices
			2.10.2 A generating function tool to calculate the Hankel transform
			2.10.3 Another tool to calculate the Hankel transform involving orthogonal polynomials
		Exercises
		Outlook
	3. The Bell polynomials
		3.1 Basic properties of the Bell polynomials
			3.1.1 A recursion
			3.1.2 The exponential generating function
		3.2 About the zeros of the Bell polynomials
			3.2.1 The real zero property
			3.2.2 The sum and product of the zeros of Bn(x)
			3.2.3 The irreducibility of Bn(x)
			3.2.4 The density of the zeros of Bn(x)
			3.2.5 Summation relations for the zeros of Bn(x)
		3.3 Generalized Bell polynomials
		3.4 Idempotent numbers and involutions
		3.5 A summation formula for the Bell polynomials
		3.6 The Fa`a di Bruno formula
		Exercises
		Outlook
	4. Unimodality, log-concavity, and log-convexity
		4.1 “Global behavior” of combinatorial sequences
		4.2 Unimodality and log-concavity
		4.3 Log-concavity of the Stirling numbers of the second kind
		4.4 The log-concavity of the Lah numbers
		4.5 Log-convexity
			4.5.1 The log-convexity of the Bell numbers
			4.5.2 The Bender-Canfield theorem
		Exercises
		Outlook
	5. The Bernoulli and Cauchy numbers
		5.1 Power sums
			5.1.1 Power sums of arithmetic progressions
		5.2 The Bernoulli numbers
			5.2.1 The Bernoulli polynomials
		5.3 The Cauchy numbers and Riordan arrays
			5.3.1 The Cauchy numbers of the first and second kind
			5.3.2 Riordan arrays
			5.3.3 Some identities for the Cauchy numbers
		Exercises
		Outlook
	6. Ordered partitions
		6.1 Ordered partitions and the Fubini numbers
			6.1.1 The definition of the Fubini numbers
			6.1.2 Two more interpretations of the Fubini numbers
			6.1.3 The Fubini numbers count chains of subsets
			6.1.4 The generating function of the Fubini numbers
			6.1.5 The Hankel determinants of the Fubini numbers
		6.2 Fubini polynomials
		6.3 Permutations, ascents, and the Eulerian numbers
			6.3.1 Ascents, descents, and runs
			6.3.2 The definition of the Eulerian numbers
			6.3.3 The basic recursion for the Eulerian numbers
			6.3.4 Worpitzky’s identity
			6.3.5 A relation between Eulerian numbers and Stirling numbers
		6.4 The combination lock game
		6.5 Relations between the Eulerian and Fubini polynomials
		6.6 An application of the Eulerian polynomials
		6.7 Differential equation of the Eulerian polynomials
			6.7.1 An application of the Fubini polynomials
		Exercises
		Outlook
	7. Asymptotics and inequalities
		7.1 The Bonferroni-inequality
		7.2 The asymptotics of the second kind Stirling numbers
			7.2.1 First approach
			7.2.2 Second approach
		7.3 The asymptotics of the maximizing index of the Stirling numbers of the second kind
			7.3.1 The Euler Gamma function and the Digamma function
			7.3.2 The asymptotics of Kn
		7.4 The asymptotics of the first kind Stirling numbers and Bell numbers
		7.5 The asymptotics of the Fubini numbers
		7.6 Inequalities
			7.6.1 Polynomials with roots inside the unit disk
			7.6.2 Polynomials and interlacing zeros
			7.6.3 Estimations on the ratio of two consecutive sequence elements
			7.6.4 Dixon’s theorem
			7.6.5 Colucci’s theorem and the Samuelson–Laguerre theorem and estimations for the leftmost zeros of polynomials
			7.6.6 An estimation between two consecutive Fubini numbers via Lax’s theorem
		Exercises
		Outlook
Part II: Generalizations of our counting sequences
	8. Prohibiting elements from being together
		8.1 Partitions with restrictions – second kind r-Stirling numbers
		8.2 Generating functions of the r-Stirling numbers
		8.3 The r-Bell numbers and polynomials
		8.4 The generating function of the r-Bell polynomials
			8.4.1 The hypergeometric function
		8.5 The r-Fubini numbers and r-Eulerian numbers
		8.6 The r-Eulerian numbers and polynomials
		8.7 The combinatorial interpretation of the r-Eulerian numbers
		8.8 Permutations with restrictions – r-Stirling numbers of the first kind
		8.9 The hyperharmonic numbers
		Exercises
		Outlook
	9. Avoidance of big substructures
		9.1 The Bessel numbers
		9.2 The generating functions of the Bessel numbers
		9.3 The number of partitions with blocks of size at most two
		9.4 Young diagrams and Young tableaux
		9.5 The differential equation of the Bessel polynomials
		9.6 Blocks of maximal size m
		9.7 The restricted Bell numbers
		9.8 The gift exchange problem
		9.9 The restricted Stirling numbers of the first kind
		Exercises
		Outlook
	10. Avoidance of small substructures
		10.1 Associated Stirling numbers of the second kind
			10.1.1 The associated Bell numbers and polynomials
		10.2 The associated Stirling numbers of the first kind
			10.2.1 The associated factorials An,=m
			10.2.2 The derangement numbers
		10.3 Universal Stirling numbers of the second kind
		10.4 Universal Stirling numbers of the first kind
		Exercises
		Outlook
Part III: Number theoretical properties
	11. Congruences
		11.1 The notion of congruence
		11.2 The parity of the binomial coefficients
			11.2.1 The Stolarsky-Harborth constant
		11.3 Lucas congruence for the binomial coefficients
		11.4 The parity of the Stirling numbers
		11.5 Stirling numbers with prime parameters
			11.5.1 Wilson’s theorem
			11.5.2 Wolstenholme’s theorem
			11.5.3 Wolstenholme’s theorem for the harmonic numbers
			11.5.4 Wolstenholme’s primes
			11.5.5 Wolstenholme’s theorem for Hp-1,2
		11.6 Lucas congruence for the Stirling numbers of both kinds
			11.6.1 The first kind Stirling number case
			11.6.2 The second kind Stirling number case
		11.7 Divisibility properties of the Bell numbers
			11.7.1 Theorems about Bp and Bp+1
			11.7.2 Touchard’s congruence
		11.8 Divisibility properties of the Fubini numbers
			11.8.1 Elementary congruences
			11.8.2 A Touchard-like congruence
			11.8.3 The Gross-Kaufman-Poonen congruences
		11.9 Kurepa’s conjecture
		11.10 The non-integral property of the harmonic and hyperharmonic numbers
			11.10.1 Hn is not integer when n > 1
			11.10.2 The 2-adic norm of the hyperharmonic numbers
			11.10.3 H1 + H2 + · · · + Hn is not integer when n > 1
		Exercises
		Outlook
	12. Congruences via finite field methods
		12.1 An application of the Hankel matrices
		12.2 The characteristic polynomials
			12.2.1 Representation of mod p sequences via the zeros of their characteristic polynomials
			12.2.2 The Bell numbers modulo 2 and 3
			12.2.3 General periodicity modulo p
			12.2.4 Shortest period of the Fubini numbers
		12.3 The minimal polynomial
			12.3.1 The Berlekamp – Massey algorithm
		12.4 Periodicity with respect to composite moduli
			12.4.1 Chinese remainder theorem
			12.4.2 The Bell numbers modulo 10
		12.5 Value distributions modulo p
			12.5.1 The Bell numbers modulo p
		Exercises
		Outlook
	13. Diophantic results
		13.1 Value distribution in the Pascal triangle
			13.1.1 Lind’s construction
			13.1.2 The number of occurrences of a positive integer
			13.1.3 Singmaster’s conjecture
		13.2 Equal values in the Pascal triangle
			13.2.1 The history of the equation (n k)=(m l)
			13.2.2 The particular case (n 3)=(m 4)
		13.3 Value distribution in the Stirling triangles
			13.3.1 Stirling triangle of the second kind
			13.3.2 Stirling triangle of the first kind
		13.4 Equal values in the Stirling triangles and some related diophantine equations
			13.4.1 The Ramanujan-Nagell equation
			13.4.2 The diophantine equation {n n-3} = {m m-1}
			13.4.3 A diophantic equation involving factorials and triangular numbers
			13.4.4 The Klazar – Luca theorem
		Exercises
		Outlook
Appendix
	Basic combinatorial notions
	The polynomial theorem
	The Lambert W function
	function
Formulas
Tables
Bibliography
Index