# Harrison Chapman

## Math 301: Counting problems and the pigeonhole principle

Class date: Friday, September 13, 2019
1. How many different strings can you make by rearranging the letters of MATHEMATICS? For example, one is THEMMAASTIC.

There are 11 letters in MATHEMATICS. So, if all letters were distinct, there would be $$11!$$ words we could make. But, there are two M’s, T’s, and A’s that are each indistinguishable. Each of those three letters can appear in any of $$2!$$ ways each. So, the answer is; $\frac{11!}{(2!)^3}.$

2. On an $$n \times n$$ grid, how many paths connect the lower-left corner to the upper-right corner, if only unit-length up steps and unit-length right steps are allowed? Here are examples for sizes $$n = 1,2,3$$:

Since we can only walk up or right, notice that every path must consist of $$2n$$ steps. Furthermore, we can only make it to the top right corner if we take the same number of up-steps as right-steps (that is, $$n$$ of them). So, the answer is $\binom {2n}n.$
If we make buckets be the mutually exclusive sets $$\{x \in \mathbb R : 10(k-1) < x \le 10k\}$$ for $$k \in \mathbb N, 1 \le k \le 10$$, we have partitioned the numbers $$(0,100]$$ into 10 mutually exclusive buckets. Notice that if we take any two numbers $$x,y$$ where $$x > y$$ in the same bucket, their difference is $$x-y < 10k - 10(k-1) = 10.$$