Stairstep Interpretation of Catalan Numbers

roam
Messages
1,265
Reaction score
12
How does one go about proving that C_n (Catalan number) is the number of ways to tile a stairstep shape of height n with n rectangles? :rolleyes:
 
Physics news on Phys.org
If you draw your staircase going up from left to right, then the rectangle in the lower right hand corner is special. For a particular staircase of height n+1, this rectangle separates the staircase into two smaller staircases of heights j and n-j. j ranges from 0 to n. This fact can help you set up a recurrence relation, the solution of which is the Catalan numbers.
 

Thread 'Here's a Statistics problem for game of Polo (or Hockey if you like)'

Namaste & G'day Postulate: A strongly-knit team wins on average over a less knit one Fundamentals: - Two teams face off with 4 players each - A polo team consists of players that each have assigned to them a measure of their ability (called a "Handicap" - 10 is highest, -2 lowest) I attempted to measure close-knitness of a team in terms of standard deviation (SD) of handicaps of the players. Failure: It turns out that, more often than, a team with a higher SD wins. In my language, that...
View full post »

Thread 'Roulette wheel physics and probability'

Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
View full post »

Similar threads

A Clarification of Mihăilescu's Theorem (Catalan's Conjecture)
Replies
1
Views
2K
I Logical representation of prime numbers
Replies
19
Views
4K
I How to start with proving ##a^a + b^b > a^b + b^a##?
Replies
3
Views
2K
I Help me understand skewness in QQ-plots please
Replies
1
Views
1K
I What are the properties of a plane cut into regions by a set of lines?
Replies
1
Views
1K
Relation between Catalan numbers
Replies
2
Views
3K
I Sampling theory and random sample
Replies
5
Views
2K
I May I use set theory to define the number of solutions of polynomials?
Replies
13
Views
2K
A Concrete examples of randomness in math vs. probability theory
Replies
11
Views
3K
MHB Can we prove that (m+1)/(n+1) > m/n if n>m>0 using synthetic proof?
Replies
9
Views
2K

Hot Threads

Recent Insights

Back
Top