CATALAN AND RELATED SEQUENCES ARISING FROM INVERSES OF PASCAL'S TRIANGLE MATRICES V. E. HOGGATT, JR., and MAFBJORIE BICKNELL San Jose State University, San Jose, California 95192
Here is recorded a fascinating sequence of sequences which arise in the first column of matrix inverses of matrices containing certain columns of Pascal's triangle. The convolution arrays of these sequences are computed, leading to determinant relationships, a general formula for any element in the convolution array for any of these sequences, and a class of combinatorial identities. The sequence S1 = \ 1, 1, 2, 5, 14, 42, — j is the sequence of Catalan numbers [ 1 ] , and the sequence S2 = \ 1, 1, 3, 12, 55, — 
appeared in an enumeration problem given by Carlitz [2, p. 125].
1. SEQUENCES ARISING FROM INVERSES OF PASCAL'S TRIANGLE MATRICES We form a series of n x n matrices/7/, /'= 0, 1, 2, 3, ••, by placing every (i + 1)st column of Pascal's triangle on and below the main diagonal, and zeroes elsewhere. Then, PQ contains Pascal's triangle itself, while Pj contains every other column of Pascal's triangle and P2 every third column. We call the inverse of P; the matrix Pr1 and record the convolution arrays for the sequences S; which arise as the absolute values of the elements in the first column of Pj in the tables which follow. Table 1.1 NonZero Elements of the Matrices/ 7 / 1 and/*, Pi
1 3 6 10
i = 2
2 5 14
1 3 9 28
1 5 20
1 1 3 12 55
1 4 18 38
1 7 42
1 1 4 22 140
1 5 30 200
1 9 72
1 4 10
5
3 6 10
1
1 4 10
1 7
1 3 6 10
1 5 15
1 10
1
4 10 20
1 7 28
1 10
1
1 5 15 35
1 9 45
1 13
1 13
395
396
CATALAN AND RELATED SEQUENCES ARISING
[DEC.
Next, we will compute the convolution arrays for the sequences S, which are tabulated below as well as establish the form of the nth term. Table 1.2 The SequencesStArising from Matrices T^"1 nth term
1
Si
0
1 1, I 1, I 
1
1, 7, 2t 5, 14, 
2
7, 7, 3, 12, 55, •
3
1, 1, 4, 22, 140,
4
1, 1, 5, 35, 285,
k
1,1,k+1,~
— (2n) n+ 1 \ n )
h(3;) 4 JH hi ;) 2n
4n
h{5:)
JL
l(k+Dn\
=L((k+1)n\
It is important to note that convolutions of the sequences S, arisingfrom PJ1 have as their ith convolution that same sequence, less its first element. Let S,(x) be the generating function for the sequence S,, and let * denote a convolution. We easily calculate: / = 1:
(1, 1, 2, 5, 14, >)*(1, I 2, 5, 14, •••) = 11, 2, 5, 14, j
(1.1)
xS\(x) i = 2:
(1, 1, 3, 12, 55, )*(1,
i = 3:
(1, 1, 4, 22, )*(1,
(1.2)
= Sjx)
1, 3, 12, 55, )*(1, xS\M
(1.3)
1
= S2(x)
1, 4, 22, )*(1,
1, 3, 12, 55,  ) = (1, 3, 12, 55,
)
1
1, 4, 22, )*(1,
xS%(x) = SJxJ
1, 4, 22, )
= (1, 4, 22,
)
1.
In fact, it will be shown by the Lemma [3] following, that xSJ+1 = Sj(x)
(1.4)
1,
which will allow an easy construction of the convolution array for S,. Two infinite matrices (denoted by giving successive column generators),
Lemma: m
(f (x),xfm+k(x),x2fm+2k(x),
..J
and
(Am(x),xAm+k(x),x2Am+2k(x),
~)
are inverses if A(x)f(xAk(x))
= 7.
Here, we take f(x) = 1/(1  x), the generating function for the first column of the Pascal matrix, and \s\A(x) = 3,(x), where S;(x) is the generating function for the sequence S,, and take k = i + 7. Then 7 = A(x)f(xAk(x))
Si{x)[1xS?1(x)]1.
=
or 1xSJ+1(x)
=
Sj(x)
which establishes (1.4) upon replacing (x) b y x and rearranging terms. Also notice that, in a convolution triangle, the generating function for the / f column is the / power of the generating function forthefirstcolumn. Putting this together with (1.4) gives us a neat way to generate the convolution triangle for any one of the sequences S,. For example, for / = 7,
1976]
FROM INVERSES OF PASCAL'S TRIANGLE MATRICES
xtffx) (1.5)
xS
k+1
(x)
S7(x)
=
387
7
s'iMS'fUx)
Sk1(x) = sft(x)+xSk1
+ 1
(x)
which means that we have a Pascallike rule of formation for the elements of the convolution triangle. An element in the kth column in the sum of elements in the (k  l)st and (k + 1)st columns as shown in the convolution triangle forS 7 (the Catalan numbers) given below: Table 1.3 Convolution Triangle for S1 : 1, 1,2, 5, 14, 42, •••
1 1 1 1 2 3 2 5 9 5 14 28 14 42 90
1 1 1 4 6 5 14 20 27 48 75 110 165 275 429
Scheme: z = x + y
1 J—v X
\
Z
\
Notice that, except for spacing, the rule of formation is the same as that for Pascal's triangle. For Pascal's triangle in rectangular form, the scheme would be a diagram like below, where z = x + y:
Similarly, for / = 2, we obtain rk,..<_rk1,,,..^21M Sk2(x) = S^' (x)+xSk2
(1.6)
which leads to the generation of the convolution triange for $2 below. Table 1.4 Convolution Triange f o r S 2 : 1, 1, 3, 12, 55, 1 1
3 12 55
1
1
2
1 3
7 30 143
1 4
5
1 6

