Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Discussion Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: Catalan number

Bottom of Page

1 to 34 of 34

  1.  
    • CommentRowNumber1.
    • CommentAuthorzskoda
    • CommentTimeDec 6th 2017

    Few words added at Catalan number.

    • CommentRowNumber2.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 6th 2017

    I added “binary” to tree.

    What does this have to do with the Cayley-Dickson construction?

    • CommentRowNumber3.
    • CommentAuthorzskoda
    • CommentTimeDec 7th 2017

    Thanks. This link to Cayley-Dickson is left from the version 1 written by Urs, I have no idea.

    • CommentRowNumber4.
    • CommentAuthorUrs
    • CommentTimeDec 8th 2017

    Thanks for the alert.

    I forget why I added that link to the Cayley-Dickson construction. Worse, I have no memory of adding it in the first place. (?)

    Googling for “Cayley-Dickson” and “Catalan number” does yield a couple of articles that mention both, but I don’t see any real connection. So I removed the link now.

  5. listified, and added interpretation as pointed endomorphisms in the simplex 2-category

    diff, v5, current

  6. wait, I meant the semi-simplex category Δ inj\Delta_{inj}

    diff, v7, current

    • CommentRowNumber7.
    • CommentAuthorDavid_Corfield
    • CommentTimeSep 3rd 2018

    Added a reference to treatment via species.

    diff, v8, current

    • CommentRowNumber8.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 3rd 2018
    • (edited Sep 3rd 2018)

    There should be out there a treatment that goes further than the Baez-Dolan paper on species, who in effect write that after setting up and solving the generating function identity for planar binary trees, and after doing some numerical messing around, one can arrive at the formula 1n+1(2nn)\frac1{n+1}\binom{2n}{n}. It’s that numerical messing around part that should be enacted straight through at a more categorified level, by setting up a ℤ/(n+1)\mathbb{Z}/(n+1)-action on a structure with (2nn)\binom{2n}{n} elements (or something like that).

    If I can recall how that goes, I’ll add to the article. It must be related to the monotonic lattice path interpretation.

  9. Indeed there is a bijective proof of the formula described over at the wikipedia article, which works by classifying monotonic lattice paths (= monotone injective functions [n]→[n][n] \to [n], counted by (2nn)\binom{2n}{n}) by their “exceedance” across the diagonal, and then observing that there is a reversible transformation reducing the exceedance of a path by one. If you think you can incorporate something like that into the nlab article, that would be great.

  10. …except that I seem to have been psyching myself out about injectivity. Monotone lattice paths correspond to arbitrary order-preserving functions [n]→[n][n] \to [n] (there is only one injective one), so everything really should be taking place in Δ\Delta rather than Δ inj\Delta_{inj}. I will fix that back.

  11. Let me try to be a bit more careful in order to sort out my confusion, since there was still a small mistake above. A monotonic lattice path on the n×nn\times n grid is just a shuffle of nn North steps with nn East steps, and is represented most concretely by an injective monotone function p:[2n]→[n]×[n]p : [2n] \to [n] \times [n] specifying the (x,y)(x,y)-coordinate p[i]p[i] of the path at a given time ii. To obtain a monotone function f p:[n]→[n]f_p : [n] \to [n] from the path pp, we can for example take the function

    f p=x↦π 2p[min{i∣π 1p[i]=x}]f_p = x \mapsto \pi_2 p[\min\{i \mid \pi_1 p[i] = x\}]

    which sends any xx coordinate to the first (= minimum) yy coordinate where xx appears along the path. Observe that such an f=f pf = f_p will always have the property that f(0)=0f(0) = 0, in other words it is an endomorphism [n]→[n][n] \to [n] in the category Δ ⊥\Delta_\bot of finite non-empty ordinals and order-and-least-element-preserving maps. (Alternatively, we can use max rather than min, and then we obtain an ff such that f(n)=nf(n) = n, in other words an endomorphism in Δ ⊤\Delta_\top.)

    Conversely, given any f:[n]→[n]f : [n] \to [n] in Δ ⊥\Delta_\bot, there is a lattice path p f:[2n]→[n]×[n]p_f : [2n] \to [n] \times [n] which can be described inductively as follows. It takes exactly x+f(x)x + f(x) steps to arrive at coordinate (x,f(x))(x,f(x)), and to get from (x,f(x))(x,f(x)) to (x+1,f(x+1)(x+1,f(x+1), it begins with a sequence of f(x+1)−f(x)f(x+1) - f(x) North steps, followed by a single East step.

    This establishes a bijection between lattice paths p:[2n]→[n]×[n]p : [2n] \to [n] \times [n] in Pos injPos_{inj} and endomorphisms f:[n]→[n]f : [n] \to [n] in Δ ⊥\Delta_\bot. Moreover, such paths pp stay above the diagonal just in case the corresponding endomorphisms ff lie above the identity.

  12. went ahead and split up the interpretation as upper lattice paths and as pointed endomorphisms in Δ ⊥\Delta_\bot into two separate interpretations

    diff, v11, current

    • CommentRowNumber13.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 4th 2018
    • (edited Sep 4th 2018)

    Re #9: thanks! The proof I was struggling to recall actually counts it as the equivalent expression 12n+1(2n+1n)\frac1{2n+1} \binom{2n+1}{n}. The picture is similar to the lattice path picture: one is trying to count the number of functions f:{1,…,2n+1}→{1,−1}f: \{1, \ldots, 2n+1\} \to \{1, -1\} such that

    • |f −1(1)|=n+1{|f^{-1}(1)|} = n+1,

    • |f −1(−1)|=n{|f^{-1}(-1)|} = n,

    • ∑ i≤jf(i)\sum_{i \leq j} f(i) is positive for every j≤2n+1j \leq 2n+1.

    The idea is that the cyclic permutations σ k=(12…2n+1) k\sigma^k = (1\; 2\; \ldots\; 2n+1)^k act on the set of all functions ff satisfying the first two conditions, and for each such ff, the function σ kf\sigma^k f satisfies the third condition for exactly one σ k\sigma^k. It’s explained pretty nicely in visual terms here.

    Dreaming out loud, I would find it nice if this could be related to something happening in the cycle category, but I don’t know how to do this yet.

    • CommentRowNumber14.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 6th 2018

    Rough start on recording some isomorphisms between various species counted by Catalan numbers. Not close to done.

    diff, v14, current

    • CommentRowNumber15.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 9th 2018
    • (edited Sep 9th 2018)

    A TON of work of mine on this entry has apparently been lost because of “an invalid LaTeX block”. Any possibility of retrieval?

    This took me DAYS to put together.

  16. Not sure exactly what you mean, but if you still have the opportunity to press “back” in your browser, you should recover the edit panel. But also you should not lose your edits when such an error occurs, though there is a known bug (unrelated to any recent changes) that seems to make this unpredictable.

    • CommentRowNumber17.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 9th 2018

    I did try hitting back. I can’t find it.

    • CommentRowNumber18.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 9th 2018

    The offending phrases when I tried to save my edit seem to have been “mountain ranges” and “stay-ahead races”. If that’s of any help.

  19. Yes, I can see in the logs where the LaTeX error was. The ’new’ code seems to have behaved correctly from that point of view, and it is intended that one receives an error; but one should not lose the content, the error should just appear on the top. Though as I say there may be an old bug such that this happens. I unfortunately (I realise this will be enormously frustrating if you do not have a saved copy of it) cannot recover your edit itself, it is not stored anywhere on the server if it is invalid.

    This is if I understand correctly that you had been working on something without saving it yourself. If you were in fact saving it and just cannot get it to the save to the nLab, that is no problem to fix.

    In the future we can try to add some kind of draft functionality to the nLab to try to avoid cases like this.

    • CommentRowNumber20.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 9th 2018

    Thanks for the info. Wasn’t saved however. Yes, it is very frustrating.

    Out of curiosity: I can’t figure out what triggered the error. I understand that some strings may be blocked (if they are considered salacious of offensive, for example, as one guess), but I don’t really see how any text I had really qualifies.

    • CommentRowNumber21.
    • CommentAuthorRichard Williamson
    • CommentTimeSep 9th 2018
    • (edited Sep 9th 2018)

    Yes, it is very frustrating.

    I understand. I have double-checked, and see where the (very old) bug is. I will prioritise fixing it, but it is non-trivial, so unfortunately I cannot do so now just now.

    I can’t figure out what triggered the error.

    Almost certainly it is due to a LaTeX block not being closed properly, i.e. missing a dollar sign at the end, or having an extra one. If you had not lost the edit, you would probably have seen immediately how to fix it.

    If you had been working on it for days, maybe you have at least part of the work saved?

    It is also a bit strange that you couldn’t find it when you click “Back” in the browser, I always recover it in that way. But it could be browser dependent (and anyhow of course we cannot rely on this, we need this to be handled properly).

    • CommentRowNumber22.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 9th 2018

    If you had been working on it for days, maybe you have at least part of the work saved?

    Sadly, not really – only in my head.

    Usually I don’t get an error message in a yellow header if it’s simply a matter of a missing dollar sign. And usually I don’t lose work like this – I’ve been editing the nLab for almost 10 years and usually know very well what to do. Sigh. (I’m not griping at you, though. I do appreciate your help.)

    I’ll try to gather back the steam in my head to do it all over again.

    • CommentRowNumber23.
    • CommentAuthorRichard Williamson
    • CommentTimeSep 9th 2018
    • (edited Sep 9th 2018)

    This particular validation error is new (a few days old) as such, it is needed because undetected syntax errors of this kind lead to hard-to-detect rendering issues. But the bug has been there forever, it will have occurred for the older validation errors as well, one just will have encountered these less often. It only occurs for pages over a certain size.

    The old renderer sometimes, it seems, ignored syntax errors of this nature, or made a best guess (often wrong) as to how to fix them. Thus we have a bit of a transition period now where we are fixing them. Urs has been doing most of that so far.

  24. I found a bit of time after all, and the bug should be fixed now. See here.

    • CommentRowNumber25.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 9th 2018

    Saving progress so far. Not done. Added to the list of structures enumerated by Catalan; added material on natural bijections between them.

    diff, v16, current

    • CommentRowNumber26.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeSep 10th 2018
    • (edited Sep 10th 2018)

    Thanks for putting in this work of writing (and restoring) all these nice explanations!

    I had an idea for another way of obtaining a more structural proof of the formula, based on Rémy’s algorithm for generating random binary trees. The algorithm (see the description at p.16 of this draft of Knuth’s Volume 4A, Section 7.2.1.6) works iteratively by starting from the trivial one-leaf tree, and then repeatedly picking any edge of the tree and growing a leaf off to the left or to the right: after nn iterations, the result is a binary tree with nn internal nodes, equipped with a random ordering of its n+1n+1 leaves. Since at each kkth iteration of the algorithm there are exactly (2k−1)⋅2(2k-1)\cdot 2 possible choices of an edge and a direction, after nn iterations we obtain the identity:

    (n+1)!C n=(2n−1)!!⋅2 n=(2n)!n!.(n+1)! C_n = (2n-1)!! \cdot 2^n = \frac{(2n)!}{n!}.

    I don’t think this quite counts as a “nice” bijective proof, since it is recursive and relies on having an arbitrary labelling of the edges of the tree. On the other hand, maybe there’s a nicer proof lurking in the identity

    (n+1)!C n=(2n−1)!!⋅2 n(n+1)! C_n = (2n-1)!! \cdot 2^n

    which apparently relates permutations, binary trees, chord diagrams, and subsets!

  27. added proof of the formula via Rémy’s algorithm

    diff, v19, current

    • CommentRowNumber28.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 10th 2018

    Completed the subsection “Method 2”.

    diff, v20, current

    • CommentRowNumber29.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 10th 2018
    • (edited Sep 10th 2018)

    Let me mull over your Method 3 for a while – thanks!

    I’m not sure the long section with the various bijections is a geodesic path linking together the various structures, although most of the steps are close to obvious once you start drawing pictures. A critical step seems to be getting from planar binary trees to planar trees, which is not visually immediate as far as I know, but at least the basic idea is pretty familiar when viewed in terms of exponential laws (cf. Goodstein sequences, etc.).

    I was struck by the two “simplicial” examples that you put next to each other. One was in terms of surjective maps (n)+(n)→(2n)(n) + (n) \to (2n), the other in terms of injective maps [2n]→[n]×[n][2n] \to [n] \times [n]. Doesn’t this remind you of the duality between finite linear orders (objects of Δ\Delta) and finite linear intervals (objects of Δ op\Delta^{op})? Applying Pos(−,(2))Pos(-, (2)) to a surjection, we get an injection, and the resulting injection Pos((2n),(2))→Pos((n)+(n),(2))≅Pos((n),(2))×Pos((n),(2))Pos((2n), (2)) \to Pos((n) + (n), (2)) \cong Pos((n), (2)) \times Pos((n), (2)) is identified with an injection [2n]→[n]×[n][2n] \to [n] \times [n], which is kind of nice.

    One other thing: in the pointed endomorphism description, I didn’t see how the x≤f(x)x \leq f(x) condition follows from pointedness. Maybe I misunderstood what you were saying.

    • CommentRowNumber30.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeSep 11th 2018
    • (edited Sep 11th 2018)

    A critical step seems to be getting from planar binary trees to planar trees, which is not visually immediate as far as I know, but at least the basic idea is pretty familiar when viewed in terms of exponential laws (cf. Goodstein sequences, etc.).

    The idea of seeing this bijection in terms of exponential laws was actually new and interesting to me. I’ve seen it described (I believe equivalently) in terms of a “left-child right-sibling correspondence” (also called “rotation correspondence”), which is at least mildly visual.

    I was struck by the two “simplicial” examples that you put next to each other. One was in terms of surjective maps (n)+(n)→(2n)(n) + (n) \to (2n), the other in terms of injective maps [2n]→[n]×[n][2n] \to [n] \times [n]. Doesn’t this remind you of the duality between finite linear orders (objects of Δ\Delta) and finite linear intervals (objects of Δ op\Delta^{op})?

    Indeed. I think of both of these as shuffles (with an additional constraint): a shuffle of n left parens with n right parens in the case of a Dyck word, and a shuffle of n north steps with n east steps in the case of a lattice path. But a (p,q)-shuffle can be defined in dual ways, either as a surjective map (p)+(q)→(p+q)(p)+(q) \to (p+q), or as an injective map [p+q]→[p]×[q][p+q] \to [p]\times[q]. (I first learned about this from a talk by Eric Hoffbeck.)

    One other thing: in the pointed endomorphism description, I didn’t see how the x≤f(x)x \leq f(x) condition follows from pointedness. Maybe I misunderstood what you were saying.

    Hmm. What I meant by pointed endomorphism is that f:[n]→[n]f : [n] \to [n] (as a 1-cell in the 2-category Δ ⊥\Delta_\bot) is equipped with a 2-cell id [n]⇒fid_{[n]} \Rightarrow f from the identity. I just recently added that definition to the article pointed endofunctor, but I guess it might have other connotations?? If so I can change the terminology, or in any case add clarification.

    By the way, I’ve also noticed a similar kind of fact about monads in Δ\Delta, and powers of two: a monad on [n][n] is fully determined by saying which of the elements in {0,…,n−1}\{0,\dots,n-1\} it fixes, and so there are exactly 2 n2^n different monads on [n][n].

  31. tried rephrasing the bit about pointed endomorphisms

    diff, v22, current

  32. tried rephrasing the bit about pointed endomorphisms

    …as well as some additional disambiguation.

    To get back to this point:

    I was struck by the two “simplicial” examples that you put next to each other. One was in terms of surjective maps (n)+(n)→(2n)(n) + (n) \to (2n), the other in terms of injective maps [2n]→[n]×[n][2n] \to [n] \times [n]. Doesn’t this remind you of the duality between finite linear orders (objects of Δ\Delta) and finite linear intervals (objects of Δ op\Delta^{op})?

    I guess that I was thinking of the simplices [n][n] as non-empty ordinals (objects of Δ\Delta) embedded into the category of posets and monotone maps, rather than as linear intervals embedded into the category of general intervals (= posets equipped with ⊥\bot and ⊤\top elements) and ⊥\bot-and-⊤\top-preserving monotone maps. In the way I saw it, it just so happens that the injectivity + monotonicity condition on the map p:[2n]→[n]×[n]p : [2n] \to [n] \times [n] forces p(0)=(0,0)p(0) = (0,0) and p(2n)=(n,n)p(2n) = (n,n)… But indeed maybe as you suggest it is better to think of pp as a morphism of intervals.

    I think this is probably related to an issue that came up a while ago when I first started writing the articles on the zeta polynomial and the order polynomial of a poset PP. Then it seemed to me most natural to (re)define the zeta polynomial as Z P(n)=|Hom([n],P)|Z_P(n) = |Hom([n],P)| (like the nerve of PP hit with cardinality), but this actually has an index shift of 2 relative to the definition found in the literature. Of course I should have taken the accepted definition more seriously! And perhaps it becomes more natural if analyzed in terms of linear intervals rather than in terms of linear orders.

    • CommentRowNumber33.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 11th 2018

    Started plans to look more closely at the relation to cyclic objects.

    diff, v23, current

    • CommentRowNumber34.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 11th 2018

    Re #32: thanks for clarifying the bit about “pointed”. Actually when you explained it in #30, it made total sense; I should have remembered that.

1 to 34 of 34

  1.