## Basic Combinatorics.

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: , . We also use set constructor notation where is some statement about that can be true or false. For example: , . We write: , for the set of natural numbers, for the set of rational numbers, for the set of integers.

We write to mean that is in the set . We write . We write . We write for if . If then we say that and are disjoint sets.

We write for the set of ordered pairs of elements.

Definition 1A function isinjective (one to one)if: implies . A function issurjective (onto)if: for all there is such that . A function isbijectiveif: for all there is such that . The number of elements in a set is written .

** 1.2. Basic formulae **

The basic facts of combinatorics are very simple.

- If then there is no injective function from a set with elements to a set with elements. (This is called pigeon hole principle.)
- If there is a bijective function from to then .
- If and are disjoint then .
- If and are disjoint then .
- .
- The number of element subsets of a set with elements is: . (Why is this an integer? Prove it.)
- The number of functions from an -element set to a element set is .
- If then the number of bijective functions from to (permutations of ) is .

There are a couple formulae that are handy to remember:

- There are subset of .
- Suppose you have objects of types 1, 2, , respectively. The number of ways of arranging all the objects is:
- Suppose you have identical objects that you want to distribute among containers. The number of ways to do this is: . (Why?)

## Of Committees and Meetings

I’m happy to announce that I survived my PhD supervisory committee meeting. After 362 days, my committee met once again (we last met Apr 10th 2013), and things went well.

Below I’ve included some details on the process and some post-meeting thoughts. All of it is based purely on my own experience, but might be helpful to others.

## 2014 Mentoring

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.

## The Rotationally Distinct Ways to Label a Die

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.

## Questions about Discs

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.

## A Bijection

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

Exercise 1Show that is a bijective map .

## The Spherical Isoperimetric Inequality

Here is an application of the spherical isoperimetric inequality.

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

## Antipodal points after Vîlcu

I’ve been thinking a lot about convex bodies in 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 be a centrally symmetric convex body in . Let denote thes intrinsic metric of and its intrinsic diameter. For a point we write for its image under the central symmetry.

Lemma 1 (Vîlcu) If then .

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.

## Group Theory Problems

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 denote the symmetric group on elements. We say is *a point-fixing subgroup* if there is a such that for all . We say *has fixed points* if for each there is such that .

Exercise 1Is every that has fixed points a point-fixing subgroup?

## Polynomials

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

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

*Hint*: Look at and .

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

leave a comment