Talk:Catalan number

Untitled

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)

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

History

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

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

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

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

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\leq w\leq \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

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 (talk • contribs)

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

Acortis (talk) 18:45, 30 May 2021 (UTC) The recurrence relation :$C_{0}=1\quad {\text{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n}.$ does not appear ro be correct!!

 # python
 C = {}
 C[0] = 1
 for n in range(5):
   C[n+1] = 2*(2*n+1)//(n+2)*C[n]
 print(C)

 {0: 1, 1: 1, 2: 2, 3: 4, 4: 8, 5: 24}

Darcourse (talk) 06:45, 20 June 2021 (UTC) $C_{n+1}={\frac {1}{n+2}}{\binom {2n+2}{n+1}}={\frac {(2n+2)(2n+1)}{(n+2)(n+1)^{2}}}{\binom {2n}{n}}={\frac {2(2n+1)}{(n+2)(n+1)}}{\binom {2n}{n}}={\frac {2(2n+1)}{n+2}}C_{n}$

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)

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

Catalan numbers

$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^{2}c^{2}+abcd+abc^{2}+adb^{2}+cda^{2}+ab^{3}+da^{3}+2acb^{2}+2bda^{2}+4bca^{2}+3a^{2}b^{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 C_n. Similarly, the number of terms in the expansion of (a₁+a₂+...+a_k)ⁿ 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)

Other kind of Catalan numbers?

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)

This is actually a joke exercise in Stanley's book, asking the student to "Explain the significance of the following sequence: un, dos, tres, quatre, cinc, sis, set, vuit, nou, deu..." Miclugo (talk) 20:21, 23 September 2022 (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 ${2n \choose n-1}={2n \choose n+1}$.--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?:

${\begin{aligned}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 {1}{2}}\cdot {\frac {3}{2}}\cdot \ldots \cdot {\frac {2n-1}{2}})({\frac {2}{2}}\cdot {\frac {4}{2}}\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 {1}{2}}}{-{\frac {3}{2}}}}\,,\end{aligned}}$

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

New non-geometric bijective proof

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"

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

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)

Incorrect Equation

The last formula in the first equation of the page:

$C_{n}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\qquad {\mbox{ for }}n\geq 0.$

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

— Preceding unsigned comment added by Agold1982 (talk • contribs)

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

Name: Mingantu, Minggatu?

https://wiki.riteme.site/wiki/Minggatu

