Atnaujinkite slapukų nuostatas

Combinatorics and Number Theory of Counting Sequences [Kietas viršelis]

  • Formatas: Hardback, 498 pages, aukštis x plotis: 234x156 mm, weight: 544 g, 10 Illustrations, black and white
  • Serija: Discrete Mathematics and Its Applications
  • Išleidimo metai: 20-Aug-2019
  • Leidėjas: CRC Press
  • ISBN-10: 1138564850
  • ISBN-13: 9781138564855
Kitos knygos pagal šią temą:
Combinatorics and Number Theory of Counting SequencesDidesnis paveikslėlis
  • Formatas: Hardback, 498 pages, aukštis x plotis: 234x156 mm, weight: 544 g, 10 Illustrations, black and white
  • Serija: Discrete Mathematics and Its Applications
  • Išleidimo metai: 20-Aug-2019
  • Leidėjas: CRC Press
  • ISBN-10: 1138564850
  • ISBN-13: 9781138564855
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9781138564855.html
Raktažodžiai:
Combinatorics and Number Theory of Counting Sequences is an introduction to the theory of finite set partitions and to the enumeration of cycle decompositions of permutations.

The presentation prioritizes elementary enumerative proofs. Therefore, parts of the book are designed so that even those high school students and teachers who are interested in combinatorics can have the benefit of them. Still, the book collects vast, up-to-date information for many counting sequences (especially, related to set partitions and permutations), so it is a must-have piece for those mathematicians who do research on enumerative combinatorics.

In addition, the book contains number theoretical results on counting sequences of set partitions and permutations, so number theorists who would like to see nice applications of their area of interest in combinatorics will enjoy the book, too.

Features











The Outlook sections at the end of each chapter guide the reader towards topics not covered in the book, and many of the Outlook items point towards new research problems.





An extensive bibliography and tables at the end make the book usable as a standard reference.





Citations to results which were scattered in the literature now become easy, because huge parts of the book (especially in parts II and III) appear in book form for the first time.

Recenzijos

This book provides an interesting introduction to combinatorics by employing number-theoretic techniques of counting sequences. The level of the presentation often seems elementary, as the author frequently throws out lagniappes suitable for high school students. The text unfolds in three parts. Part 1 covers set partitions, generating functions, Bell polynomials, log-concavity, log-convexity, Bernoulli and Cauchy numbers, ordered partitions, asymptotes, and related inequalities. Part 2 discusses generalizations of counting sequences in three chapters. The final part considers number theoretical properties, including congruences, by way of finite field methods and Diophantine results. Each chapter concludes with an "Outlook" section that gives suggestions about exploring additional topics not covered in the text. Mathematical proof is used throughout the exposition and tends to be "enumerative," again contributing to a sense that the author hopes to engage mathematical novices through this text. However, the more than 250 exercises included in the book are frequently challenging and always interesting. The bibliography comprises more than 600 entries. Anyone who can follow the text is likely to enjoy working through the book. -D. P. Turner, Faulkner University

