Let , and consider the 2-configuration consisting of for all for all , and for all . Find the number of subsets of that are consistent of order 1.
Solution
Let for , and consider the 2-configuration consisting of for all for all , and for all . Let be the number of subsets of that are consistent of order 1 (call these "matchings" of ). Consider any matching of . Either is paired with , in which case the remaining elements of our matching form a matching of ; or is paired with , in which case must be paired with , and the remaining elements form a matching of . It follows that . By direct calculation, and , and now computing successive values of using the recurrence yields .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.