Ashwanth.K's blog

Help needed: Catalan Numbers
By Ashwanth.K, history, 3 months ago, In English

Let $$$C_i$$$ be $$$i^{th}$$$ catalan number. Is it possible to derive a generalised formula for convolution of catalan numbers in $$$k$$$ variables.
For example:

For $$$K = 2$$$,
$$$\sum_{i=0}^{n} {C_iC_{n-i}} = C_{n+1}$$$

For $$$K = 3$$$,
$$$\sum_{i=0}^{n} \sum_{j=0}^{n} {C_iC_jC_{n-i-j}} = C_{n+2} - C_{n+1}$$$

For $$$K = 4$$$,
$$$\sum_{i=0}^{n} \sum_{j=0}^{n} \sum_{k=0}^{n} {C_iC_jC_kC_{n-i-j-k}} = C_{n+3} - {2 C_{n+2}}$$$

I wanted to know, does any formula exist for any generalized K?

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it -22 Vote: I do not like it

probably, yeah

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I tried to derive, but seemed hard..

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      I'd have to agree with you there

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +45 Vote: I do not like it

        bro said a bunch of nothing

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it -11 Vote: I do not like it

          Well let's take a second to think about the positive impact I made here: I took his post from the bottom to the top of the recent actions tab. Now, the probability that someone actually answers his question is quite a bit higher.

          → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Assuming F(k, n) = sum(Xik * C(n + i)) for i from 1 to k where Xik is coefficient of C(n + i) in F(k, n)

F(n, k + 1) = sum(F(t, k) * C(n — t)) for t from 0 to n (Combine first k factors while summing)

= sum(Xik * sum(C(S + i) * C(n — S)) for S from 0 to n) for i from 1 to k (Just written by expanding)

= sum(Xik * (C(n + i + 1) — (sum(C(j) * C(n + j)) for j from 0 to i — 1)) for i from 1 to k (Negation comes as some of the terms were missing from product(using formula for K = 2)

So I am getting somewhat recursive way of getting the coefficients, maybe implementation can help us get few more F's to make some observation.

→ Reply
»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

One silly implementation later:

K = 2
1 * C[n+1]
K = 3
1 * C[n+2] + -1 * C[n+1]
K = 4
1 * C[n+3] + -2 * C[n+2]
K = 5
1 * C[n+4] + -3 * C[n+3] + 1 * C[n+2]
K = 6
1 * C[n+5] + -4 * C[n+4] + 3 * C[n+3]
K = 7
1 * C[n+6] + -5 * C[n+5] + 6 * C[n+4] + -1 * C[n+3]
K = 8
1 * C[n+7] + -6 * C[n+6] + 10 * C[n+5] + -4 * C[n+4]
K = 9
1 * C[n+8] + -7 * C[n+7] + 15 * C[n+6] + -10 * C[n+5] + 1 * C[n+4]
K = 10
1 * C[n+9] + -8 * C[n+8] + 21 * C[n+7] + -20 * C[n+6] + 5 * C[n+5]
K = 11
1 * C[n+10] + -9 * C[n+9] + 28 * C[n+8] + -35 * C[n+7] + 15 * C[n+6] + -1 * C[n+5]
K = 12
1 * C[n+11] + -10 * C[n+10] + 36 * C[n+9] + -56 * C[n+8] + 35 * C[n+7] + -6 * C[n+6]
K = 13
1 * C[n+12] + -11 * C[n+11] + 45 * C[n+10] + -84 * C[n+9] + 70 * C[n+8] + -21 * C[n+7] + 1 * C[n+6]
K = 14
1 * C[n+13] + -12 * C[n+12] + 55 * C[n+11] + -120 * C[n+10] + 126 * C[n+9] + -56 * C[n+8] + 7 * C[n+7]
...

A pretty clear Pascal's triangle pattern, but... in each column, the numbers seem to be shifted down by double the normal amount! This could very well be related to the other formula for Catalan numbers:

$$$C_{n} = \binom{2n}{n} - \binom{2n}{n-1}$$$

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ooh, that's great, how did you come up with this? I just wanted to know how did u figure out this pattern, just as part of learning

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      brutfors

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        A realer answer: At some point, you'll see a lot of patterns appear in problems. It can be the Pascal Triangle, Catalan numbers, pentagonal numbers, Stirling's numbers of the second kind etc. Once you see them enough times, you start realising: "hey, I should probably memorise the first few terms of these sequences, so when there is a weird combinatorial problem, I can just bruteforce some small values and see if any of these sequences emerge!". Sometimes, it turns out the answer is really simple, like in this case. And now, once you have intuition for the pattern, proving mathematically (if necessary) should be really easy.

        So, in combinatorics, just as in game theory, it's always worth bruteforcing for a bit and looking for common patterns! Intuition rocks

        → Reply
»
3 months ago, # |
← Rev. 4   Vote: I like it +24 Vote: I do not like it

You can use generating functions to brute-force this.

A simpler way is to use the first relation (which is often used to derive the generating function $$$f$$$) in the form: $$$x f(x)^2 - f(x) + 1 = 0$$$. This resembles a second order recurrence. You can now do things like this:

  1. $$$f(x)^3 = f(x) \cdot f(x)^2 = f(x) \cdot (f(x) - 1) / x = (f(x)^2 - f(x)) / x = ((1 - x)f(x) + 1) / x^2$$$.
  2. $$$f(x)^4 = (f(x)^2)^2 = (f(x)^2 - 2f(x) + 1)/x^2$$$ etc.

Basically, you note that the $$$k$$$-variable identity is the convolution of the generating function with itself $$$k$$$ times. To find a general formula, a more direct way is to just expand:

$$$ f(x)^k = \left(\frac{1 - \sqrt{1 - 4x}}{2x}\right)^k = \frac{\sum_{i = 0}^{\lfloor k/2 \rfloor} (1 - 4x)^i \binom{k}{2i} - (1 - 2xf(x)) \sum_{i = 0}^{\lfloor (k - 1)/2 \rfloor} (1 - 4x)^i \binom{k}{2i + 1}}{(2x)^{k}} $$$

The RHS gives a linear function in the coefficients of $$$f(x)$$$ which are just the Catalan numbers.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this is awesome, so I can use ideas of generative functions to deal with simplifying any combinatorics expressions.

    → Reply