|WikiProject Mathematics||(Rated B-class, Mid-importance)|
- 1 Untitled
- 2 To Do list for this article
- 3 "prepositional groups"
- 4 History
- 5 3x3 grid image in SVG
- 6 Graphical relation between Catalan numbers, stairs with slope<45°, triangulated polygons
- 7 Ballot problem
- 8 hankel matrix stuff
- 9 RE: Catalan Recurrence
- 10 Two more Catalan problems
- 11 Catalan numbers
- 12 Other kind of Catalan numbers?
- 13 Ballot problem/second proof
- 14 Is the definition of Dyck's word correct?
- 15 Trees and catalan numbers
- 16 As a binomial coefficent
- 17 New non-geometric bijective proof
- 18 Section "quadruple factorial"
- 19 Second proof
- 20 Incorrect Equation
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
- 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)
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)
Ming An-tu discovered them before but they were published in 1839. 126.96.36.199 03:27, 31 October 2005 (UTC)
3x3 grid image in SVG
I've created the 3x3 grid image in SVG for the article in the spanish wikipedia:
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
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)
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.
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 be the Hankel-matrix formed fromed by the Catalan-numbers: (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: is the number of paths of right and 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, . 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 be a matrix we get from half of the elements from the Catalan-triangle like this: . 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 . For this, we need to prove that . Now is, by definition, the number of paths of right and 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 long and a second one that's long. Let be the number of right segments in the first part of the path. Then, clearly, is positive because this part is a prefix, and this part has up segments. Also, the second part of the path has right segments and 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 by multiplying the number of valid first parts and the number of valid second parts, and summing this product for every . The number of valid first parts is, by definition . 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 right pointing segments and upward pointing ones, and each of whose prefixes have no less right segments then up segments. The number of such paths is so the matrix equation is indeed true.
- Now observe that if and , so is a triangular matrix with all ones in its diagonal. Thus, , thus indeed which is what we wanted to prove.
- The proof of that the determinant of the Hankel matrix starting with ,
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 we use the matrix defined by . This matrix contains the other half of the elements of 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 188.8.131.52 (talk) 15:46, 26 January 2011 (UTC)
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)
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 184.108.40.206 (talk • contribs)
- I've added an explicit explanation of that. Michael Hardy 02:07, 22 June 2007 (UTC)
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)
- More relevantly, the number of terms is Cn. Similarly, the number of terms in the expansion of (a1+a2+...+ak)n is . 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
Other kind of Catalan numbers?
- 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
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 .--RDBury (talk) 17:11, 8 February 2009 (UTC)
Is the definition of Dyck's word correct?
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
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
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?:
New non-geometric bijective proof
I have added a new bijective proof aimed to directly derive the fascinating 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.
Section "quadruple factorial"
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)
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)
The last formula in the first equation of the page: Is incorrect (or at least gives inconsistent answers with the other formulas), for example for n = 0, 1, 2, 3, 4, 5 this gives: 1, 1, 2, 4, 14, 36 but should be: 1, 1, 2, 5, 14, 42
- (3+2)/2 * (3+3)/3 = 5. (5+2)/2 * (5+3)/3 * (5+4)/4 * (5+5)/5 = 42. It is also easy to check that this formula agrees with the factorial formula. --JBL (talk) 14:55, 27 November 2015 (UTC)
- You are completely right, this was my mistake. (Agold1982)