Talk:Catalan number

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Discrete mathematics
A selected article on the Mathematics Portal.


Untitled[edit]

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. :)

To Do list for this article[edit]

  • 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)

"prepositional groups"[edit]

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)

History[edit]

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

3x3 grid image in SVG[edit]

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.

Graphical relation between Catalan numbers, stairs with slope<45°, triangulated polygons[edit]

As an architect I try to understand things with graphics. See: http://home.versateladsl.be/vt649464/TrapVeelhNummering.PDF If someone wants to use it I can give a version without text.--Bleuprint (talk) 05:12, 8 February 2008 (UTC)

Ballot problem[edit]

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)

hankel matrix stuff[edit]

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  2u long and a second one that's  2v 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 if  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)
I'm reacting to this sentence: "The Catalan numbers form the unique sequence with this property." This cannot be true, as the Hankel transform is invariant under the binomial transform (see the article on the binomial transform). —Preceding unsigned comment added by 84.215.177.45 (talk) 15:46, 26 January 2011 (UTC)

RE: Catalan Recurrence[edit]

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)

Is it possible to explain why a particular root of the Quadratic equation is used instead of the another one? In the expanded presentation that is no justification on that. —Preceding unsigned comment added by 207.46.55.31 (talkcontribs)

I've added an explicit explanation of that. Michael Hardy 02:07, 22 June 2007 (UTC)

Two more Catalan problems[edit]

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)

These have been added.--RDBury (talk) 17:53, 8 February 2009 (UTC)

Catalan numbers[edit]

 a\,
 a(a+b)=\,
 a(a+b)(a+b+c)=\,
 a(a+b)(a+b+c)(a+b+c+d)=\,
a\,
ab+a^2\,
abc+ab^2+ca^2+2ba^2+a^3\,
a^2c^2+abcd+abc^2+adb^2+cda^2+ab^3+da^3+2acb^2+2bda^2+4bca^2+3a^2b^2+2ca^3+3ba^3+a^4\,

The sum of the entries of every row is  n! \, Twentythreethousand (talk) 16:36, 31 May 2008 (UTC)

More relevantly, the number of terms is Cn. Similarly, the number of terms in the expansion of (a1+a2+...+ak)n is {n+k-1 \choose n}. Both of these can be proven by mapping the terms to lattice paths.--RDBury (talk) 18:28, 8 February 2009 (UTC)
vvvv a shape or a patern numbers take.the knowledge of God whether you think he is dead or not.v

