Talk:Catalan number

From Wikipedia, the free encyclopedia

Need to get page number, ISBN for reference to enumerative combinatorics vol 2, and perhaps write up some more examples from there. Dmharvey 19:07, 31 May 2005 (UTC)

The first formula accompanying the quadruple factorial discussion might be made more clear with some parentheses- i.e., (2n)!/n! rather than 2n!/n!. I know that with just a little thought it is obvious, but since factorial has precedence over multiplication it caught me for a moment. By the way, this is a very nice article. :)

1 To Do list for this article
2 "prepositional groups"
3 History
4 3x3 grid image in SVG
5 Ballot problem
6 hankel matrix stuff
7 RE: Catalan Recurrence
8 Two more Catalan problems

[edit] To Do list for this article

The generating function actually yields the formula for C_n pretty easily, using the binomial formula for the square root term. This should really be described somewhere as the "generating function proof of the formula"; then the "Proof of the formula" section should be relabelled "Bijective proofs of the formula".
Need to mention the Ballot problem somewhere, which is a generalisation of many of the ideas in this article.
What was Andre's first name? I can't seem to work this out.
Need to add this reference:

D. Andre, Note: Calcul des probabilites. Solution directe du probleme resolu par M. Bertrand, Comptes Rendus de l’Academie des Sciences, Paris, vol 105(1887), p. 436., where the reflection principle was first used (I think?)

