Parker Glynn-Adey

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: , , ,

Dodecahedral Crafts

Posted in Math by pgadey on 2014/03/02

Math Crafts

This evening I made some dodecahredral crafts to show my mentoring students. This week we’re proving that the dodecahderon actually exists, by constructing it explicitly. The model on the right illustrates our proof splendidly. For instructions, check out Laszlo Bardos’ site CutOutFoldUp.com. The dodecahedral calendar is from Marlies’ Crafts.

Tagged with: ,

Singularities I.1

Posted in Math by pgadey on 2013/12/04

These are some notes that I’m writing up on Gromov’s papers on singularities of maps. This first post will look at some of the introductory material in: Singularities, Expanders and Topology of Maps. Pt 1. These notes will be a partial introduction to what is going on.

(more…)

Tagged with: , ,

Of Waists and Spheres

Posted in Math by pgadey on 2013/11/19

These are some notes that I’m writing up on Gromov‘s waist inequality. We’ll look at some standard material about the Borsuk-Ulam theorem and finish with a nice application of the inequality.

(more…)

Of Loewner and Besicovitch

Posted in Math by pgadey on 2013/11/05

I’d like to share some of the notes that I’m writing up about systoles. After a little bit of preliminaries we’ll see a slick proof the systolic inequality in the torus case.

The systole of manifold is the length of the shortest non-contractible curve in the manifold. Systoles hard to estimate. In general there are many many non-contractible curves, and its not easy to track down which one should be smallest. If someone hands you a donut, you’ll visually guess the systole correctly. If someone hands you a coffee cup, it’s still clear. Once you get a generic metric, you’re in deep water. Loewner‘s theorem gives us an upper bound on the systole a Riemannian 2-torus (generalized donut / coffee cup case).

(more…)

Tagged with: ,

The Rotationally Distinct Ways to Label a Die

Posted in Math by pgadey on 2013/07/24

I’m giving a talk at the Canadian Math Camp this year. I’ll be showing the kids of how to count the number of ways to label a six sided die up to the rotational symmetries of the cube. Here is the handout for the talk with questions about dice labellings, the 15-puzzle, and permutation groups.

For the curious the labellings are below the cut. Please note that there are typos in the table below. Alex Fink kindly pointed them out and they will be fixed eventually. For now they are an exercise in keen observation.

(more…)

Tagged with: , ,

Questions about Discs

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.

(more…)

Tagged with: , , ,

The Spherical Isoperimetric Inequality

Posted in Math by pgadey on 2013/03/28

Here is an application of the spherical isoperimetric inequality.

Fact You can’t cut up a beach ball into equal parts with a path that is too short.

(more…)

Tagged with: , , ,

Antipodal points after Vîlcu

Posted in Math by pgadey on 2013/03/26

I’ve been thinking a lot about convex bodies in {{\mathbb R}^3} lately. This post is going to be a write up of a useful lemma in the paper: Vîlcu, Constin, On Two Conjectures of Steinhaus, Geom. Dedicata 79 (2000), 267-275.

Let {S} be a centrally symmetric convex body in {{\mathbb R}^3}. Let {d(x,y)} denote thes intrinsic metric of {S} and {D = \sup_{x,y} d(x,y)} its intrinsic diameter. For a point {x \in S} we write {\bar{x}} for its image under the central symmetry.

Lemma 1 (Vîlcu) If {d(x,y) = D} then {y = \bar{x}}.

This lemma says that if a pair realizes the inner diameter of a centrally symmetric convex body, the pair has to be centrally symmetric. This aligns well with our intuition about the sphere and cube, for example.

(more…)

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.

(more…)

Tagged with: , , ,