How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-recta

gvaldytist

gvaldytist

Answered question

2022-06-21

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be:
f(n) = 4f(n-1) - 2f(n-2)
where f(0) = 1
and f(1) = 1
but the recurrence relation only counts the cases in which at least one side (either top, bottom, left or right of the original rectangle) is not split into sub-rectangles.

Answer & Explanation

Zayden Wiley

Zayden Wiley

Beginner2022-06-22Added 21 answers

Would it overcome some of the difficulty by using some sort of graph representation of the subdivided rectangle? Each rectangle is a vertex and an edge represents sharing a side, i.e. the first rectangle above would be represented by the edges ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) and the second by ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 4 ) , ( 2 , 5 ) , ( 3 , 4 ) , ( 3 , 5 ) , numbering the rectangles from top-left to bottom-right. The tricky part here would then be to implement the operations for subdividing by a vertical or horizontal line segment. Starting instead with lines instead of segments could be promising.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?