|
Pascal
Triangle of the Second Kind and Catalan Numbers
Below is the Pascal Triangle of the second kind
representation. It is very interesting triangle's form of
numbers.The odd numbers , square numbers and pyramidal numbers can be found as columns
in Pascal's triangle of the second kind :
2
1
2
1 3
2
1 4 5 2
1 5 9 7 2
1 6 14 16 9 2
1 7 20 30
25 11
2
1 8 27 50 55 36 13 2
1 9 35 77
105 91 49
15 2
It can clearly be seen
that any number within the triangle is the sum of the two numbers
immediately above it. This is the basis for constructing the
triangle, as shown below.
The Catalan numbers are an integer
sequence which appears in tree enumeration problems of the type, "In
how many ways can a regular n-gon be divided into triangles
if different orientations are counted separately?" (Euler's polygon
division problem).
| Number of sides |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| Number of way to partition it into triangles |
1 |
2 |
5 |
14 |
42 |
132 |
429 |
The first few Catalan
numbers for n = 1, 2, ... are 1, 2, 5, 14, 42, 132, 429,
1430, 4862, 16796, ... (Sloane's A000108).
There are at least two ways they can be found in
Pascal's triangle, one in the middle column going down the center,
subtracting the element immediately adjacent (see numbers in red),
| 1 |
3 |
9 |
30 |
105 |
378 |
............ |
| - |
2 |
7 |
25 |
91 |
336 |
............ |
| 1 |
1 |
2 |
5 |
14 |
42 |
............ |
and another one row above, taking the Nth term over
and subtracting the term to the right (numbers in blue).
| 2 |
5 |
16 |
55 |
196 |
............ |
| - |
|
2 |
13 |
64 |
............ |
| 2 |
5 |
14 |
42 |
132 |
........... |
See the next examples:
| 1 |
3 |
9 |
30 |
105 |
372 |
............ |
| - |
1 |
5 |
20 |
77 |
294 |
............ |
| 2 |
2 |
4 |
10 |
28 |
84 |
............ |
We have
2,2,4,10,28,84,... = 2* (1,1,2,5,14,42, ...
)
See the next example:
|
1 = 1
1 = 3-2
2 = 9-5-2
5 =
30-16-7-2
14=105-55-25-9-2
|
Or:
|
2* 1 = 2
2* 1 = 3-1
2* 2 = 9-4-1
2* 5 =
30-14-5-1
2*14=105-50-20-6-1
|
Here are the next examples:
| |
2 |
5 |
16 |
55 |
196 |
............ |
| - |
1 |
4 |
14 |
50 |
182 |
............ |
| |
1 |
1 |
2 |
5 |
14 |
............ |
| |
2 |
7 |
25 |
91 |
236 |
............ |
| - |
1 |
5 |
20 |
77 |
294 |
............ |
| |
1 |
2 |
5 |
14 |
42 |
............ |
|