I recall reading a long time ago (can't remember where) that the first disucssion of "exceedance" was in a probability setting. Consider a coin tossing game between A and B. They toss a coin 2n times. Heads gives A a point, tails gives B a point. Now, given that they each win n tosses, what is the probability that A is not ahead of B at any point of the game? You could also ask, for any k between 0 and n inclusive, what is the probability that A is ahead of B for precisely k turns? (you need to be a bit careful about how exactly you define when A is ahead.) The point is that it was shown that the answer does not depend on k, and so must be equal to 1/(n+1), which a priori is quite a surprising result. Would be nice to mention this in the History section, but the details need to be found.
My explanations of the two bijective proofs are a little wordy. Someone please write them better. Thanks.
Give C_3 examples/pictures for some of the other combinatorial interpretations listed.
Add more combinatorial interpretations; there are plenty of interesting and accessible ones still left. I don't have a copy of EC vol 2 handy.

Dmharvey 12:07, 1 Jun 2005 (UTC)

[edit] "prepositional groups"

I have deleted the following from the "history" section.

It has been shown that the number of possible interpretations of a sentence, function of the number of prepositional groups ("he saw a man on the hill with a telescope"), is the Catalan number series.

It doesn't belong under History. Perhaps it belongs in the list of combinatorial applications. But the text quality needs to be improved, and I don't really know what it's about. Dmharvey Talk 17:11, 6 Jun 2005 (UTC)

That's just the number of binary parse trees. Not particularly interesting, seeing as equiparseable sentences with distinct meanings are highly artificial anyway. EdC 10:41, 21 July 2006 (UTC)

[edit] History

Ming An-tu discovered them before but they were published in 1839. 24.203.251.69 03:27, 31 October 2005 (UTC)

[edit] 3x3 grid image in SVG

I've created the 3x3 grid image in SVG for the article in the spanish wikipedia:

http://es.wikipedia.org/wiki/Imagen:Catalan_number_3x3_grid_example.svg

I don't know about licensing, but I want to release it on the public domain as a trivial work. I hope it will be useful. Thank you.

[edit] Ballot problem

Dmharvey wrote in the TODO list above:

Need to mention the Ballot problem somewhere, which is a generalisation of many of the ideas in this article.

I've added Bertrand's ballot theorem to the See also section, of course, some more details are worth including. --Kompik 11:28, 11 March 2006 (UTC)

[edit] hankel matrix stuff

Does anyone have any references for this hankel matrices stuff? Thanks. Dmharvey 11:15, 31 May 2006 (UTC)

Yes. Firstly, let me say that I'll don't know anything about uniqueness of such a series, only that this series have an all ones Hankel-transform. I'll only talk about why the Hankel-transform of this sequence is all ones.

I've read of this property in the OEIS entry of Catalan numbers. I became curious and started to look for a proof. This entry refers to the article J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5. That article also states that the Catalan sequence has this property, and while it doesn't give a full proof, it does give a valueable hint to find it.

I've given this property as a task on a course, so I had to derive the complete proof, but I've never written the proof down completely, so it took me a while to reconstruct the proof from my old notebook and memory. As I think this is a notable property and proof, I'm glad you've asked about it so I'll finally write the proof down. Btw, the problem lists for that course are available on my homepage: this one is problem number 5 on series 7 of term 4 (automn term 2005/2006).

Now I'll draft the proof. The basic idea (from the article) is that we will find the LU decomposition of the Hankel matrix as it's easy to calculate the determinant from them. If you do the decomposition with a computer for some matrices, it's easy to guess the general statement.

Let $\mathbf H$ be the Hankel-matrix formed fromed by the Catalan-numbers:

h k, l = C k + l

(note that we are numbering rows and columns from 0 here). This matrix is this:

            1     1     2     5    14    42   132
            1     2     5    14    42   132   429
            2     5    14    42   132   429  1430
            5    14    42   132   429  1430  4862
           14    42   132   429  1430  4862 16796
           42   132   429  1430  4862 16796 58786
          132   429  1430  4862 16796 58786 208012

Now let's define the Catalan triangle like this:

c k, l

is the number of paths of

k

right and

l

upwards segments that always stay below the diagonal from the starting point (i.e. no prefix of the path has more upwards segments then right ones). Then, clearly,

C n = c n, n

. The Catalan triangle has some interesting properties, one of which I should write about later. The triangle looks like this:

            1     0     0     0     0     0     0     0     0     0
            1     1     0     0     0     0     0     0     0     0
            1     2     2     0     0     0     0     0     0     0
            1     3     5     5     0     0     0     0     0     0
            1     4     9    14    14     0     0     0     0     0
            1     5    14    28    42    42     0     0     0     0
            1     6    20    48    90   132   132     0     0     0
            1     7    27    75   165   297   429   429     0     0
            1     8    35   110   275   572  1001  1430  1430     0
            1     9    44   154   429  1001  2002  3432  4862  4862

Now let $\mathbf S$ be a matrix we get from half of the elements from the Catalan-triangle like this:

s u, w = c u + w, u - w

. $\mathbf S$ looks like this:

            1     0     0     0     0     0     0
            1     1     0     0     0     0     0
            2     3     1     0     0     0     0
            5     9     5     1     0     0     0
           14    28    20     7     1     0     0
           42    90    75    35     9     1     0
          132   297   275   154    54    11     1

I state that $\mathbf S \mathbf S^{\textrm T} = \mathbf H$ . For this, we need to prove that $C_{u+v} = \sum_w s_{u,w} s_{v,w} = \sum_{0 \le w \le \max(u, v)} c_{u+w,u-w} c_{v+w,v-w}$ . Now

C u + v

is, by definition, the number of paths of

u + v

right and

u + v

upwards segments which are under the main diagonal, which means that none of its prefixes have more up then right segments, and also that none of its suffixes have more right than up segments. Let's split this path to a first part that's

2 u

long and a second one that's

2 v

long. Let

u + w

be the number of right segments in the first part of the path. Then, clearly,

w

is positive because this part is a prefix, and this part has

u - w

up segments. Also, the second part of the path has

v - w

right segments and

v + w

up segments, and all suffixes of this part has at most the same number of up segments then right pointing ones. It's also easy to see that if the first part of the path has no more up segments than right in any of its prefixes, and the second part of the path has no more right than up segments in any of its suffixes, we can combine these two parts to a valid path which stays under the diagonal. Thus, we can calculate

C u + v

by multiplying the number of valid first parts and the number of valid second parts, and summing this product for every

w

. The number of valid first parts is, by definition

c u + w, u - w

. To calculate the number of second parts, we have to mirror them, so reverse the order of paths in it and replace up paths with right ones and vice versa. Then we have a path which has

v + w

right pointing segments and

v - w

upward pointing ones, and each of whose prefixes have no less right segments then up segments. The number of such paths is

c v + w, v - w

so the matrix equation is indeed true.

Now observe that

s u, v = 0

u < v

and

s u, u = 1

, so $\mathbf S$ is a triangular matrix with all ones in its diagonal. Thus, $\det(\mathbf S) = 1$ , thus indeed $\det(\mathbf H) = \det(\mathbf S) \det(\mathbf S^{\textrm T}) = 1$ which is what we wanted to prove.

The proof of that the determinant of the Hankel matrix starting with

C 1

            1     2     5    14    42
            2     5    14    42   132
            5    14    42   132   429
           14    42   132   429  1430
           42   132   429  1430  4862

is also one is almost the same as above. The difference is that instead of $\mathbf S$ we use the matrix $\mathbf T$ defined by

t u, w = c u + w + 1, u - w

. This matrix contains the other half of the elements of $\mathbf C$ like this.

            1     0     0     0     0     0     0
            2     1     0     0     0     0     0
            5     4     1     0     0     0     0
           14    14     6     1     0     0     0
           42    48    27     8     1     0     0
          132   165   110    44    10     1     0
          429   572   429   208    65    12     1

Finally, let me ask you or anyone else reading this to feel free correcting errors or anything you don't like in this proof inline (unlike normal posts on talk pages). Thanks. – b_jonas 23:03, 31 July 2006 (UTC)

[edit] RE: Catalan Recurrence

The Catalan Recurrence

C(x)=SIGMA C(i) C(n-1)

has not been solved properly. A Quadratic eqn. appears out of nowhere. Can someone explain where it came from?

It's not "out of nowhere", although the explanation is not very explicit. It comes from realizing that the sum defines a Cauchy product. I'll see if I can add something on this. Michael Hardy 20:43, 20 August 2006 (UTC)

OK, I've expanded that section, adding a more leisurely derivation of the quadratic equation. Michael Hardy 21:07, 20 August 2006 (UTC)

[edit] Two more Catalan problems

Perhaps these two problems with Catalan solutions are already in the harder stuff in the article. If not, do they belong?

1. How many ways can 2n ordered objects be arranged in a 2 x n matrix so that the elements are strictly increasing left to right and top down? (sometimes posed as a photographer arranging 2n people in 2 rows so that the heights increase left to right and front to back)

2. How many ways can n non-intersecting diagonals be drawn in a 2n-gon? (How many ways can 2n people seated at a circular table shake hands with no one's arms crossing) Jd2718 18:00, 5 November 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../c/a/t/Talk%7ECatalan_number_10c6.html"