Problems
Is it possible to construct a 485 × 6 table with the integers from 1 to 2910 such that the sum of the 6 numbers in each row is constant, and the sum of the 485 numbers in each column is also constant?
Let \(p\) be a prime number greater than \(3\). Prove that \(p^2-1\) is divisible by \(12\).
How many ways can the numbers \(1,1,1,1,1,2,3,\dots,9\) be listed in such a way that none of the \(1\)’s are adjacent? The number 1 appears five times and each of \(2\) to \(9\) appear exactly once.
John’s local grocery store sells 7 kinds of vegetable, 7 kinds of meat, 7 kinds of grains and 7 kinds of cheese. John would like to plan the entire week’s dinners so that exactly one ingredient of each type is used per meal and no ingredients repeat during the week. How many ways can John plan the dinners?
Suppose there is an \(7 \times 7\) grid. We would like to travel from the bottom left corner to the top right corner in exactly 14 steps. A step is from one point on the grid to another point via a segment of length 1. How many paths are there? The picture below shows one possible path on the grid.
In an office, at various times during the day, the boss gives the secretary a letter to type, each time putting the letter on top of the pile of the secretary’s in-box. When there is time, the secretary takes the top letter off the pile and types it. There are nine letters to be typed during the day, and the boss delivers them in the order \(1,2,3,4,5,6,7,8,9\). While leaving for lunch, the secretary tells a colleague that letter 8 has already been typed, but says nothing else about the morning’s typing. The colleague wonders which of the nine letters remain to be typed after lunch and in what order they will be typed. Base upon the above information, how many such after-lunch orders are possible? (That there are no letters left to be typed is one of the possibilities.)
In this sheet, we will look at basic counting problems. The fundamental principle is quite simple. If you have two independent choices to make, then the number of options for making both choices is calculated by multiplying the number of options for each choice.
An issue we frequently run into is that of overcounting. This means we count the same thing more than once. In the examples and problems today, you will see various ideas that we can use to correct for overcounting, or for avoiding it.
A library keeps track of its books by a code with two (not necessarily different) letters taken from A to Z, followed by a three digit number from 000 to 999. What is the maximum number of books one can keep in the library and still tell them apart by looking at their codes?
From the examples above, we see that we often need to pick \(k\) objects from \(n\) objects where the order of the \(k\) objects is ignored. The number of ways to pick them is notated with the special symbol \(\binom{n}{k}\), pronounced “\(n\) choose \(k\)". Following a similar line of reasoning as the examples, we can write down a general formula:
\[\binom{n}{k} = \frac{n\times (n-1) \times \dots (n-k+1)}{k\times (k-1) \times \dots 1} = \frac{n!}{k!(n-k)!}.\]
\(n!\) is a shorthand for \(n\times (n-1)\times \dots \times 1\), pronounced “\(n\) factorial". This is another useful expression and allows us to write down many formulas succinctly.