5. Combinatorics

数学英语



周维祺

Combinatorics

The mathematics of counting

Permutation

Rearrangement of an ordered tuple

Example: cyclic permutation

Factorial

Combination

Selection of objects from a set in which the order does not matter

Binomial Coefficients

Repetitions, Distinctness, Uniqueness

  • a sequence where repetitions are allowed:

  • a sequence in which all entries are distinct:

  • in both sequences there is a unique entry that is prime

Sets

  • set: a collection of objects
  • elements: members in sets
  • the empty set:
  • subset:
  • proper subset:
  • power set: the collection of all subsets of a given set

Enumeration

To enumerate is to make a complete list of objects one by one

Finite and Infinite

  • finite set:

  • infinite set:

Countable and Uncountable

  • countable set: a set whose elements can be enumerated
    e.g.,

  • uncountable set: a set whose elements can not be exhausted by enumeration, e.g.,

Set Operations

  • union:
  • intersection:
  • complement:
  • differrence:
  • symmetric difference:
  • (direct) product:

Partitions

a partition of a set is a way of writing it into
non-overlapping unions of its subsets

Equivalence Relations

  • a relation betwen is a subset of

  • an equivalence relation is a relation that is
    reflexive:
    symmetric:
    transitive:

  • an equivalence relation induces a partition on a set

The Pigeonhole Principle

if we put items into drawers, then at least one drawer contains more than one item

Game

  • this is a game of voting, initially every of us has a salary of 1

  • as the teacher I have the right to propose for a new distribution plan

Game

  • every one of you can vote, you will vote for the plan if it increases your salary, against it if it decreases your salary, and forfeit the vote if there is no change
  • the new plan will take effect if there are more people voted for it than against it

Game

  • the salary (of any person, in all plans) must be a non-negative integer

  • the total salary shall not exceed the inital total amount (i.e., total number of persons)

Game

  • I can not vote but I can keep proposing new plans until no further progress can be made

  • so what is the maximal salary I can get?

Recurrences

recursively defined terms with given initial values

Periodicity

A fuction is periodic if there exists some such that

holds for all , is then a period of

Generating Function

A formal power series with coefficients produced by some sequence

Example: Fix , let , then its generating function is

Ordering

  • (Partial) Order: A reflexive, antisymmetric, transitive relation
    e.g.,

  • Lexicographic order: the order as per the dictionary

Asymptotics

The growth of as , e.g.,

Mathematical Inductions

  • suppose that holds for

  • assume that holds for all with

  • show that holds for

Tasks

  • write a proof for the statement that the set of all infinite binary sequence is uncountable

  • formulate it in academic style with definitions, lemmata, and theorems.

  • you may refer to this source for the Cantor's Diagonal Argument

Summary

  • Permutations and Combinations

  • Sets and Relations

  • The Pigeonhole Principle

  • Induction