## Basic Combinatorics.

Posted in Uncategorized by pgadey on 2014/07/27

First we recall a little bit of terminology:

1.1. Sets and functions

A set is a collection of elements . We write a set by surrounding its list elements with curly braces. For example: ${X = \{1,2,3\}}$, ${Y = \{\heartsuit, \clubsuit, \star\}}$. We also use set constructor notation ${Y = \{x : P(x)\}}$ where ${P(x)}$ is some statement about ${x}$ that can be true or false. For example: ${X = \{n : n\text{ is even}\}}$, ${Z = \{n : n\text{ is prime}\}}$. We write: ${\{\} = \emptyset}$, ${{\mathbb N}}$ for the set of natural numbers, ${{\mathbb Q}}$ for the set of rational numbers, ${{\mathbb Z}}$ for the set of integers.

We write ${x \in X}$ to mean that ${x}$ is in the set ${X}$. We write ${X \cup Y = \{x : x \in X \text{ or } x \in Y\}}$. We write ${X \cap Y = \{x : x \in X \text{ and } x \in Y\}}$. We write ${X \sqcup Y}$ for ${X \cup Y}$ if ${X \cap Y = \emptyset}$. If ${X \cap Y = \emptyset}$ then we say that ${X}$ and ${Y}$ are disjoint sets.

We write ${X \times Y = \{(x,y) : x \in X,\ y \in Y\}}$ for the set of ordered pairs of elements.

Definition 1 A function ${f : X \rightarrow Y}$ is injective (one to one) if: ${x \neq y}$ implies ${f(x) \neq f(y)}$. A function is surjective (onto) if: for all ${y \in Y}$ there is ${x \in X}$ such that ${f(x) = y}$. A function is bijective if: for all ${y \in Y}$ there is ${x \in X}$ such that ${f(x) = y}$. The number of elements in a set ${X}$ is written ${|X|}$.

1.2. Basic formulae

The basic facts of combinatorics are very simple.

1. If ${k < n}$ then there is no injective function from a set with ${n}$ elements to a set with ${k}$ elements. (This is called pigeon hole principle.)
2. If there is a bijective function from ${X}$ to ${Y}$ then ${|X| = |Y|}$.
3. If ${X}$ and ${Y}$ are disjoint then ${|X \cup Y| = |X| + |Y| - |X \cap Y|}$.
4. If ${X}$ and ${Y}$ are disjoint then ${|X \sqcup Y| = |X| + |Y|}$.
5. ${|X \times Y| = |X| \cdot |Y|}$.
6. The number of ${k}$ element subsets of a set with ${n}$ elements is: ${\binom{n}{k} = \frac{ n! }{ (n-k)! k! }}$. (Why is this an integer? Prove it.)
7. The number of functions from an ${n}$-element set to a ${k}$ element set is ${k^n}$.
8. If ${|X| = n}$ then the number of bijective functions from ${X}$ to ${X}$ (permutations of ${X}$) is ${n!}$.

There are a couple formulae that are handy to remember:

1. There are ${2^n}$ subset of ${\{1, \dots, n\}}$.
2. Suppose you have ${n_1, \dots, n_k}$ objects of types 1, 2, ${\dots}$, ${k}$ respectively. The number of ways of arranging all the objects is: ${{ (n_1 + \dots + n_k)! }/{ n_1! n_2! \dots n_k! }}$
3. Suppose you have ${n}$ identical objects that you want to distribute among ${k}$ containers. The number of ways to do this is: ${\binom{n+k-1}{k-1}}$. (Why?)

Tagged with: , , ,

## 2014 Mentoring

Posted in Math by pgadey on 2014/02/08

I’ve added a page about the mentoring project that I’m working on with three Gr. 12 students this semester. I’ll be updating the page as we go. For more information see Mentoring — 2014. From the introductory remarks:

The plan for the semester is an ambitious one. We’re going to understand the structure of all the regular convex polytopes in all dimensions, and build up a intuition for dimensions greater than three. We’ll spend most of our time learning the tools we need to understand how a geometric object can be pieced together. These tools will include vectors, metric spaces, symmetry groups, and simplicial complexes. I’m taking a very broad view of what constitutes a tool and counts as information about a space. The final result of the project will be a poster presentation about the solids and some 3-dimensional “nets” of the 4-dimemsional solids (the simplex, cube, cross-polytope, and 24-cell).

