1

Suppose that we have some $n$ numbers.

As an example let us take $n=4$ and call that numbers $a,b,c,d$. We can parenthesise them in these ways:$(a,b,c,d)$, then $((a,b),c,d)$, then $(a,(b,c),d)$, then $(a,b,(c,d))$, then $((a,b),(c,d))$, then $((a,b,c),d)$, then $(a,(b,c,d))$, then $(((a,b),c),d)$, then $((a,(b,c)),d)$, then $(a,(b,(c,d))$, then $(a,((b,c),d)$.

How to calculate this number for arbitrary $n$?

  • 2
    The problem of how many fully parenthsized arrangements there are is solved by the Catalan numbers, about which there are several previous Questions. All of your examples show an outermost pair of parentheses, so perhaps your intention is to require those. – hardmath Sep 29 '17 at 23:25
  • @hardmath maybe they are taking it to be a 4-tuple so that the order of a,b,c and d can't change ? –  Sep 29 '17 at 23:27
  • @hardmath But Catalan numbers give $14$ for $n=4$ while we have $11$ here, what is missing? –  Sep 29 '17 at 23:27
  • I see what problem they solve, they forbid some groupings. –  Sep 29 '17 at 23:36
  • @AntoinedePaladin The Catalan number $$C_n=\frac{\binom{2n}n}{n+1}$$ is the number of ways of fully parenthesizing a product of $n+1$ factors, so for $4$ factors the relevant Catalan number is $C_3=5.$ – bof Sep 29 '17 at 23:41
  • @bof Ok, then Catalan number for this problem would be $5$, but we have eleven here? –  Sep 29 '17 at 23:43
  • because you haven't specified product maybe... –  Sep 29 '17 at 23:52
  • 1
    https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Hipparchus_number – Steven Stadnicki Sep 29 '17 at 23:55
  • 2
    (Note: I found this by just going to OEIS and typing '1,1,3,11' which I highly recommend as a first step with unfamiliar sequences.) – Steven Stadnicki Sep 29 '17 at 23:56
  • @StevenStadnicki This looks like the right thing. Thank you, man. –  Sep 29 '17 at 23:57
  • @AntoinedePaladin Yes, because Catalan number only counts fully parenthesized expressins a(b(cd)), a((bc)d), ((a(bc))d, ((ab)c)d, (ab)(cd), while OP also counts abcd, (ab)cd, a(bc)d, (abc)d, etc. – bof Sep 29 '17 at 23:57

1 Answers1

4

These are the "Schröder-Hipparchus", or "Super-Catalan", numbers: https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Hipparchus_number . Neither the Wikipedia nor the OEIS page for them seems to give any asymptotics for them.

(Note that I found this by searching '1,1,3,11' on OEIS, which I highly recommend as a first step when dealing with unfamiliar sequences.)

Steven Stadnicki
  • 51,746