Problem

Source: Russian Regional Olympiad 2010 10.8

Tags: combinatorics, combinatorial geometry



Let's call it a staircase of height $n$, a figure consisting from all square cells $n\times n$ lying no higher diagonals (the figure shows a staircase of height $4$ ). In how many different ways can a staircase of height $n$ can be divided into several rectangles whose sides go along the grid lines, but the areas are different in pairs?