I can’t resist saying things about hyperbolic geometry. Therefore, if we get to the end of the proposed project, we’ll take a stab at using out high brow high dimensional intuition to understand the Gieseking manifold. There is more than enough stuff to say about the platonic solids, so we’ll see how far we get.

Tagged with: , , ,

Posted in Math by pgadey on 2013/07/20

Over the past couple weeks I’ve been asked a lot of questions about discs in Euclidean space. In this post we’ll be putting pennies on a table, refining covers of discs, and trying to cram lots of balls into high dimensional balls. Some open questions about putting pennies on tables occur below.

Tagged with: , , ,

## A Bijection

Posted in Math by pgadey on 2013/03/30

While grading an assignment on cardinality, I ran into the answer to the following problem:

Exercise 1 Show that ${f(n) = \sum_{k=0}^n (-1)^{k+1} k}$ is a bijective map ${{\mathbb N} \cup \{0\} \rightarrow {\mathbb Z}}$.

Tagged with: , ,

## Group Theory Problems

Posted in Math by pgadey on 2013/03/26

Mike Pawliuk and I got talking about elementary group theory problems today. I wanted to record one of my favourites. I heard this one from Lucy Kadets, who heard it from Yuri Burda. I’m not sure if he is the original author or not.

Let ${S_n}$ denote the symmetric group on ${n}$ elements. We say ${H \leq S_n}$ is a point-fixing subgroup if there is a ${1 \leq k \leq n}$ such that ${h(k) = k}$ for all ${h \in H}$. We say ${H}$ has fixed points if for each ${h \in H}$ there is ${1 \leq k_h \leq n}$ such that ${h(k_h) = k_h}$.

Exercise 1 Is every ${H \leq S_n}$ that has fixed points a point-fixing subgroup?

Tagged with: , ,

## Polynomials

Posted in Math by pgadey on 2013/03/01

Brandon Hanson told me the following elementary number theory problems last night.

Exercise 1 Every non-constant polynomial takes on a composite value.

Hint: Look at ${f(x) = p}$ and ${f(kp + x)}$.

Exercise 2 If a non-constant polynomial takes on infinitely many prime values then it is irreducible.

## Induction for Fields Circle

Posted in Math by pgadey on 2013/03/01

Below the cut are some induction related questions I collected together for a Math Circle at the Fields Institute.

Tagged with: ,

## An Original Colouring Puzzle

Posted in Uncategorized by pgadey on 2013/03/01

Is it possible to colour the naturals greater than one using two colours, red and blue, such that: the product of two red numbers is blue, and the product of two blue numbers is red?

Tagged with:

## The Pigeon Hole Principle

Posted in Uncategorized by pgadey on 2012/11/17

Below the cut are some pigeon hole related questions I collected together for a Math Circle at the Fields Institute.

Tagged with: , , ,

## BPM 1.4.2 (Sp 84)

Posted in Math by pgadey on 2011/03/10

Let $f(x) = x \log(1 + 1/x)$ for $0 < x < \infty$. We show that $f$ is monotonically increasing. First we rewrite $f(x) = x \log \left( \frac{x + 1}{x} \right) = x [ \log(x+1) - \log(x)]$. Taking derivatives, and doing some algebra, we get $f'(x) = [\log(x + 1) - \log(x)] - 1/(x+1)$. We wish to show that $0 < f'(x)$ everywhere. This would follow from $1/(x+1) < \log(x + 1) - \log(x)$. However, this follows from the convexity of $\log(x)$. Which says that $1/(x + \epsilon) < [\log(x + \epsilon) - \log(x)] / \epsilon$ for all $0 < x, \epsilon$.

We compute $\lim_{x \rightarrow 0} f(x)$. Taking $x_n = 1/(e^n - 1)$ we see that $f(x_n) = 1/(e^n - 1) \log(e^n) = n/(e^n - 1)$. We then have that $f(x_n) \rightarrow 0$. Since $f$ is monotonically increasing, and positive, we have that $\lim f(x) = 0$ as $x \rightarrow 0$. We compute $\lim_{x \rightarrow \infty} f(x)$. Applying concavity, we have $f(e^n) = e^n \log(1 + e^{-n}) \geq e^n \epsilon e^{-n} = \epsilon$ for all $0 < \epsilon < 1$. We then check that $f(x) = x \log(1 + 1/x) \stackrel{\star}{\leq} x (1/x) \leq 1$, where $\star$ is by applying $\log(1 + y) \leq y$. It follows that $\lim_{x \rightarrow \infty} f(x) = 1$.

Tagged with: , , ,