Let us imagine making a big list of all of the ways to choose two different birthdays for two pairs of people. The list looks something like this:
- Alice, Bob on Jan 1; Charlie, Diane on Jan 2.
- Alice, Bob on Jan 1; Charlie, Evan on Jan 2.
- Alice, Bob on Jan 1; Diane, Evan on Jan 2.
Etc.
Now, there are several equivalent ways to write each of these entries. For example, the entry "Alice, Bob on Jan 1; Charlie, Diane on Jan 2" is equivalent to "Charlie, Diane on Jan 2; Alice, Bob on Jan 1". We want to ensure that there are no repeats in the list. One way to do that is to impose the following rule;
- Always list the date which comes earlier in the year first.
In addition to switching the dates, you can also switch the order of the two people born on each of the same days. That is, "Alice, Bob on Jan 1; Charlie, Diane on Jan 2" is the same as "Bob, Alice on Jan 1; Charlie, Diane on Jan 2", which in turns is the same as "Bob, Charlie on Jan 1; Diane, Charlie on Jan 2". To ensure multiple equivalent entries do not appear, we impose a second rule:
- For each pair of people born on the same day, list them in alphabetical order.
Now, let us count the number of ways to choose an expression of the form
$$
\text{Person 1, Person 2 on Day 1;$\quad$ Person 3, Person 4 on Day 2}
$$
subject to these two rules.
There are $365$ choices for Day 1, and $364$ choices for Day 2. However, exactly half of the the $365\times 364$ choices will violate our rule, because they put the later day first. When you throw out the illegal choices, there are only $(365\cdot 364)/2=\binom{365}2$ ways remaining.
There are $n$ choices for Person 1, then $n-1$ choices for Person 2. However, half of these violate the alphabetical rule, so the number of legal choices is only $n(n-1)/2=\binom n2$.
There are $n-2$ choices for Person 1, then $n-3$ choices for Person 2. However, half of these violate the alphabetical rule, so the number of legal choices is only $(n-2)(n-3)/2=\binom {n-2}2$.
How does this connect with the denominator? Well, the denominator describes the entire situation, so the denominator describes all of the ways to assign birthdays to the $n$ people. That is, something in the denominator would be a list of $n$ items like
Alice was born on May 12,
Bob was born on June 19,
Charlie was born on December 28,
$\vdots$
Nancy was born on March 05.
To make this unique, we impose the rule that the names are always listed in alphabetical order. Since there are $365$ choices for each birthday, the number of ways to choose the list is $365^n$, as expected. Obviously, here, order matters, because switching the order of the dates changes who gets which birthday.
How does the work in the numerator help determine this big list? Say that the choice for the numerator was "Paul, John born on Mar 2; George, Ringo on Nov 30". This means that you would go to the "Paul" row on the big list, and fill in the birthday Mar 2. Then, you go to the "John" row, and fill in the birthday Mar 2. Finally, you go to the "George" and "Ringo" rows and fill in the birthday Nov 30 for both. At this point, four rows have been filled, leaving $n-4$ rows remaining. These remaining rows can be filled with distinct birthdays, none of which are Mar 2 or Nov 30, in $(363)!/(363-(n-4))!$ ways, which is the rest of the numerator.
Summary: Combinatorics problems do not just boil down to the question of "Does order matter?". In the $\binom{365}2\binom n2\binom {n-2}2$, there is some division in the denominator, suggesting that order does not matter. However, even so, the information contained in $\binom{365}2\binom n2\binom{n-2}2$ was enough to specify the positions of four birthdays in the big list, where order does matter.
The takeaway message is this: combinatorics problems cannot just be put into two boxes, of problems where "order matters" and "order does not matter". You can have mixes between the two. Instead, you must carefully think about how to apply these two concepts to each problem. For every problem, you should first think about how to uniquely represent each item being counted, and then think about which counting paradigms are best to describe it.
