Wednesday, August 5, 2026

Combinatorics: For the National Undergraduate Mathematics Olympiad (Bangladesh) (Table of Contents)

 

Table of Contents

Part I: Combinatorics

For the National Undergraduate Mathematics Olympiad (Bangladesh)


Preface

  • About This Book

  • How to Use This Book

  • National Undergraduate Mathematics Olympiad (NUMO) Syllabus

  • Mathematical Notation

  • Common Proof Techniques

  • Problem-Solving Strategies in Olympiad Mathematics


Chapter 1: Foundations of Combinatorics

1.1 What is Combinatorics?

1.2 Counting Principles

1.3 Addition Principle

1.4 Multiplication Principle

1.5 Principle of Inclusion and Exclusion (Introduction)

1.6 Pigeonhole Principle

1.7 Double Counting

1.8 Mathematical Induction in Combinatorics

1.9 Invariants and Monovariants

1.10 Common Counting Mistakes

Problem Solving Methods

  • Direct Counting

  • Complementary Counting

  • Bijective Proofs

  • Recursive Counting

  • Counting by Cases

Worked Examples

Practice Problems

Challenge Problems


Chapter 2: Permutations

2.1 Definition

2.2 Factorials

2.3 Basic Permutations

2.4 Circular Permutations

2.5 Permutations with Repeated Objects

2.6 Restricted Permutations

2.7 Derangements

2.8 Inversions

2.9 Multiset Permutations

2.10 Lexicographic Ordering

2.11 Applications

Problem Solving Methods

  • Gap Method

  • Block Method

  • Inclusion-Exclusion

  • Complement Method

  • Symmetry Arguments

Worked Examples

Practice Problems

Olympiad Problems


Chapter 3: Combinations

3.1 Definition

3.2 Binomial Coefficients

3.3 Pascal's Identity

3.4 Binomial Theorem

3.5 Multinomial Coefficients

3.6 Combinations with Restrictions

3.7 Stars and Bars

3.8 Inclusion-Exclusion Principle

3.9 Catalan Numbers

3.10 Counting Lattice Paths

3.11 Applications

Problem Solving Methods

  • Case Analysis

  • Complementary Counting

  • Recursive Methods

  • Symmetry

  • Bijections

Worked Examples

Practice Problems

Olympiad Problems


Chapter 4: Prime Numbers

4.1 Fundamental Theorem of Arithmetic

4.2 Prime Factorization

4.3 Sieve of Eratosthenes

4.4 Distribution of Primes

4.5 Euclid's Theorem

4.6 Twin Primes

4.7 Mersenne Primes

4.8 Fermat Numbers

4.9 Wilson's Theorem

4.10 Fermat's Little Theorem

4.11 Euler's Theorem

4.12 Chinese Remainder Theorem (Introduction)

Problem Solving Methods

  • Prime Factorization

  • Divisibility Arguments

  • Contradiction

  • Modular Arithmetic

  • Bounding Techniques

Worked Examples

Practice Problems

Olympiad Problems


Chapter 5: Arithmetic Functions

5.1 Divisibility

5.2 Greatest Common Divisor

5.3 Least Common Multiple

5.4 Euclidean Algorithm

5.5 Bézout's Identity

5.6 Euler Phi Function

5.7 Divisor Function

5.8 Sum of Divisors Function

5.9 Möbius Function

5.10 Multiplicative Functions

5.11 Dirichlet Convolution (Introduction)

5.12 Applications

Problem Solving Methods

  • Prime Factorization

  • Function Identities

  • Multiplicativity

  • Recursive Evaluation

Worked Examples

Practice Problems

Olympiad Problems


Chapter 6: Congruence

6.1 Congruence Relations

6.2 Properties of Congruences

6.3 Linear Congruences

6.4 Systems of Congruences

6.5 Chinese Remainder Theorem

6.6 Modular Inverses

6.7 Modular Exponentiation

