18 1. Let’s Count!
second?abc acb bac bca cab cbabacabca b cfirst?second? second?FIGURE 1.3. A decision tree for selecting a permutation of{a, b, c}.possible answers to the question. Making a decision, we can follow one of
the arrows down to the next node. This carries the next decision problem:
whom do we put in the second chair? The two arrows out of the node
represent the two possible choices. (Note that these choices are different
for different nodes on this level; what is important is that there are two
arrows going out from each node.) If we make a decision and follow the
corresponding arrow to the next node, we know who sits in the third chair.
The node carries the whole seating order.
It is clear that for a set withnelements,narrows leave the top node,
and hence there arennodes on the next level. Thenn−1 arrows leave
each of these, hence there aren(n−1) nodes on the third level. Thenn− 2
arrows leave each of these, etc. The bottom level hasn! nodes. This shows
that there are exactlyn! permutations.
1.6.1nboys andngirls go out to dance. In how many ways can they all dance
simultaneously? (We assume that only couples of mixed gender dance with each
other.)
1.6.2 (a) In how many ways can 8 people play chess in Alice’s interpretation
of the question?
(b) Can you give a general formula for 2npeople?