Scheme: z = x + y
12 18 25 33 55 88 130 182 273 455 700 1020
For/ = 3, we have Sk2(x) = Sk3'1(x) + xSk3+3(x)
(1.7)
which gives a scheme similar to those preceding, using a grid in which the column entries to be added are separated by three spaces, as computed below: Table 1.5 Convolution Triangle for S3: 1, 1,4,22, 140, 1 1 2 1 4 9 52 22 140 340
1 3 15 91 612
1 4 22 140 969
1 5 30 200 1425
1 6 39 272 1995

Scheme: z =
x+y
EI
Returning for a moment to the matrices PJ and comparing them to the convolution arrays for the sequences just given, notice that, ignoring signs, P^1 contains the alternate columns of the Catalan convolution array, and that PJ is always composed of columns of a convolution array for the sequence in the first column. In fact, except for signs, the m a t r i x / 3 ^ always contains the zero th column, the (i + Dst column, the 2(i + 1)n column,
398
CATALAN AND RELATED SEQUENCES ARISING
[DEC.
— , and has its (k + 1) column given by the k(i + 1)st column of the convolution array for the sequence Sj, (Notice that the count of the columns for matrices begins with one, but for convolution arrays begins with zero.) We have proved this already in applying the Lemma. Now, to generalize, the formulation of the convolution triangle for Sj would require a grid in which column entries to be added were separated by / spaces, so that the generating function S/(x) for the zero th column of the convolution array for Sj satisfies
(1.8)
SJT1(x)+xSf+1M,
S$(x) =
where, of course, Sf (x) is the generating function for the (k  1)st column, k = 1,2, 3, —. Then, notice that this means that each row in the convolution array for any of the sequences S, is the partial sum of the previous row from some point on. Thus, each convolution array written in rectangular form has its / row an arithmetic progression of order i, / = 0, 1,2, 3, •••, and the constant of each of these progressions is 1. By previous results [ 4 ] , we have Theorem 1.1. The determinant of any n x n array taken to include the row of 1's in the convolution array written in rectangular form for any of the sequences Sj has value one. It will also be shown in a later paper that the determinant of any n x n array taken to include the row of integers (1, 2, 3, 4, —) and its first column the (j  1)st column of the convolution array has value
2. GENERATION OF CONVOLUTION TRIANGLES FOR SEQUENCES Sj FROM PASCAL'S TRIANGLE The convolution triangles for these sequences Sj are also available from Pascal's triangle in a reasonable way. If one looks at Pascal's triangle as given in Table 2.1, Table 2.1 Pascal's Triangle 1 1
1 1 1
6
1 4 5
1 3
1 2
1 3
6 10 15
1 4
1
10 20
5 15
1 6
1
and takes diagonals parallel to the central diagonal 1, 2, 6, 20, 20, 70, 252, •, ( ^
)
one sees that 1/1, 2/2, 6/3, 20/4, 70/5, 252/6, ••• = 7 , 1 2 , 5, 14, 42, »• 2(1/2, 3/3, 10/4, 35/5, 126/6,  ) = 1,2, 5, 14, 42, ••• 3(1/3, 4/4, 15/5, 56/6, 210/7, •) = 1, 3, 9, 28, 90, ••• 4(1/4, 5/5, 21/6, 84/7, 330/8,  ; = 1,4, 14, 48, 165,  , where successive parallel diagonals of Pascal's triangle produce successive columns of the Catalan convolution triangle. To write the convolution triangle for the sequence S2, one uses the diagonal
1,3, 15,84,495,  , ( ^ )
,,
and diagonals parallel to it: 1/1, 3/3, 15/5, 84/7, 495/9, ••• = 1, 1, 3, 12, 55, ••• 2(1/2, 4/4, 21/6, 120/8, •>•) = 1, 2, 7, 30, •••
1976]
FROM INVERSES OF PASCAL'S TRIANGLE MATRICES
399
3(1/3, 5/5, 28/7, 165/9, •••) = 1,3, 12, 55, ••• 4(1/4, 6/6, 36/8, 220/10, •••) = 1,4, 18, 88, •• 5(1/5, 7/7, 45/9, 286/11, )
= 1, 5, 25, 130,  .
Notice that we again produce successive columns of the convolution triangle from successive diagonals of Pascal's triangle. As a final example, we write the convolution triangle for S3 from the diagonal
1,4,28,220,
(4/?A7)
1820,,
and diagonals parallel to it:
///, 4/4, 28/7, 220/10, 1820/13, ••• = 1, 1, 4, 22, 140, ••• 2(1/2, 5/5, 36/8, 286/11, 2380/14, )
= 1, 2, 9, 52, 340, •••
3(1/3, 6/6, 45/9, 364/12,  ) = 1,3, 15, 91, 4(1/4, 7/7, 55/10, 455/13, )
= 1, 4, 22, 140, 
5(1/5, 8/8, 66/11, 560/14, )
= 1, 5f 25, 200,  .
Before we continue to the general case, observe the arithmetic progressions appearing in the denominators. For the Catalan numbers, the sequence Sf, the common difference is one; for S2, two; and for S3, three. For S3, for example, we find the parallel diagonals from Pascal's rectangular array by beginning in the leftmost column and counting to the right one and down 4 throughout the array. To get the sequence^ itself, we multiply the Pascal diagonal 1,4, 28, 220,  by 1 and divide by 1,4, 7, 10, 13, •••; to get the first convolution or SI, we multiply the first diagonal parallel to 1,4, 28, 220, ••• by 2 and divide by 2, 5, 8, 11, •••; for the second convolution or S3, we take the next parallel diagonal, multiply by 3, and divide by 3, 6, 9, 12, — ;and for £3, we multiply the kth diagonal by k and divide by k, k + 3, k + 6, k + 9, •••. To find the diagonals easily, write Pascal's triangle in rectangular form: Table 2.2 Pascal's Triangle in Rectangular Form
1 1 \ \ 2 > <>\ \ 1>
1
1 3
1
1
1
1
1
4
5
6
7
8
6
10
15
21
28
36 120
4
\ \ V15°
vox \
6
\ \ 7 \
2 1
\ \
28 ^
\
20
35
56
84
35
70
126
210
330
56
126
252
462
792
84
210
462
924
1716
Then the sequence Sf is given by
/ +1
t«+ 1)n \ \ " I
which diagonal is found by beginning in the leftmost column and counting to the right one and down (i + 1) throughout the rectangular Pascal array. The diagonals which lead to the convolution array for S, are parallel and below this first diagonal. To find the (k  1)stconvolutionS*,we multiply the k^ diagonal by/rand divide by k, k + 1, k + 2i, k + 3i, •••. The diagonals used to find the convolution triangle forS2 are marked in the array above. Now, we can find all the positive integral powers of the Catalan sequence in the convolution sense. However, let us not neglect the zero or negative powers. Here, we must adopt a convention, and call 0/0 = 1 and  0 / 0 =  1 . We find sf, S'j1, and S~y by following the same process as given above but using an extended Pascal's triangle which includes coefficients for the binomial expansion of (1 +x)~ .
400
CATALAN AMD RELATED SEQUENCES ARISING
[DEC.
To see this in perspective, let us write down the parallel diagonals and the numbers to multiply and divide by.
si
3(1/3, 4/4, 15/5y 56/6, 210/7, •
=
1,3,9,28,90,
SI
2(1/2, 3/3, 10/4, 35/5, 126/6, ••
=
1,2,5,14,42,
Si
1(1/1, 2/2, 6/3, 20/4, 70/5, 0
1, 1,2,5, 1 4 , 
0(1/0, 1/1, 3/2, 10/3, 35/4,  . )
1, 0, 0, 0, 0, 
s° 1
s: ss
 K 1 /  1 , 0/0, 1/1,4/2,15/3,56/4,..)
=
1,1,1,2,5,14,
 2 ( 1 /  2 ,  1 /  1 , 0/0, 1/1, 5/2,  ) = 1,  2 ,  1 ,  2 ,  5 , 
Thus, you see that if we write down the extra terms from "Pascal's attic," the process works in reverse to obtain all columns of the Catalan convolution triangle. This process will provide the zero and negative powers for any of the sequences S/. One can also complete the Catalan convolution array to the left to provide negative integral powers by using its rule of formation in reverse, which is the following scheme: _j X
y
x = z y
\ Z \
The rule of formation can be rewritten to work to the left for the convolution array for any of the sequences SiNow, write the complete Pascal array down in rectangular form as
1 7 21 35 35 21
1 6 15 20
15 6
1 5 10 10 5 1
1 _4 6 4 1 0
1 3 3 1 0 0
1 2 1 0 0 0
1 1 0 0 0 0
1
0 0
0 0
' I 'I I 'I
0
1 2 3 4 5
6
1 3 6 10 15 21
1 4 10 20 35 56
1 5 15 35 70 126
1 6 21 56 126 252
.. ••• •.. ••• •.. 
sgular arrangement. Now if we move the/ th row/placeJS to the left, / = 0,1 , 2,  , we form 1 6 10 4 0 0
1 5 6 1 0 0
1 4
3 0 0 0
1 3
1 0 0 1
1 2 0 0 1 6
1 1 0 1 6 21
1 0 1 4 15 56
1 1 1 1 1 1 4 2 3 1 5 6 28 3 6 10 15 21 84 120 10 56 20 35 70 126 210 330 495 35 126 252 462 792
1 7 36 165 715
Now, all diagonals which are parallel to 1, 2, 6, 20, 70, — are all vertical. By proper processing, as just described, we can obtain all columns of the Catalan convolution triangle. To obtain the column which gives us S1. we multiply the column above which starts with 1, k+ 1,  , by k and divide successive terms by k, k+ 1, k + 2, k + 3, k + 4, •••, for k = O, ±1, ±2, ±3,  , where we adopt the convention that 0/0 = 1 and  0 / 0 =  1 . If we begin again with the regular arrangement, but this time move the i th " ,row 2i spaces to the right, we obtain an arrangement which has co in 1 ,  2 , 6 ,  20, 70, ., as 4 1 1 1 1 1 1 1 1 1 1 1
5 21 84 330
4 15 56 210
3 10 35 126
2 6 20 70
1 3 10 35
0 1 4 15
1 0 1 5
2 0 0 1
3 1 0 0
4 3 0 0
5 6 1 0
1976]
FROM INVERSES OF PASCAL'S TRIANGLE MATRICES
401
With the same processing as above, we obtain the Catalan convolution array with alternating signs. This shows that Pascal's triangle itself contains all that the inverses of the Pascal matrices gives from properly processed columns in the Pascal convolution array. By similar movement of the rows of Pascal's triangle and proper processing, we can obtain sjf, i = 0, 1, 2, 3,  ; k = 0,±1, ±2,  . As we already know, the Catalan sequence Sx and its convolution triangle are obtained by processing properly the diagonal 1, 2, 6, 20, 70, —, and those diagonals parallel to it. Since Pascal's triangle has symmetry, we can use the parallel diagonals either above or below the central diagonal, when Pascal's triangle is written in rectangular form as in Table 4.4. Then, S1 is obtained by multiplying the parallel diagonal which begins with 1, k + 1, — by k and dividing successive entries by k, k+ 1, k+2, —. Now, suppose that we try the same process for the Catalan convolution array, using diagonals parallel to 7, 2, 9, 48, 275,  , the central diagonal of the array, as given in Table 1.3. 1/1, 2/2, 973, 48/4, 275/5,  = 1, 1, 3, 12, 55,  = S2 2(1/2, 3/3, 14/4, 75/5, 429/6,  ) = 1, 2, 7, 30, 143,  = S\ 3(1/3,4/4,20/5,110/6,637/7,) = 1 , 3 , 1 2 , 5 5 , 2 7 3 ,  = S\ 4(1/4,5/5,27/6,154/7,) = 1 , 4 , 1 8 , 8 8 ,  =
^
Surely you recognize the convolution array for the next of our sequences, S2! If this same process is used on the convolution array for 5,, one obtains the convolution array f o r S / * / . See [ 8 ] , [ 9 ] , [10]. 3. A SECOND GENERATION OF THE SEQUENCES S, FROM PASCAL'S TRIANGLE These arrays can be obtained in yet another way from the diagonals of Pascal's triangle written in rectangular form. To obtain the convolution array for S2 = \ 1, 1, 3, 12, 55, 273, —J, we multiply successive diagonals and divide by successive members of an arithmetic progression with constant difference 3 as follows: 1(1/1,4/4,2177,120/10,) = 1, 1 , 3 , 1 2 ,  = S2 2(1/2, 5/5, 28/8, 165/11,  ) = 1,2, 7, 30,  = S\ 3(1/3, 6/6, 36/9, 220/12,  ) = 1, 3, 12, 55,  = S\ 4(1/4, 7/7, 45/10, 286/13,  ) = 1, 4, 18, 88,  = S* The diagonals are obtained by beginning in the row of ones in the Pascal rectangular array and counting down one and righttwo, or by beginning in the column of ones and counting to the right one and down two. The multiplier is the same as the exponent ofS 2 / and the arithmetic progression used is k, k + 3, k + 6, —, k + 3n, n = O, 1,2,. To obtain the Catalan sequence, and its convolution triangle, we can use the diagonals obtained by counting down one and right one beginning in the column of ones (or in the row of ones) so that the beginning diagonal is 1, 3, 10, 35,  , and dividing by successive terms of arithmetic progressions with constant difference two as follows: 1(1/1,3/3,10/5,35/7,126/9,) = 1 , 1 , 2 , 5 , 1 4 ,  = S, 2(1/2, 4/4, 15/6, 56/8, 210/10,  ) = 1, 2, 5, 14, 42,  = S? 3(1/3,5/5,21/7,84/9,330/11,) = 1 , 3 , 9 , 2 8 , 9 0 ,  = S* Again the multiplier is the same as the exponent for Skp and the arithmetic progression used for the divisors is k + 2n, n = 0, 1,2,  . Then, we have a dual system working here for extracting the convolution array of the sequence S; from Pascal's triangle written in rectangular form. To obtain the convolution array for S,, we find successive diagonals from Pascal's array by beginning in the column of ones and counting right one and down i, taking the first diagonal as 1,1 + 2,  . (Or, we can work to the right, taking the diagonals successively that are parallel to the diagonal beginning with 1, i + 2, —, obtained by counting down one and right/throughout the array.)
402
CATALAN AND RELATED SEQUENCES ARISING
[DEC.
To write S,, we take the kth diagonal which begins 1, k + i + 1, —, multiply by k, and divide successively by the successive terms of the arithmetic progression k + in, n = 0, 1, 2, —. Explicitly, we write themth element of
S? as k + im
\
(i+ 1)m+k • m
')
for 1 = 0, 1,2,; k= 1,2,3,; m = 0, 1,2,. Many cases were shown which verify that the mth term of the (k  1)st convolution of the sequence Sj, denoted by Sj(m,k), is given by
(3.D
[
'M'rfe
m = 0, 1, 2,  ; k = 1, 2, 3,  ; i = 0, 1,2, — . Applying (1.8) leads to a rule of formation for the convolution array for any sequence Sj, (3.2)
Sj(m, k) = Sj(m, k
1) + s,(m 1,k
+ i).
Assume that (3.1) holds for all convolutions for the first (m  1) terms, and holds for the first (k  ^convolutions for the first m terms. Then sf(m,k) again will have the desired form of (3.1) as shown by
\[* k  1 # im+k  1 l\k  1 + im ' im + m + k — 1
l(i+1)m+k1 \ m l(i+ \
1)m + k  1 \ kfim +m+k m I ' (k+im)(im+m+k
+
k k + im
m
rn 1 im + m + k — 1 J
 1) 1)
4. THE SEQUENCE OF SEQUENCES S, TAKEN AS A RECTANGULAR ARRAY Next, suppose one simply considers the sequence of sequences Sj as the rows of a rectangular array, and considers the progressions appearing in the columns. We omit the first term for each sequence Sj Table 4.1 The Sequences Sj
So
1
1
1
1
1
1
1
1
St:
1
2
5
14
42
132
429
1,430
S>:
1
3
12
55
273
1,428
7,752
43,263
sy
1
4
22
140
969
7,084
53,820
420,732
S4:
1
5
35
285
2,530
23,751
231,880
2,330,445
S5:
1
6
51
506
5,481
62,832
749,398
9,203,634
S>: 57:
1
7
70
819
10,472
141,776
1,997,688
28,989,675
1
8
92
1,240
18,278
285,384
4,638,348
77,652,024
0
1
2
3
4
5
6
7
1
1
3
16
125
1296
16807
26^144
5
8*
Order of
AP: Constant: Form:
7 1/ 2° 3 th
4
2
5
3
6
4
I
nn2
Notice that the k column is an arithmetic progression of order (k  1), with common difference k means, using Eves' Theorem [ 4 ] , [ 5 ] ,
, This
Eves' Theorem: Consider a determinant of order n whose Ith column (i = 1, 2, —, n) is composed of any n successive terms of an arithmetic progression of order ft  7,/with constant a,% The value of the determinant is the product ^ / ^ 2 ••• an 
1976]
FROM INVERSES OF PASCAL'S TRIANGLE MATRICES
403
that we can write Theorems 4.1 and 4.2. Theorem 4.1: The determinant of any # x n array taken to include the column of 1's in the sequence of sequences S, rectangular array has value
J".
U 1=1
Theorem 4.2: Take a determinant of order n with its first column in the column of integers, and its first row along the row of ones of the rectangular sequence of sequences S; array. The value of the determinant is n+1 . 2 0
n r.
1=1
Proof: Subtract the (i  1)st row from the Ith row, / = n, n  1,  , 2, to obtain a determinant whose kth column is an arithmetic progression of order k 1 with constant (k + i)'k+"~2 anc j apply Eve's Theorem. Further, the following result seems to be true. Conjecture: Take an/? xn determinant such that its first column is the column of integers in the sequence of sequences S; rectangular array and its first row is the kth row, k= 1,2,3, •••. Then its determinant is given by
To prove that the constants of the arithmetic progressions have the form given, we quote Hsu [6, p. 480]: m < n m = n
r=0 2 and substitute n' = n  1, t = n , s = n,
(4.D
m = n  /, to obtain
<v'(n7')(n2az?)i<«"'>*»"*.
i£'
where we also make use of the known general form for the/ft*' 7 term of S,. 5. A CLASS OF COMBINATORIAL IDENTITIES 1
1
Returning to the first section, in Table 1.1 we computed matrices/^ . Now, since P,Pl = I, we can write an entire class of combinatorial identities. Notice that, since we are dealing with infinite matrices such that all nonzero elements appear on and below the main diagonals, P,PJ / for any n x n matrices/3,, Pj , and / formed from the n x n blocks in the upper left of the original infinite matrices. Since/5/ contains elements taken from Pascal's triangle, it is a simple matter to write the element in its (n + 1)st row and (j+ 1)st column as (5.1)
Pi(n,j)=
n = 0,1,2,;
{"1%).
j =
0,1,2,..
Now, the elements in PJ1 are the same as those in the convolution array for 5/, except for sign. When / = /, we have the Catalan convolution array, and the element of P*}1 in i t s / W 1)st row and (p + 1)st column is given by the (r  p)th element of the (2p)th convolution of 5 ; , or the (r  p)**1 element in the sequence S2p+1,which is, by (3.1), h
pVr.Pt  t1)"s,(rp,*+1)
while Pl(n,j)
=
, „ . .\ =("+>)
^ ^
(A
.
Since P7P~^ = I, the element in the (n + 1)st row and (p + 1)st column of/ is given by
)
404
CATALAN! AND RELATED SEQUENCES ARISING
0 =
J2 P^n'^P%P)'
[DEC.
n ? p.
i=0 Now, when/7 = ft we have the first column of/ 3 ; 7 , of the sequence Sf of Catalan numbers, and
«
'E#f(7)(V')
J=o which was given as (3.100) by Gould [ 7 ] . Since n >p + 1 gives nondiagonal elements of /, we also have the more general
(5.3)
0=yUlt^±JLl **
P+1+J
2j \, \ JP
l\
n+j\ 2j
I
We can further generalize by not restricting i. Let the element in the (r + 1)
row and (p + 1)
column
of/^be (5.4) Since PfPJ (* R)
pffr, p) = ( m(r
p,ip
+ 1) = Lzll^JLlkJLlJ
( ' +J j
= I, for/7 > p + 1 we obtain a nondiagonal element, giving the very general identity n = V (VJ~P[(1+i)P+
for/ = 0, 12,3, ;p = 0, 1, 2,>;mdn
11 l J + a \ I » + 4 \ \ JP I \J + 'J I
'
> p + 1.
Notice that, f o r / = 0, we have Pascal's triangle in both P,and PJ1, leading to
(5.6)
'E'^UPH/)' J=P
and, when / = 0 and p = 0, to the familiar identity, n
(5.7)
(~1>j
0=Y<
(•)•
1=0
For/? = 0 in (5.5), we are in the first column, and
a*
 t ^
['Y)[Ui)t^{';')[i)
j=0
j=0
gives a recursion relation for the terms of S,, as
(5.9)
o = £(i)iSi(n)
(;;/),
y=0
where $,Y/v /J is the/ f / 7 term of the sequence S . REFERENCES 1. Michael Rondeau, "The Generating Functions for the Vertical Columns of the [N + 1)Nomial Triangles," San Jose State University, Unpublished Master's Thesis, December 1973. 2. L. Carlitz, "Enumeration of TwoLine Arrays," The Fibonacci Quarterly, Vol. 11, No. 2 (April 1973) pp. 113130. 3. V. E. Hoggatt, Jr., and Marjorie Bicknell, "Sequences of Matrix Inverses from Pascal, Catalan, and Related Convolution Arrays," The Fibonacci Quarterly, Vol. 14, No. 3 (Oct. 1976), pp. 224232.
1976]
405
FROM INVERSES OF PASCAL'S TRSAWGLE MATRICES
4. Marjorie Bicknell and V.E. Hoggatt, Jr., "Unit Determinants in Generalized Pascal Triangles," The Fibonacci Quarterly, Vol. 11, No. 2 (April 1973), pp. 131144. 5. V.E. Hoggatt, Jr., and Marjorie Bicknell, "Special Determinants Found Within Generalized Pascal Triangles," The Fibonacci Quarterly, Vol. 11, No. 5 (Dec. 1973), pp. 457465. 6. L C. Hsu, "Note on a Combinatorial Algebraic Identity and its Application," The Fibonacci Quarterly, Vol. 11, No. 5 (Dec. 1973), pp. 480484. 7. H. W. Gould, "Combinatorial Identities," Published by the Author, Morgantown, W. Va., 1972. 8. P. Bruckman and V. E. Hoggatt, Jr., "HConvolution Transform," The Fibonacci Quarterly, Vol.13, No. 4 (Dec. 1975), pp. 357368. 9. V. E. Hoggatt, Jr., and Marjorie Bicknell, "Pascal, Catalan, and General Sequence Convolution Arrays in a Matrix," The Fibonacci Quarterly, Vol. 14, No. 2 (April 1976), pp. 135142. 10. V. E. Hoggatt, Jr., and Marjorie Bicknell, "Numerator Polynomial Coefficient Arrays for Catalan and R e lated Sequence Convolution Triangles," to appear, The Fibonacci Quarterly, February, 1977. *kkkkkk
EXPONENTIALS AND BESSEL FUNCTIONS BRO. BASIL DAVIS, C. F. C. S t Augustine's High School, P. 0. Basse"m Road, 40102 Maharashtra, India and V . E . HOGGATT, JR. San Jose State University, San Jose, California 95192
A Bessell function of orders may be defined as follows: (1 )
J (x)=Y
/ * \n+2k
^
x=o It may be easily shown that for integral n,J^(x) is the coefficient of Un in the expansion of
"p [!("£)] i.e.,
(2)
un
"4J(«£)]I;
^>
A7=CQ
Now let
(3)
u
1
=
L2k+1,
sa
where L2k+1 ' Lucas number defined by (4) L1 = 1, L2 = 3, Ln = Ln^ + Ln2 . where n is any integer. Equation (3) becomes u  uL2k+i 1 = 0with roots 2k+i _ ,. , /p T X2k+1
(i^)"«
where
a
a
^
_ l±Jl
and
and
are the roots of the well known quadratic
(5) [Continued on page 418.]
0 2 = +1.
(i^p '.p&
 L^H
2k+1