'''''''''''''''

,,,,,,,,,,,, —Preceding unsigned comment added by 74.198.10.74 (talk) 11:17, 28 August 2009 (UTC)

Other kind of Catalan numbers?[edit]

Where should we send the reader who typed "Catalan numbers" into the search box, looking for how to count to ten in Catalan? --Damian Yerrick (talk | stalk) 21:31, 23 August 2008 (UTC)

That would probably be Catalan language#Numerals but it doesn't exist yet.--RDBury (talk) 06:25, 4 January 2012 (UTC)

Ballot problem/second proof[edit]

The reflection method is described both here and in Bertrand's ballot theorem. I added a more obvious link in the article; should there be an attempt to merge? Also, it's not entirely incorrect to call it André's reflection method, he had the basic idea but without the reflection part. The reflections are essentially only a way of giving a one-one proof that {2n\choose n-1} = {2n\choose n+1}.--RDBury (talk) 17:11, 8 February 2009 (UTC)

Is the definition of Dyck's word correct?[edit]

The article says that "A Dyck word is a string .. such that no initial segment of the string has more Y's than X's" then it lists several examples including XXXYYY. But: X, XX, XXX, XXXY are all initial segments of XXXYYY and each of them has more X's than Y's.--Jirka6 (talk) 00:25, 10 April 2009 (UTC)

My fault, sorry. Of course it is correct. I switched X and Y.--Jirka6 (talk) 22:18, 13 April 2009 (UTC)

Trees and catalan numbers[edit]

The nice picture with green trees is correct, the description was not. There is an infinite number of binary trees (not necessarily full) with n leaves. Also, "ordered" is already implied by "binary". The picture actually belongs to (what used to be) the next item, I fixed that. --Ikska (talk)

As a binomial coefficent[edit]

What do you think? Is it worthy of inclusion in the article that a Catalan number can be written in terms of a generalized binomial coefficient?:

\begin{align}C_n
&= \frac{2n!}{n! (n+1)!}
= \frac{(1 \cdot 3 \cdot \ldots \cdot (2n-1))(2 \cdot 4 \cdot \ldots \cdot 2n)}{n! (n+1)!}
= 2^{2n} \frac{(\frac 12 \cdot \frac 32 \cdot \ldots \cdot \frac{2n-1}2)(\frac 22 \cdot \frac 42 \cdot \ldots \cdot \frac{2n}2)}{n! (n+1)!} \\
&= 2^{2n} \frac{\left(\frac{\Gamma(n+1/2)}{\Gamma(1/2)}\right)(n!)}{n! (n+1)!}
= 2^{2n} \frac{\left(\frac{\Gamma(n+1/2)}{(-1/2)\Gamma(-1/2)}\right)}{(n+1)!}
= -2^{2n+1} \frac{\left(\frac{\Gamma(n+1/2)}{\Gamma(-1/2)}\right)}{(n+1)!}
= -2^{2n+1} \binom{n-\frac 12}{-\frac 32}
\,,\end{align}

using the Gamma function. Thanks -- Quantling (talk) 17:01, 21 April 2010 (UTC)

New non-geometric bijective proof[edit]

I have added a new bijective proof aimed to directly derive the fascinating \tfrac{1}{n+1} factor in the formula. I think it makes a nice complement to the existing bijective proofs as it is not based on a geometric interpretation but instead uses Dyke words and calculates the factor algebraically by comparing coefficients.

I tried several approaches and found this to be the most economical. I made this proof up myself as I could not find a similar one with the same features on the web. Still it should be simple and straightforward enough to be immediately obvious and verifiable by anyone with basic math skills in order to justify its inclusion into wikipedia. If it has been done before (which seems likely), please feel free to add a reference.

Bernhard Oemer (talk) 16:02, 10 January 2011 (UTC)

Section "quadruple factorial"[edit]

What the heck is this section refering to? Where does the name "quadruple factorial" come from? Is it notable at all? Right now I'm inclined to delete it because I can't figure out what it's about, but if someone can tell me what it means, then I'd be happy to reverse my position. (Maybe it would be better as a subsection somewhere?) --JBL (talk) 13:32, 17 September 2012 (UTC)

Hearing nothing after one year, I've removed mentions of the "quadruple factorial". --JBL (talk) 03:10, 16 September 2013 (UTC)

Second proof[edit]

I have just finished some copyediting of the second proof to improve the English and flow of the proof. I tried to preserve as much of the section as I could, but it did require some significant changes to increase clarity and deal with some of the harder parts of the proof. I did not, at this time, put back the historical sentence concerning Andre's reflection method, since there is an editor who objects to that, and so, it should be discussed here. My feeling is that it should be returned since it has encyclopedic value and we are writing an encyclopedia, not a textbook. The statement is of interest and I should point out a comment concerning it made above on this talk page. Bill Cherowitzo (talk) 06:41, 8 January 2015 (UTC)

I would accept one sentence about the author if it provided some new information in addition to the reflection article. The point to discuss the authorship of reflection method, whenever you apply it is stupid verbosity and as any verbosity it was confusing: I could not even understand who is author of what. `Encyclopedia` does not mean that you copy-paste referred material under every reference. Which encyclopedic standard tells you that you must copy only the historic sections but not the whole referenced articles every time you use/refer them? Finally, sane people can distinguish Andreas reflection from Schwarz reflection without notice. Only dumb ones will follow the hyperlink and confuse it with Schwarz reflection. For them, you should notice that Andre's reflection principle is different from both electricity, economics, computer manufactoring, psychology and everything we have in the world (there are 20 reflection principles that you had to enumerate in your article at least). It seems that your purpose was to draw the proof into the stupid verbosity. I do not understand which fluence you are talking about. --Javalenok (talk) 13:09, 11 January 2015 (UTC)