Number of feasible airport networks
Source: SAMO 2011 Senior Round 3 Problem 4
September 7, 2011
functioncombinatorics unsolvedcombinatorics
Problem Statement
An airline company is planning to introduce a network of connections between the ten different airports of Sawubonia. The airports are ranked by priority from first to last (with no ties). We call such a network feasible if it satisfies the following conditions:
[*] All connections operate in both directions
[*] If there is a direct connection between two airports A and B, and C has higher priority than B, then there must also be a direct connection between A and C.Some of the airports may not be served, and even the empty network (no connections at all) is allowed. How many feasible networks are there?