"Mingantu" felt bogus to me, so I Googled it, and found the more plausible entry, "Minggatu," above. My feeling is that this "Mingantu" thingie, and the related renaming of his hometown as "Ming Antu," apparently, by some Chinese bureaucrat, are the work of perhaps well-intentioned but semi-literate functionaries. The Han government in Beijing is faced with all sorts of ethnic frictions, and they're scurrying around trying to solve them, but clearly some of the people involved are acting without really understanding what they're doing. (We have the same sort of thing in the West, with all the halfwits who pronounce the Chinese capital a Frenchified "bay-zhhing." It's furrin, but if I make it sound French that will show people how cosmopolitan and sophisticated I am, right? Feh!)

Imho, we ought to go with the way the guy pronounced it himself, and in Roman letters that would be "Minggatu," to the minimum possible distortion.

Fixing this will involve inserting the Wikipedia reference as #14, and renumbering the higher footnote numbers, which I'm afraid is beyond my Wiki skills. Could somebody else maybe do that?

David Lloyd-Jones (talk) 12:31, 6 November 2017 (UTC)

Um, your feelings about this are irrelevant. None of the listed sources use this spelling, and if anything, the biography article should be moved to reflect the spellings we have in sources. --Deacon Vorbis (talk) 13:10, 6 November 2017 (UTC)

Should there be a mention of inversion of power series?

Should there be a mention of inversion of power series? One way to define the Catalan numbers is to say that they are the coefficients in the inverse series of x(1-x), regarded as a power series in x. In other words, if you set y=x(1-x) and solve for x as a series in y, you get them as coefficients. Maybe this follows pretty readily from one of the other descriptions given here. I don't feel confident enough to wade in and make a change to the article. Ishboyfay (talk) 23:22, 16 November 2017 (UTC)

Ishboyfay, there seems to already be a blurb about it at Lagrange inversion theorem#Binary trees. You could always just write a sentence or two that mentions something about it and link to there. --Deacon Vorbis (talk) 00:25, 17 November 2017 (UTC)

On further thought, it's so similar to what appears in Proof 1 that it's not a useful addition. Ishboyfay (talk) 03:50, 18 November 2017 (UTC)

Which Catalan number for counting triangulations of a polygon

Knowing that some Catalan number counts the number of triangulations of a polygon is part of the excitement of what mathematics is all about. Knowing which Catalan number it is, through the mnemonic that "the n-th Catalan number counts the case of n triangles" is intended to be the frosting on the cake. I'd like to put in the count of triangles without it getting reverted. Thank you, 64.132.59.226 (talk) 13:32, 30 January 2018 (UTC)

The flowery language about the excitement of mathematics really isn't needed. My concern when I reverted was that the new wording makes it sound like triangulations into other numbers of triangulations are possible, but those just aren't being counted here, which isn't the case. –Deacon Vorbis (carbon • videos) 13:51, 30 January 2018 (UTC)

Thank you Deacon Vorbis for the detailed feedback. Yes, I agree that triangulations formed "by connecting vertices with non-crossing line segments" will always have exactly n triangles and that simply inserting "n" into the article text could instead be interpreted as specified by Deacon Vorbis. In contrast, arbitrary triangulations of a convex (n+2)-gon could have more than n triangles, e.g. because triangles themselves can be further triangulated. What edits would you make to the following proposed language?:

C_n is the number of different ways a convex polygon with n + 2 sides can be triangulated into exactly n triangles. The following hexagons illustrate the case n = 4:

64.132.59.226 (talk) 14:54, 30 January 2018 (UTC)

I like the following better. What edits would you make to the following proposed language? Please speak up yea or nay lest your silence be considered acquiescence.

A convex polygon with n + 2 sides can be cut into triangles by connecting vertices with non-crossing line segments (a form of polygon triangulation). The number of triangles formed is n and the number of different ways that this can be achieved is C_n. The following hexagons illustrate the case n = 4:

64.132.59.226 (talk) 12:57, 31 January 2018 (UTC)

The discussion has ground to a halt so let's try the BOLD, revert, discuss cycle. Because the edit I am making attempts to address the prior criticism, if you find yourself compelled to revert the edit then also comment here as to your reasons. Make your comments constructive; "it would be better if we ..." helps much more than "that is worse because ..." because the former helps to find the right direction to go, but the latter lists only one of many possible directions that should be avoided. 64.132.59.226 (talk) 13:36, 2 February 2018 (UTC)

This version seems fine to me. --JBL (talk) 13:56, 2 February 2018 (UTC)

Redundancy in Applications in combinatorics

In the list of applications, applications 2, 3, and 13 are stating the same thing. Also, applications 4 and 12 are redundant. I am going to remove applications 3, 12, and 13 upon consensus.

Plaba123 (talk) 16:23, 15 October 2018 (UTC)

First of all, a lot of these are going to be fairly similar, and I think a little redundancy for listing what's counted is actually okay. That being said, I think 12 (rooted binary trees) is definitely just a repeat of 4 (same thing), so it's safe to remove. I think #13 (mountain ranges) is probably okay to remove too, but more so because it's really the same as #6 (lattice paths), although this one isn't quite as clear-cut. But 2 and 3 are probably different enough that they should have their own entries. If anything, #2 is too similar to #1, but the connection to #3 isn't quite so immediately obvious. –Deacon Vorbis (carbon • videos) 17:22, 15 October 2018 (UTC)

@Deacon Vorbis: Thanks for your input. I'll start off by removing #12 (rooted binary trees). Plaba123 (talk) 01:25, 16 October 2018 (UTC)

Second recursive formula

The second recursive formula was shifted one to the right, it returned 1 for C_0, 2 for C_1, 5 for C_2 and so on. OEIS gives the same recursive definition (https://oeis.org/A000108):

2*(2*n-1)*a(n-1) = (n+1)*a(n)

I see that my change was reverted, could it be incorporated? Pranomostro (talk) 21:06, 18 February 2019 (UTC) comment added by Pranomostro (talk • contribs) 20:51, 18 February 2019 (UTC)

Side note first: there's certainly nothing wrong with notifying someone on their talk page of a discussion on an article's talk page, but if you want to get someone's attention on an article talk page post directly, you can just WP:PING them (I'll generally use either the {{re}} or {{u}} template, depending). Anyway, about the recurrence relation, you might want to double check that you're using the right value for n. The formula that's already here is correct and agrees with what's listed at the OEIS. –Deacon Vorbis (carbon • videos) 02:11, 19 February 2019 (UTC)

@Deacon Vorbis: I'm sorry if I violated some wikiquette by notifying you on your talk page, thanks for the pointers :D

Now, about the recurrence relation, the following was my thought process:

When plugging in the indices [0;13]:

The given values for the catalan numbers were:

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

S1: $C_{n}={\frac {1}{n+1}}{2n \choose n}$ gives the following values for C_0, C_1, C_2 etc.:

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

OEIS lists the catalan numbers the same way:

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

S2: $C_{0}=1\quad {\text{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n}$ gives the following numbers (and is used in the current article):

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

Note that one $1$ is missing.

S3: $C_{0}=1\quad {\text{and}}\quad C_{n+1}={\frac {2(2n-1)}{n+1}}C_{n}$. This is equivalent to 2*(2*n-1)*a(n-1) = (n+1)*a(n) from OEIS and returns the following sequence:

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

Here is the code I used, in python3:

from math import factorial as fac


def binomial(x, y):
	try:
		binom = fac(x) // fac(y) // fac(x - y)
	except ValueError:
		binom = 0
	return binom

def s1(x):
	return binomial(2*x, x)/(1+x)

def s2(x):
	if x==0:
		return 1
	else:
		return (2*(2*x+1))/(x+2)*s2(x-1)

def s3(x):
        if x==0:
                return 1
        else:
                return ((2*(2*x-1))/(x+1))*s3(x-1)

arg=list(range(0,13))
print(list(map(s1,arg)))
print(list(map(s2,arg)))
print(list(map(s3,arg)))

There might still be good reasons to keep the current version. First of all, there is a proof for it in this article, and secondly, it is a lot more common. On the other hand, it may be misleading (it misled me at first as well). I hope I made my case clear here, and will stop pestering you now.

Have a nice day.

Pranomostro (talk) 21:16, 19 February 2019 (UTC)

@Pranomostro: You are mistaken, and the version in the article is correct. Your error comes from replacing n+1 and n with n and n-1 in the subscripts, but not also making the same substitution for the other copies of n. The simplest way to verify that you are mistaken is to plug in n=0 in the version in the article.—JBL (talk) 23:42, 19 February 2019 (UTC)

via Wolfram Alpha rising factorial

Using WA, one can use the following query: (5*4^(n-3) * (Pochhammer 7/2,n-3)) / (Pochhammer 5,n-3) for n=3,10

alternately, Table[ CatalanNumber@ n, {n, 0, 100}] --Billymac00 (talk) 18:44, 3 September 2020 (UTC)

And? --JBL (talk) 19:34, 3 September 2020 (UTC)

Relation to matrix chain multiplication

Thank you @JayBeeEll for your recent concern about my edit to this article. Would you please give more information about your comment "this is not an example of what is being discussed"? The paragraph is about the number of associative ways to multiply an ordered set of n+1 objects. For the matrix chain multiplication problem, the n+1 objects are matrices. To me, it is the premier example where people care about the association order for the multiplications. Thank you —Quantling (talk | contribs) 17:38, 8 February 2021 (UTC)

The paragraph is about the number of ways to associate, whereas mcm is the context in which people care about different associations. The latter is not an example of the former. In fact, the connection between the Catalan numbers (the topic of this article, and the common thread that binds all the different examples in that section together) and the mcm problem is rather weak: one does not need to know a priori how many parenthesizations there are in order to solve mcm, and there's nothing about mcm that is more Catalan-y than the generic observation about possible associations of any binary operation. I did not remove the link from the article -- it's now in the see also section -- but if you really think it would be better in the bullet point, we could talk about other phrasing. One possibility might be to extend the parenthetical in the previous sentence: "(or the number of ways of associating n applications of a binary operator, as in the matrix chain multiplication problem)". --JBL (talk) 17:54, 8 February 2021 (UTC)

That parenthetical works for me. Thank you —Quantling (talk | contribs) 19:53, 8 February 2021 (UTC)

Taking this to GA and maybe, beyond

If any talk-page watcher has any interest in taking this to a GA or improve the overall quality, I will appreciate their collaboration. Will start drafting at User:TrangaBellam/Catalan Number. Thanks, TrangaBellam (talk) 18:00, 21 April 2022 (UTC)

It needs a lot of work, but I am definitely interested. End-of-semester busyness may be an issue for me for the next few weeks, though. --JBL (talk) 18:02, 21 April 2022 (UTC)

We

I think using "we" in the proofs is kinda weird and should be removed — Preceding unsigned comment added by 2604:3D09:1580:9600:C884:4058:E2C4:3F13 (talk) 03:19, 17 May 2022 (UTC)

Method of images

@Darcourse et al. There is use of the method of images in the second proof of the Catalan numbers formula. While the method of images is used for continuous cases, such as energy potentials in the presence of boundary conditions, it is also used for discrete cases. A random walk that starts at the origin on the real line, that takes steps of ±1 , and that is prohibited from going to −1 — in our case the number of '(' minus the number of ')' cannot be −1 — can be modeled by adding the random walk to a "negative" of the random walk that starts at −2. For any given number of steps, both the random walk from the origin and the one from −2 have equal chance of ending up at −1, and thus adding that "negative" "image" that starts at −2 to the original random walk from the origin ends up zeroing all values at −1, which is exactly what we need when we are enumerating Catalan numbers.

I propose to mention this in the section on the second proof, via something like

Further information: Method of images

but I am open to alternatives. Thanks —Quantling (talk | contribs) 14:57, 16 October 2023 (UTC)

The MoI article is way too technical for the level the Catalan number article is aimed at, and the connection is no way obvious. You could add it to 'see also', but I can't see how it is related at all. Darcourse (talk) 03:55, 17 October 2023 (UTC)

The Method of images article is lacking an example that is a discrete case. I plan to make edits there and then revisit the present discussion. —Quantling (talk | contribs) 12:58, 17 October 2023 (UTC)

Connection to Mandelbrot set

If you take the variable c and run it through the function for the Mandelbrot set, $f(z)=z^{2}+c$, an infinite number of times, you get an infinite series denoted by:

$\sum _{n=1}^{\infty }C_{n}c^{n}$

where $C_{n}$ is the nth Catalan number. And the curve in the complex plane for which this infinite series equals two is precisely the boundary of the Mandelbrot set.  Denelson83  02:17, 19 January 2024 (UTC)

With the notation of this article, the formula is off by one, yes? I believe that the limiting value of f(f(... f(f(0)) ...)) = f(f(... f(f(c)) ...)) is $\sum _{n=0}^{\infty }C_{n}c^{n+1}$. One gets absolute convergence of the series for |c| < 1/4, so we'd have to explain what we mean by "you get an infinite series" for other values of c.

I cannot verify in a few minutes that the Mandelbrot set boundary is when the series value $\sum _{n=0}^{\infty }C_{n}c^{n+1}=2$, especially if it is to be meaningful when we don't have absolute convergence. If this is to go into the article, we'd need a quick proof (WP:CALC) or a citation. Thank you —Quantling (talk | contribs) 14:13, 19 January 2024 (UTC)

It is minimally cited in the OEIS entry for the Catalan Numbers, A000108, by Donald D. Cross. It is not a proof, but it does give you a brief idea as to the connection. Cross goes into this in a bit more detail here, illustrating a slow rate of convergence. --  Denelson83  20:05, 19 January 2024 (UTC)

This is cute but I would want to see a much better source (from the point of view of WP:RS) before adding anything about this to either article. --JBL (talk) 20:38, 19 January 2024 (UTC)

I have attempted to contact Donald Cross to see if he has been able to come up with a proof for this connection. It is just too bad we cannot note this as an unsolved conjecture, despite the fact that cursory observations provide support to it.

And I should have said "absolute value", as in $\left\vert \sum _{n=0}^{\infty }C_{n}c^{n+1}\right\vert =2$. --  Denelson83  19:45, 2 February 2024 (UTC)

Wikipedia is not part of the research literature, it is a tertiary source. If other people writing reliable, secondary sources comment on this as an usolved problem, then we can follow them. --JBL (talk) 20:28, 2 February 2024 (UTC)

Putting on my WP:CALC hat, let's define the "convergence" here. Let's write f₀(c) = 0 and, for positive integer n, let's write f_n(c) = (f_n−1(c))² + c. For any particular value of n, the value of f_n(c) is a polynomial function of c with integer coefficients. We'll write [c^m]f_n(c) for the integer coefficient of c^m in the polynomial f_n(c). For positive integer m, we have the convergence that

$$\lim _{n\rightarrow \infty }[c^{m}]f_{n}(c)=C_{m-1}\,,$$

the (m−1)-th Catalan number.

This convergence is not the same as

$$\lim _{n\rightarrow \infty }f_{n}(c)\,,$$

which converges only for those elements of the Mandelbrot set that converge to a point under the z² + c iteration, rather than either cycling around inside the Mandelbrot set or running off to infinity.

This convergence is also not the same as that for the infinite series

$$\sum _{m=1}^{\infty }C_{m-1}c^{m}\,,$$

which converges absolutely only for |c| < 1/4. (Well, maybe for |c| ≤ 1/4.)

I don't know which of these forms of convergence, if any, is the one that is being used in the comparison to 2.

Even if we iron out all these mathematical details, we still need a reliable source that this result has notability.

That's my 2¢. —Quantling (talk | contribs) 20:32, 2 February 2024 (UTC)

And such a reliable source is something I hope to one day find. --  Denelson83  21:42, 2 February 2024 (UTC)

@Quantling: Might this paper help? https://www.mdpi.com/2504-3110/5/3/92 -_  Denelson83  06:45, 4 December 2024 (UTC)