PUMaC 2012 · 组合（A 组） · 第 2 题

PUMaC 2012 — Combinatorics (Division A) — Problem 2

[ 3 ] How many ways are there to arrange the 6 permutations of the tuple (1 , 2 , 3) in a sequence, such that each pair of adjacent permutations contains at least one entry in common? For example, a valid such sequence is given by (3 , 2 , 1 ) − ( 2 , 3 , 1) − (2 , 1 , 3 ) − ( 1 , 2 , 3) − (1 , 3 , 2 ) − (3 , 1 , 2) .

解析

We can do this by casework. Notice that there is exactly one fixed element between consecutive permutations, and there are exactly two permutations for each fixed digit as a fixed element. Without loss of generality, suppose the first permutation is given by (123) (six possibilities), and that the second permutation fixes the third element, and so must be (213) (three possibilities). Without loss of generality again, one may assume that the third permutation fixes the second element (between the first and second elements), and so must be (312) (two possibilities). For the fourth permutation, there are two distinct cases: either the first or third elements are fixed. • In the former case, one gets the permutation (213). The two permutations left are (231) and (321) and must occur in that order. • In the latter case, one gets the permutation (321). The two permutations left are (231) and (213) and must occur in that order. Hence, there are 6 × 3 × 2 × (1 + 1) = 72 possible orderings of these permutations. An equivalent restatement of the problem is to count the number of Hamiltonian paths of the complete bipartite graph K (each bipartition corresponding to a copy of A ≤ S ), which is 3 , 3 3 3 readily seen to be 6 × 3 × 2 × 2 = 72 . Problem contributed by Luke Paulsen.