Foreword xv
About the Author xvii
I Counting sequences related to set partitions and permutations 1(194)
1 Set partitions and permutation cycles
3(30)
1.1 Partitions and Bell numbers
3(3)
1.2 Partitions with a given number of blocks and the Stirling numbers of the second kind
6(4)
1.3 Permutations and factorials
10(1)
1.4 Permutation with a given number of cycles and the Stirling numbers of the first kind
11(4)
1.5 Connections between the first and second kind Stirling numbers
15(1)
1.6 Some further results with respect to the Stirling numbers
16(2)
1.6.1 Rhyme schemes
16(1)
1.6.2 Functions on finite sets
16(2)
1.7 d-regular partitions
18(3)
1.8 Zigzag permutations
21(5)
1.8.1 Zigzag permutations and trees
23(3)
Exercises
26(3)
Outlook
29(4)
2 Generating functions
33(52)
2.1 On the generating functions in general
33(2)
2.2 Operations on generating functions
35(7)
2.2.1 Addition and multiplication
35(3)
2.2.2 Some additional transformations
38(1)
2.2.3 Differentiation and integration
38(2)
2.2.4 Where do the name generating functions come from?
40(2)
2.3 The binomial transformation
42(3)
2.4 Applications of the above techniques
45(8)
2.4.1 The exponential generating function of the Bell numbers
45(1)
2.4.2 Dobinski's formula
46(1)
2.4.3 The exponential generating function of the second kind Stirling numbers
46(3)
2.4.4 The ordinary generating function of the second kind Stirling numbers
49(1)
2.4.5 The generating function of the Bell numbers and a formula for {nk}
50(2)
2.4.6 The exponential generating function of the first kind Stirling numbers
52(1)
2.4.7 Some particular lower parameters of the first kind Stirling numbers
52(1)
2.5 Additional identities coming from the generating functions
53(3)
2.6 Orthogonality
56(3)
2.7 Horizontal generating functions and polynomial identities
59(5)
2.7.1 Special values of the Stirling numbers of the first kind - second approach
63(1)
2.8 The Lah numbers
64(4)
2.8.1 The combinatorial meaning of the Lah numbers
66(2)
2.9 The total number of ordered lists and the horizontal sum of the Lah numbers
68(2)
2.10 The Hankel transform
70(9)
2.10.1 The Euler-Seidel matrices
71(2)
2.10.2 A generating function tool to calculate the Hankel transform
73(2)
2.10.3 Another tool to calculate the Hankel transform involving orthogonal polynomials
75(4)
Exercises
79(4)
Outlook
83(2)
3 The Bell polynomials
85(20)
3.1 Basic properties of the Bell polynomials
85(3)
3.1.1 A recursion
85(1)
3.1.2 The exponential generating function
86(2)
3.2 About the zeros of the Bell polynomials
88(7)
3.2.1 The real zero property
88(1)
3.2.2 The sum and product of the zeros of Bn(x)
89(1)
3.2.3 The irreducibility of Bn(x)
90(1)
3.2.4 The density of the zeros of Bn(x)
90(2)
3.2.5 Summation relations for the zeros of Bn(x)
92(3)
3.3 Generalized Bell polynomials
95(1)
3.4 Idempotent numbers and involutions
96(3)
3.5 A summation formula for the Bell polynomials
99(1)
3.6 The Fah di Bruno formula
99(2)
Exercises
101(3)
Outlook
104(1)
4 Unimodality, log-concavity, and log-convexity
105(18)
4.1 "Global behavior" of combinatorial sequences
105(1)
4.2 Unimodality and log-concavity
106(3)
4.3 Log-concavity of the Stirling numbers of the second kind
109(3)
4.4 The log-concavity of the Lah numbers
112(2)
4.5 Log-convexity
114(3)
4.5.1 The log-convexity of the Bell numbers
114(1)
4.5.2 The Bender-Canfield theorem
115(2)
Exercises
117(2)
Outlook
119(4)
5 The Bernoulli and Cauchy numbers
123(18)
5.1 Power sums
123(3)
5.1.1 Power sums of arithmetic progressions
126(1)
5.2 The Bernoulli numbers
126(4)
5.2.1 The Bernoulli polynomials
128(2)
5.3 The Cauchy numbers and Riordan arrays
130(7)
5.3.1 The Cauchy numbers of the first and second kind
130(2)
5.3.2 Riordan arrays
132(2)
5.3.3 Some identities for the Cauchy numbers
134(3)
Exercises
137(2)
Outlook
139(2)
6 Ordered partitions
141(26)
6.1 Ordered partitions and the Fubini numbers
141(4)
6.1.1 The definition of the Fubini numbers
141(1)
6.1.2 Two more interpretations of the Fubini numbers
142(1)
6.1.3 The Fubini numbers count chains of subsets
143(1)
6.1.4 The generating function of the Fubini numbers
143(1)
6.1.5 The Hankel determinants of the Fubini numbers
144(1)
6.2 Fubini polynomials
145(2)
6.3 Permutations, ascents, and the Eulerian numbers
147(6)
6.3.1 Ascents, descents, and runs
148(1)
6.3.2 The definition of the Eulerian numbers
149(1)
6.3.3 The basic recursion for the Eulerian numbers
150(1)
6.3.4 Worpitzky's identity
150(2)
6.3.5 A relation between Eulerian numbers and Stirling numbers
152(1)
6.4 The combination lock game
153(2)
6.5 Relations between the Eulerian and Fubini polynomials
155(2)
6.6 An application of the Eulerian polynomials
157(1)
6.7 Differential equation of the Eulerian polynomials
158(3)
6.7.1 An application of the Fubini polynomials
159(2)
Exercises
161(3)
Outlook
164(3)
7 Asymptotics and inequalities
167(28)
7.1 The Bonferroni-inequality
168(2)
7.2 The asymptotics of the second kind Stirling numbers
170(3)
7.2.1 First approach
170(2)
7.2.2 Second approach
172(1)
7.3 The asymptotics of the maximizing index of the Stirling numbers of the second kind
173(4)
7.3.1 The Euler Gamma function and the Digamma function
174(1)
7.3.2 The asymptotics of Kn
175(2)
7.4 The asymptotics of the first kind Stirling numbers and Bell numbers
177(2)
7.5 The asymptotics of the Fubini numbers
179(2)
7.6 Inequalities
181(10)
7.6.1 Polynomials with roots inside the unit disk
181(1)
7.6.2 Polynomials and interlacing zeros
182(1)
7.6.3 Estimations on the ratio of two consecutive sequence elements
182(2)
7.6.4 Dixon's theorem
184(1)
7.6.5 Colucci's theorem and the Samuelson-Laguerre theorem and estimations for the leftmost zeros of polynomials
185(4)
7.6.6 An estimation between two consecutive Fubini numbers via Lax's theorem
189(2)
Exercises
191(2)
Outlook
193(2)
II Generalizations of our counting sequences 195(100)
8 Prohibiting elements from being together
197(42)
8.1 Partitions with restrictions - second kind r-Stirling numbers
197(3)
8.2 Generating functions of the r-Stirling numbers
200(4)
8.3 The r-Bell numbers and polynomials
204(3)
8.4 The generating function of the r-Bell polynomials
207(3)
8.4.1 The hypergeometric function
207(3)
8.5 The r-Fubini numbers and r-Eulerian numbers
210(5)
8.6 The r-Eulerian numbers and polynomials
215(3)
8.7 The combinatorial interpretation of the r-Eulerian numbers
218(3)
8.8 Permutations with restrictions - r-Stirling numbers of the first kind
221(4)
8.9 The hyperharmonic numbers
225(5)
Exercises
230(3)
Outlook
233(6)
9 Avoidance of big substructures
239(28)
9.1 The Bessel numbers
239(1)
9.2 The generating functions of the Bessel numbers
240(2)
9.3 The number of partitions with blocks of size at most two
242(2)
9.4 Young diagrams and Young tableaux
244(3)
9.5 The differential equation of the Bessel polynomials
247(2)
9.6 Blocks of maximal size in
249(2)
9.7 The restricted Bell numbers
251(1)
9.8 The gift exchange problem
252(3)
9.9 The restricted Stirling numbers of the first kind
255(6)
Exercises
261(4)
Outlook
265(2)
10 Avoidance of small substructures
267(28)
10.1 Associated Stirling numbers of the second kind
267(6)
10.1.1 The associated Bell numbers and polynomials
271(2)
10.2 The associated Stirling numbers of the first kind
273(6)
10.2.1 The associated factorials An,> or = to m
274(1)
10.2.2 The derangement numbers
275(4)
10.3 Universal Stirling numbers of the second kind
279(5)
10.4 Universal Stirling numbers of the first kind
284(2)
Exercises
286(5)
Outlook
291(4)
III Number theoretical properties 295(86)
11 Congruences
297(44)
11.1 The notion of congruence
297(1)
11.2 The parity of the binomial coefficients
298(1)
11.2.1 The Stolarsky-Harborth constant
299(1)
11.3 Lucas congruence for the binomial coefficients
299(2)
11.4 The parity of the Stirling numbers
301(2)
11.5 Stirling numbers with prime parameters
303(6)
11.5.1 Wilson's theorem
304(1)
11.5.2 Wolstenholme's theorem
305(1)
11.5.3 Wolstenholme's theorem for the harmonic numbers
305(1)
11.5.4 Wolstenholme's primes
306(1)
11.5.5 Wolstenholme's theorem for Hp-1,2
306(3)
11.6 Lucas congruence for the Stirling numbers of both kinds
309(2)
11.6.1 The first kind Stirling number case
309(2)
11.6.2 The second kind Stirling number case
311(1)
11.7 Divisibility properties of the Bell numbers
311(2)
11.7.1 Theorems about Bp and Bp+1
311(1)
11.7.2 Touchard's congruence
312(1)
11.8 Divisibility properties of the Fubini numbers
313(3)
11.8.1 Elementary congruences
313(1)
11.8.2 A Touchard-like congruence
314(1)
11.8.3 The Gross-Kaufman-Poonen congruences
315(1)
11.9 Kurepa's conjecture
316(2)
11.10 The non-integral property of the harmonic and hyperharmonic numbers
318(7)
11.10.1 Hn is not integer when n > 1
319(2)
11.10.2 The 2-adic norm of the hyperharmonic numbers
321(2)
11.10.3 H1 + H2 + ... + Hn is not integer when n > 1
323(2)
Exercises
325(4)
Outlook
329(12)
12 Congruences via finite field methods
341(22)
12.1 An application of the Hankel matrices
341(3)
12.2 The characteristic polynomials
344(6)
12.2.1 Representation of mod p sequences via the zeros of their characteristic polynomials
345(1)
12.2.2 The Bell numbers modulo 2 and 3
346(2)
12.2.3 General periodicity modulo p
348(2)
12.2.4 Shortest period of the Fubini numbers
350(1)
12.3 The minimal polynomial
350(4)
12.3.1 The Berlekamp - Massey algorithm
351(3)
12.4 Periodicity with respect to composite moduli
354(2)
12.4.1 Chinese remainder theorem
354(1)
12.4.2 The Bell numbers modulo 10
355(1)
12.5 Value distributions modulo p
356(4)
12.5.1 The Bell numbers modulo p
356(4)
Exercises
360(1)
Outlook
361(2)
13 Diophantic results
363(18)
13.1 Value distribution in the Pascal triangle
363(5)
13.1.1 Lind's construction
363(3)
13.1.2 The number of occurrences of a positive integer
366(1)
13.1.3 Singmaster's conjecture
367(1)
13.2 Equal values in the Pascal triangle
368(1)
13.2.1 The history of the equation (n/k) = (m/l)
368(1)
13.2.2 The particular case (n/3) = (m/4)
368(1)
13.3 Value distribution in the Stirling triangles
369(3)
13.3.1 Stirling triangle of the second kind
369(2)
13.3.2 Stirling triangle of the first kind
371(1)
13.4 Equal values in the Stirling triangles and some related diophantine equations
372(6)
13.4.1 The Ramanujan-Nagell equation
372(1)
13.4.2 The diophantine equation {n/n-3} = {m/m-1}
373(1)
13.4.3 A diophantic equation involving factorials and triangular numbers
374(1)
13.4.4 The Klazar -Luca theorem
374(4)
Exercises
378(1)
Outlook
379(2)
Appendix 381(6)
Basic combinatorial notions
381(3)
The polynomial theorem
384(2)
The Lambert W function
386(1)
Formulas 387(18)
Tables 405(28)
Bibliography 433(40)
Index 473
Istvįn Mez is a Hungarian mathematician. He obtained his PhD in 2010 at the University of Debrecen. He was working in this institute until 2014. After two years of Prometeo Professorship at the Escuela Politécnica Nacional (Quito, Ecuador) between 2012 and 2014 he moved to Nanjing, China, where he is now a full-time research professor.