6.8 Fermat's Little Theorem

6.9 Euler's Theorem

6.10 Wilson's Theorem

6.11 Primitive Roots (Introduction)

6.12 Quadratic Residues (Introduction)

Problem Solving Methods

  • Modular Reduction

  • Periodicity

  • Residue Classes

  • Invariant Arguments

Worked Examples

Practice Problems

Olympiad Problems


Chapter 7: Recurrence Relations

7.1 Introduction

7.2 First-Order Recurrences

7.3 Linear Recurrence Relations

7.4 Homogeneous Recurrences

7.5 Non-Homogeneous Recurrences

7.6 Characteristic Equation Method

7.7 Fibonacci Numbers

7.8 Lucas Numbers

7.9 Divide-and-Conquer Recurrences

7.10 Matrix Method

7.11 Applications

Problem Solving Methods

  • Iteration

  • Characteristic Roots

  • Induction

  • Matrix Exponentiation

Worked Examples

Practice Problems

Olympiad Problems


Chapter 8: Generating Functions

8.1 Motivation

8.2 Ordinary Generating Functions

8.3 Algebra of Generating Functions

8.4 Solving Recurrences

8.5 Counting Problems

8.6 Integer Partitions

8.7 Exponential Generating Functions (Introduction)

8.8 Catalan Numbers via Generating Functions

8.9 Applications

Problem Solving Methods

  • Series Manipulation

  • Coefficient Extraction

  • Functional Equations

  • Recurrence Solving

Worked Examples

Practice Problems

Olympiad Problems


Chapter 9: Complexity

9.1 Algorithms and Complexity

9.2 Growth of Functions

9.3 Big-O Notation

9.4 Big-Theta and Big-Omega

9.5 Best, Average, and Worst Case

9.6 Recursive Algorithms

9.7 Time Complexity Analysis

9.8 Space Complexity

9.9 Divide-and-Conquer Algorithms

9.10 Dynamic Programming (Introduction)

9.11 Greedy Algorithms (Introduction)

9.12 Complexity in Counting Problems

Problem Solving Methods

  • Asymptotic Analysis

  • Recurrence Trees

  • Master Theorem (Overview)

  • Amortized Reasoning (Introduction)

Worked Examples

Practice Problems

Olympiad Problems


Chapter 10: Integrated Olympiad Problem Solving

10.1 Counting Techniques

10.2 Number-Theoretic Methods

10.3 Modular Arithmetic Techniques

10.4 Recurrence Techniques

10.5 Generating Function Techniques

10.6 Complexity-Based Problems

10.7 Mixed Combinatorics Problems

10.8 Proof-Based Olympiad Questions

10.9 Strategy for National Undergraduate Mathematics Olympiad

Fully Worked Olympiad Problems

Timed Practice Sets

Previous Olympiad Style Problems


Appendices

Appendix A: Mathematical Proof Techniques

Appendix B: Frequently Used Identities

Appendix C: Binomial Coefficient Identities

Appendix D: Modular Arithmetic Formulae

Appendix E: Prime Number Tables

Appendix F: Arithmetic Function Formulae

Appendix G: Common Recurrence Relations

Appendix H: Common Generating Functions

Appendix I: Asymptotic Growth Reference Table

Appendix J: Olympiad Problem-Solving Checklist


Answers to Selected Problems

Hints for Challenge Problems

Complete Solutions Manual

Bibliography

Index

This structure progresses from foundational counting principles to advanced undergraduate topics such as generating functions and computational complexity, while consistently integrating theory, problem-solving techniques, fully worked examples, and Olympiad-style exercises aligned with the National Undergraduate Mathematics Olympiad syllabus.

No comments:

Post a Comment

Chapter 8.1 (Part II)

  Chapter 8: Generating Functions 8.1 Motivation Part II: The Fundamental Idea Behind Generating Functions 8.1.11 A Sequence as a Mathematic...