Problem

Source: India Postal Coaching 2014 Set 6 Problem 4 & Putnam 1990 A6

Tags: Putnam, combinatorics unsolved, combinatorics



Show that the number of ordered pairs $(S,T)$ of subsets of $[n]$ satisfying $s>|T|$ for all $s\in S$ and $t>|S|$ for all $t\in T$ is equal to the Fibonacci number $F_{2n+2}$. Moderator says: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=296007#p296007 http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=515970&hilit=Putnam+1990