[Question]
  [
# Challenge
Write a function/program that outputs either the `n`'th element, or the first `n` elements, in the well known number sequence:
```
         1, 2, 4, 8, 16 ...
```
Oh, wait... I forgot the first few numbers:
```
1, 1, 1, 1, 2, 4, 8, 16 ...
```
Heck, I'll add a few more for good measure:
```
1, 1, 1, 1, 2, 4, 8, 16, 33, 69, 146, 312, 673, 1463, 3202, 7050, 15605, 34705 ...
```
---
The numbers are Generalized Catalan numbers given by the (zero-indexed) formula: 
$$a(n+1)= a(n) + \sum\_{k=2}^{n-1} a(k)\cdot a(n-1-k)$$
where 
$$a(0)= a(1)= a(2)= a(3) = 1$$
This is [OEIS A004149](http://oeis.org/A004149).
You may choose if you want to have the sequence zero- or one-indexed. The sequence must of course be the same, so you must rewrite the formula if you have it one-indexed.
  
[Answer]
# [Python](https://docs.python.org/2/), 51 bytes
```
f=lambda n,k=2:n<3or k<n and f(k)*f(n-k-2)+f(n,k+1)
```
[Try it online!](https://tio.run/##FcwxDoAgEAXR3lNsyYoWYmfgMBhFyeqHEBtPj9hN8TL5fc4EU2twl7/XzRMGcWaBnVMhsSCPjYIS7oPCKKNh3WIQPXENjYAiqHgcuzITLx3lEvG0C/2O6wc "Python 2 – Try It Online")
Simplifies the formula a bit:
$$a(n) = \sum\_{k=2}^{n-1} a(k)\cdot a(n-2-k)$$
$$ a(-1) = a(0)= a(1)= a(2) = 1$$
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~14~~ ~~13~~ 11 bytes
```
$ƒˆ¯Âø¨¨¨PO
```
[Try it online!](https://tio.run/##yy9OTMpM/f9f5dik022H1h9uOrQCBA/vCPD//9/QAAA "05AB1E – Try It Online")
Outputs the nth element, 0-indexed.
```
$                # push 1 and the input
 ƒ               # repeat (input+1) times
  ˆ              #  add the top of the stack (initially 1) to the global array
   ¯             #  push the global array
    Â            #  and a reversed copy of it
     ø           #  zip the two together, giving a list of pairs
      ¨¨¨        #  drop the last 3 pairs
         P       #  take the product of each pair (or 1 if the list is empty)
          O      #  take the sum of those products
                 #  after the last iteration, this is implicitly output;
                 #  otherwise, it's added to the global array by the next iteration
```
[Answer]
# [Perl 6](https://github.com/nxadm/rakudo-pkg), 44 bytes
```
{1,1,1,1,{sum @_[2..*]Z*@_[@_-4...0,0]}...*}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYKvwv9pQBwKri0tzFRzio4309LRio7SALId4XRM9PT0DHYPYWiCtVfu/OLFSIU1DMzrOyCD2PwA "Perl 6 – Try It Online")
Anonymous code block that returns a lazy infinite sequence of values. This pretty much implements the sequence as described, with the shortcut that it zip multiplies all the elements so far after the second element with the reverse of the list starting from the fourth element and adding an extra `1` at the end.
### Explanation:
```
{                                          }  # Anonymous code block
                                       ...*   # Create an infinite sequence
 1,1,1,1,                                     # Starting with four 1s
         {                            }       # Where each new element is:
          sum                                   # The sum of
              @_[2..*]                          # The second element onwards
                      Z*                        # Zip multiplied with
                        @_[@_-4...0  ]          # The fourth last element backwards
                                   ,0           # And 1
```
[Answer]
# JavaScript (ES6), 42 bytes
A port of [xnor's solution](https://codegolf.stackexchange.com/a/193186/58563).
0-indexed.
```
f=(n,k=2)=>n<3||k<n&&f(k)*f(n+~++k)+f(n,k)
```
[Try it online!](https://tio.run/##FctBDoIwEEDRPaeYBSEzDhqDS1rOQoPUaMkMAeOm1KtXu/qb91/u4/Zpe67vs@h9ztlblDbYjuwg5nYcwUjTeAx08ij8ZQ7EvhDKXjcUsHDtQcBAV8pMECuASWXXZb4s@sDRYR0l0Z/WscyURuqrlH8 "JavaScript (Node.js) – Try It Online")
---
# JavaScript (ES6), ~~83~~ 75 bytes
A faster, less recursive, but significantly longer solution.
0-indexed.
```
f=(n,i,a=[p=1])=>a[n]||f(n,-~i,[...a,p+=(h=k=>k<i&&a[k]*a[i-++k]+h(k))(2)])
```
[Try it online!](https://tio.run/##FY1BCoMwEADvfcUeRLJNDK1XXT8SAi5WaxpJREsvar@e2tPAMDAv/vDaLW5@FyE@@pQGEkE5xWRmulukhk2w@z6ctvg6ZbTWrGZJYiRPja9dnrPx9srGFVJ6K0fhEUWJFtMQFxGA4FZBgBrKP6VE2C4AXQxrnHo9xadoWWRbOPBMs@084dFidTnSDw "JavaScript (Node.js) – Try It Online")
[Answer]
## Haskell, ~~49~~ ~~43~~ 39 bytes
```
a n=max(sum[a k*a(n-2-k)|k<-[2..n-1]])1              
```
[Try it online!](https://tio.run/##BcExDoAgDADAr3RwEJMSYXGRlxCGDiaS0oaIJg7@vd6dNPhozYxAk9A7j0cyAS80K0Zk9/GOOXqvGEpxwYSqQoJ@Vb1hAqEOBHn1PmzFfg "Haskell – Try It Online")
For `n<3` the `sum` is 0, so `max ... 1` raises it to `1`. 
Edit: -6 bytes thanks to @Jo King.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 36 bytes
```
Sum[#0@i#0[#-i-1],{i,3,#-1}]/. 0->1&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b7P7g0N1rZwCFT2SBaWTdT1zBWpzpTx1hHWdewNlZfT8FA185Q7X9AUWZeCVDeLs1BOVZN3yEoMS891cHQ9D8A "Wolfram Language (Mathematica) – Try It Online")
1-indexed.
The 2-indexed sequence is 4 bytes shorter: `Sum[#0@i#0[#-i],{i,#-4}]/. 0->1&`.
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b7P7g0N1rZwCFT2SBaWTczVqc6U0dZ16Q2Vl9PwUDXzlDtf0BRZl4JUM4uzUE5Vk3fISgxLz3VwdD0PwA "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~17~~ 13 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
4Å1λ£₁λ¨Â¦¦s¦¦*O+
```
Not shorter than [the existing 05AB1E answer](https://codegolf.stackexchange.com/a/193183/52210), but I wanted to try the recursive functionality of the new 05AB1E version as practice for myself. ~~Could perhaps be golfed by a few bytes.~~ EDIT: And it indeed can, see the recursive version of *@Grimy*'s 05AB1E answer below, which is **13 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)**.
Outputs the first \$n\$ items: [Try it online](https://tio.run/##yy9OTMpM/f/f5HCr4bndhxY/amoEUisONx1admhZMYjQ8tf@/9/IAAA).
Could be changed to the 0-based \$n\$'th item when replacing `£` with `è`: [Try it online](https://tio.run/##yy9OTMpM/f/f5HCr4bndh1c8amo8t/vQisNNh5YdWlYMIrT8tf//N7QEAA);  
or an infinite list by removing `£`: [Try it online](https://tio.run/##yy9OTMpM/f/f5HCr4bndj5oaz@0@tOJw06Flh5YVgwgtf@3//w0tAQ).
**Explanation:**
This implements the formula used in the challenge description like this:  
\$a(n)= a(n-1) + \sum\_{k=2}^{n-1}(a(k)\cdot a(n-1-k))\$
\$a(0)=a(1)=a(2)=a(3)=1\$
```
   λ               # Create a recursive environment,
    £              # to output the first (implicit) input amount of results after we're done
4Å1                # Start this recursive list with [1,1,1,1], thus a(0)=a(1)=a(2)=a(3)=1
                   # Within the recursive environment, do the following:
      λ            #  Push the list of values in the range [a(0),a(n)]
       ¨           #  Remove the last one to make the range [a(0),a(n-1)]
        Â          #  Bifurcate this list (short for Duplicate & Reverse copy)
         ¦¦        #  Remove the first two items of the reversed list,
                   #  so we'll have a list with the values in the range [a(n-3),a(0)]
           s       #  Swap to get the [a(0),a(n-1)] list again
            ¦¦     #  Remove the first two items of this list as well,
                   #  so we'll have a list with the values in the range [a(2),a(n-1)]
              *    #  Multiply the values at the same indices in both lists,
                   #  so we'll have a list with the values [a(n-3)*a(2),...,a(0)*a(n-1)]
               O   #  Take the sum of this list
     ₁          +  #  And add it to the a(n-1)'th value
                   # (afterwards the resulting list is output implicitly)
```
---
**13 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage) version of *@Grimy* (make sure to upvote [his answer](https://codegolf.stackexchange.com/a/193183/52210) if you haven't yet!):**
```
1λ£λ1šÂ¨¨¨øPO
```
Outputs the first \$n\$ items: [Try it online.](https://tio.run/##yy9OTMpM/f/f8NzuQ4vP7TY8uvBw06EVIHh4R4D///9GBgA)
Can again be changed to 0-based indexing or an infinite list instead:  
- (0-based) indexing `1λèλ1šÂ¨¨¨øPO`: [Try it online](https://tio.run/##yy9OTMpM/f/f8NzuwyvO7TY8uvBw06EVIHh4R4A/UNwSAA);  
- Infinite list `λλ1šÂ¨¨¨øPO`: [Try it online](https://tio.run/##yy9OTMpM/f//3O5zuw2PLjzcdGgFCB7eEeD//z8A). (Note that 2 bytes are saved here instead of 1, because the recursive environment starts with \$a(0)=1\$ by default.)
**Explanation:**
This instead implements the formula found by [*@xnor* for his Python answer](https://codegolf.stackexchange.com/a/193186/52210) like this:  
\$a(n) = \sum\_{k=2}^{n-1}(a(k)\cdot a(n-2-k))\$
\$a(-1) = a(0) = a(1) = a(2) = 1\$
```
 λ             # Create a recursive environment,
  £            # to output the first (implicit) input amount of results after we're done
1              # Start this recursive list with 1, thus a(0)=1
               # Within the recursive environment, do the following:
   λ           #  Push the list of values in the range [a(0),a(n)]
    1š         #  Prepend 1 in front of this list
      Â        #  Bifurcate the list (short for Duplicate & Reverse copy)
       ¨¨¨     #  Remove (up to) the last three value in this reversed list
          ø    #  Create pairs with the list we bifurcated earlier
               #  (which will automatically remove any trailing items of the longer list)
           P   #  Get the product of each pair (which will result in 1 for an empty list)
            O  #  And sum the entire list
               # (afterwards the resulting list is output implicitly)
```
[Answer]
# [Python 3](https://docs.python.org/3/), 59 bytes
really inefficient, `a(13)` doesn't finish on TIO.
```
a=lambda n,k=2:n<4or(n-k<2)*a(n-1)or a(k)*a(n-k-2)+a(n,k+1)
```
[Try it online!](https://tio.run/##JYo7DoAgEAWvsiWrWABWBk9iLNb4zepiCI2nR4zNZObl3U/ag7icqT/pmmYC0dzbTnwbopKGvcWKihgMEUjxX9xYrItorg3mOx6S1PChbIiwlq/AIRBJtkUZhyPmFw "Python 3 – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 17 bytes
```
1WṪ;+¥×Uṫ3SƲ;@Ʋ⁸¡
```
[Try it online!](https://tio.run/##AScA2P9qZWxsef//MVfhuao7K8Klw5dV4bmrM1PGsjtAxrLigbjCof///zU "Jelly – Try It Online")
A monadic link taking the zero-indexed \$n\$ and returning the list of generalized Catalan numbers from \$0\$ to \$n\$. 
[Answer]
# [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), 34 [bytes](https://codegolf.meta.stackexchange.com/a/9429/43319 "When can APL characters be counted as 1 byte each?")[SBCS](https://github.com/abrudz/SBCS ".dyalog files using a single byte character set")
-2 thanks to dzaima.
Anonymous prefix lambda.
```
{⍵≤3:1⋄+/(∇⍵-1),⍵(-×⍥∇¯2+⊢)¨4…⍵}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTfn/v/pR79ZHnUuMrQwfdbdo62s86mgHiugaauoAKQ3dw9Mf9S4Fih1ab6T9qGuR5qEVJo8algGlav@nPWqb8Ki371HfVE//R13Nh9YbP2qbCOQFBzkDyRAPz@D/aYdWPOrdbGgOAA "APL (Dyalog Extended) – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), 76 bytes
```
1:1:1:f[1,1,1]
f(x:z)|y<-x+sum(zipWith(*)(init$init z)$reverse z)=y:f(y:x:z)
```
[Try it online!](https://tio.run/##FYuxDsIgFAB3v@INDKA2sY5EJn@gmybq8GLAvpSSBtAU4reLkEsut9yIYdLWFlT30suGufX7ymNj@Cqz@KZTt@7Ce@aZlgvFkW8FJ0eRNUEWzOuP9kHXVEkanmTbyozkQMHiyUVgEHHScDzUwvJ7GouvULrreRj@ "Haskell – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~19~~ ~~17~~ 16 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Outputs the `n`th term, 1-indexed.
```
@Zí*Zz2)Å¤x}g4Æ1
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFrtKlp6MinFpHh9ZzTGMQ&input=OA)
```
@Zí*Zz2)Å¤x}g4Æ1     :Implicit input of integer U
@                    :Function taking an array as an argument via parameter Z
 Zí                  :  Interleave Z with
    Zz2              :  Z rotated clockwise by 180 degrees (simply reversing would be a bye shorter but would modify the original array)
   *                 :  Reduce each pair by multiplcation
       )             :  End interleave
        Å            :  Slice off the first element
         ¤           :  Slice off the first 2 elements
          x          :  Reduce by addition
           }         :End function
            g        :Pass the following as Z, push the result back to it and repeat until it has length U
             4Æ1     :Map the range [0,4) to 1s
                     :Implicit output of the last element
```
[Answer]
# [Haskell](https://www.haskell.org/), 65 bytes
```
f a|a<4=1|z<-g[2..a]=sum$zipWith(*)z$reverse(1:g[0..a-4])
g=map f
```
[Try it online!](https://tio.run/##FcoxCoAgFADQvVP8wcGCRKMp8hwN4fAHNSlDtBrEu1u9@W2Ydn0ctRrAgvMoRclzb9eBMVQy3Z5kFxZ3bbRrM4n60TFpKia78m/0o2obKz0GMNWjO0FCiO68gICFvwxc1Rc "Haskell – Try It Online")
You can use either `f` to get a single element of a sequence, or pass a list of values to `g` and get all the indexes for that list.
[Answer]
# [Forth (gforth)](http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/), 99 81 bytes
```
: f recursive dup 4 > if 0 over 3 do over 1- i - f i f * + loop else 1 then nip ;
```
[Try it online!](https://tio.run/##JYtLCgIxFASvUsxSTTDoQhS8SMjKvDgPhknIfK4fM7houguqU67raL7pqNaeJKp8trroLsStcOeNJq7kXSo3Yv4vZ1BM17XnxJkp54JMi@BYR5mZtfBq7tHZxxzwGrrqsBU7cGHAH59AVxK2/QA "Forth (gforth) – Try It Online")
Output is nth term and input is 1-indexed
Edit: Saved 17 bytes by switching to xnor's formula. Saved another 1 byte by using 1-indexed
### Code Explanation
```
: f                     \ start a new word definition
  recursive             \ mark that this word will be recursive
  dup 4 >               \ duplicate the input and check if it is greater than 4
  if                    \ if it is:
    0 over              \ create an accumulator and copy n to top of stack
    3 do                \ start counted loop from 3 to n-1
      over 1- i - f     \ recursively calculate f(n-1-i)
      i f               \ recursively calculate f(i)
      * +               \ multiply results and add to accumulator
    loop                \ end the counted loop        
  else                  \ otherwise, if n < 5
    1                   \ put 1 on the stack
  then                  \ end the if block
  nip                   \ drop n from the stack
;                       \ end the word definition
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 26 bytes
```
Ｆ⁵⊞υ¹ＦＮ⊞υΣ✂Ｅ⮌υ×κ§υλ³→Ｉ§υ±⁴
```
[Try it online!](https://tio.run/##TcqxDoIwFIXhnafoeG9SB6MmRibjxCAh4AvUeoXGtpC2l/j2FVx0OcP5Pz2ooEdlc36OQcABRcNxAJZii2Xx/So/carZ3SkA/nrHDjprNMFVTdDSTCESMEpxM44ivKQ4p8o/6L1qi7iU3bJl0QTjE5xa0w9JiouKCf5kTb1KBHtcbc7HvJntBw "Charcoal – Try It Online") Link is to verbose version of code. Prints the 0-indexed nth number, although it calculates using 1-indexing internally. Explanation:
```
Ｆ⁵⊞υ¹
```
Start with `a[0] = a[1] = a[2] = a[3] = a[4] = 1`. Yes, this is 1-indexed, but then with an extra zeroth value. That's code golf for you.
```
ＦＮ
```
Calculate an additional `n` terms. This is overkill, but it makes finding the desired term easier when `n<5`.
```
⊞υΣ✂Ｅ⮌υ×κ§υλ³
```
For each term, compute the next term as the sum of the terms so far termwise multiplied by the reverse of the terms so far, excluding three terms.
```
→
```
This is a no-op used to trick Charcoal into parsing the 2-argument form of `Slice`, otherwise I would have to use a less golfy way of removing three terms.
```
Ｉ§υ±⁴
```
Output the 4th last term.
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 30 bytes
```
J*4]1VQ=+J+eJsPP*M.t,PJ_PJ0;<J
```
[Try it online!](https://tio.run/##K6gsyfj/30vLJNYwLNBW20s71as4IEDLV69EJ8ArPsDLwNrG6/9/SwA "Pyth – Try It Online")
Returns the first \$n\$ elements of the sequence.
```
J*4]1VQ=+J+eJsPP*M.t,PJ_PJ0;<JQ # Full program, last Q = input (implicitly added)
J*4]1                  # J = 4 * [1] (=[1,1,1,1])
VQ                     # for N in range(Q):
  =+J                  #  J +=
     +eJ               #   J[-1] + 
        s              #    sum(                           )
           *M          #     map(__operator_mul,          )
             .t      0 #      transpose(          , pad=0)
               ,       #       [       ,         ]
                PJ     #         J[:-1] 
                  _PJ  #                 J[1::-1]
<JQ                    # J[::Q]
```
Alternative: Replace `<` with `@` to return the \$n\$-th element of the sequence, 0-indexed.
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~42~~ 41 bytes
```
f=->n{n<4?1:(4..n).sum{|i|f[i-1]*f[n-i]}}
```
[Try it online!](https://tio.run/##BcFBCoAgEADAr4SninbJ8BRlD7E9lCB4UKT0EOrbbeZJ99ea2UH67Ddx8LUXiH7AN7lcbDHKAqfRKA@Wam0hxbfrOeIyD@iukIsuSk9GaaKRnRFAnpHV9gM "Ruby – Try It Online")
1-indexed (to save 1 byte)
[Answer]
# [Octave](https://www.gnu.org/software/octave/), 73 bytes
```
g=(1:4).^0;for(i=3:(n=input('')))g(i+2)=g(4:i+1)*g(i-(2:i-1))';end;g(end)
```
[Try it online!](https://tio.run/##DcdRCoAgEAXA47gvMdKEQPEqQZTJ/miEdf2tn4Fpe9/eLFIS2eAxrlM8202c5kA1cb2eTkoBKMTaIRXygbXF8N@QC2wsoGKuRyz0C5HlAw "Octave – Try It Online")
-2 bytes thanks to Stewie Griffin. Once more, the imperative approach wins over the functional recursive approach. That one is shown below.
### [Octave](https://www.gnu.org/software/octave/), 75 bytes
```
f(f=@(a)@(n){@()sum(arrayfun(@(k)a(a)(k)*a(a)(n-2-k),2:n-1)),1}{2-(n>3)}())
```
[Try it online!](https://tio.run/##HclLCoAgFAXQ7dwbKmSDICjcyiNyIr2wH0S0dotGZ3CWcZdzKrl3zpWI2AcIA5R3ALdjhqyrXPFQBCTKlx/Vr1pvE43v1NakqZ/bW@jQ8AFZMlqWFw "Octave – Try It Online")
Captcha wanted to verify I was a human when posting this. To be honest, [I'm not so sure](https://xkcd.com/329/).
[Answer]
# [Perl 5](https://www.perl.org/) `-MList::Util=sum`, 61 bytes
```
sub a{my$b=-2+pop;$b<2||sum a($b+1),map{a($_)*a($b-$_)}2..$b}
```
[Try it online!](https://tio.run/##K0gtyjH9/7@4NEkhsTq3UiXJVtdIuyC/wFolycaopqa4NFchUUMlSdtQUyc3saAayI7X1AKJ6AIZtUZ6eipJtf@LEysVwDIKaflFCoZ6ekYG///lF5Rk5ucV/9f19cksLrGyCi3JzLEFmgcUMNUzMDQAAA "Perl 5 – Try It Online")
[Answer]
# [C/C++](http://www.cplusplus.com/doc/tutorial/), ~~70~~ ~~69~~ 67 bytes
-1 bytes thanks to Jonathan.
```
int a(int n){int k=2,s=0;while(++k<n)s+=a(k)*a(n+~k);return s?s:1;}
```
[Try it online!](https://onlinegdb.com/r1lN1BjmvH)
]