MathCastle
Graph TheoryChallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Challenge problem

Six people 1,2,…,61,2,\dots,6 stand in a line. A "pairing" selects some number of disjoint pairs of ADJACENT people (people next to each other in the line) to shake hands, possibly none at all. In how many different ways can this be done?