Classic Counting Problems

Question

Does anyone have some good, classic, counting problems? I want things that are interesting, as well as instructive- more than just compute the number of way to get a flush, etc. (Not that those aren't interesting, but students seem to get bored of that quickly.)

Answer 1

For a while I enjoyed passing the time in meetings by counting the number of permutations in each cycle class.

Take $n=4$. There are 5 classes of permutations:

1. 
2. 
3. 
4. 
5. 

There are respectively 1, 6, 3, 8, and 6 permutations of these types. One nice thing about this problem is that it has a built-in check: $1+6+3+8+6=24=4!$; if the counts didn't add to 24 we'd know we must have made a mistake.

Then you can generalize to arbitrary $n$.

Once you have the counts, you can answer possibly interesting questions: Pick a random permutation. What is the most likely number of fixed points? What is the expected number of fixed points? What is the expected number of cycles?

The number of permutations of $n$ things with $k$ cycles is the Stirling number of the first kind, and by counting the permutations in two ways you obtain the interesting identity $$\sum\left[{n\atop i}\right]i = H_n\cdot n!$$where $H_n$ is the $n$th harmonic number.

Answer 2

The number of ways to climb $n$ stairs in jumps of $1$ step and $2$ steps is quite nice, turns out the answer is the $n$th Fibonacci number.

Another really nice counting problem is the number of standard tableau of shape $\lambda$, there is a beautiful formula for this known as the hook formula.

Answer 3

The number of ways $n$ items can be ordered if ties are permitted: $1,3,13,75,\dots$, OEIS sequence A000670.

Answer 4

One way to improve the poker hand counting problem to a more interesting version is:

For a time in the 19th century there was a vogue for 65-card decks with five suits of 13 cards each. Calculate the proper ranking of poker hands when playing with such a deck.

In particular, does a full house still beat a flush?

Or similarly:

On the planet Pyrzxqgl, the inhabitants play poker with a standard 52-card deck, but the hands have 6 cards each. Calculate the proper ranking of poker hands on the planet Pyrzxqgl. Don't forget to include a ranking for three pairs!

Or have them invent a new poker hand (with the standard deck) such as:

• a four-card straight plus a pair (for example, 4 5 5 6 7)
• all cards the same color (for example, 3♠ 9♠ J♠ and 7♣ Q♣)
• a pair, with the three odd cards all the same suit (for example, 2♡ 2♣ 5♠ 6♠ Q♠)
• no card higher than a 7
• five face cards (this is semi-standard; it is called a blaze).

and have them rank their new hand relative to the standard hands.

Or turn the problem around: The odds off getting a full house are much better than the odds of getting the next higher-ranked hand, four of a kind. Invent a poker hand that should rank as in between the two, as near to the middle as possible. (Bonus question: what does "near to the middle" mean here?)

Answer 5

The number of domino tilings of a $2 \times n$ rectangle is counted by Fibonacci numbers. This can be rather easily seen by showing they satisfy the same recursion.

The number of Dyck paths (and many related objects) are counted by the Catalan numbers. Again this can seen, with a little more work than the previous example, that they satisfy the same recursion.

Also if one has the notation of graphs there are a classic questions. For example how many graphs (or digraph) on $n$ vertices? Or how many edges does the complete graph on $n$ vertices have? And many other similar examples.

Also the are classics from "the twelvefold way". How many functions? How many onto functions? And other variations, i.e. all you bins and balls type problems.

Answer 6

How many triples of positive integers have sum 20 and product a multiple of 5?

Answer 7

Of the positive integers less than 10,000, how many have digits that add to 12?