[Question]
  [
# Introduction
The *[telephone numbers](https://en.wikipedia.org/wiki/Telephone_number_(mathematics))* or *involution numbers* are a sequence of integers that count the ways \$n\$ telephone lines can be connected to each other, where each line can be connected to at most one other line. These were first studied by Heinrich August Rothe in 1800, when he gave a recurrence equation where they may be calculated. It is sequence [A000085](https://oeis.org/A000085) in the OEIS.
## Some help
* The first terms of the sequence are \$1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496\$
* It can be described by the recurrence relation \$T(n)=T(n-1)+(n-1)T(n-2)\$ (starting from \$n=0\$)
* It can be expressed exactly by the summation \$T(n)=\sum\limits\_{k=0}^{\lfloor n/2 \rfloor}{n\choose 2k}(2k-1)!!=\sum\limits\_{k=0}^{\lfloor n/2 \rfloor}\frac{n!}{2^k(n-2k)!k!}\$ (starting from \$n=0\$)
* There are other ways to get the telephone numbers which can be found on the [Wikipedia](https://en.wikipedia.org/wiki/Telephone_number_(mathematics)) and [OEIS](https://oeis.org/A000085) pages
# Challenge
Write a program or function which returns the \$n^{th}\$ telephone number.
# I/O examples
```
(0 based indexing)
input --> output
0  -->            1
10 -->         9496
16 -->     46206736
22 --> 618884638912
```
# Rules
* Input will be the index of the sequence
* The index origin can be anything
* As the numbers can get very large, you only need to support numbers as large as your language can handle
* [Standard I/O](https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods) rules apply
* No [standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default)
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so shortest code in bytes wins
  
[Answer]
# [Python](https://docs.python.org/3/), 33 bytes
```
f=lambda n:n<2or~-n*f(n-2)+f(n-1)
```
[Try it online!](https://tio.run/##FcXBCoMwDADQ@74ieGq2FtYMPRTtvygjKGyplFxE6q9XfZe3bjon@dTKw2/8T98RJEhPKR9OnmzEEb7uPFZOGRQWAfO23rbWX3WWCMMD1ryIGm52DT0VcC7CzkYxRE@lwXoC "Python 3 – Try It Online")
Uses the recursive formula.
[Answer]
# [Oasis](https://github.com/Adriandmen/Oasis), ~~7~~ ~~6~~ 5 bytes
```
àn*+1
```
[Try it online!](https://tio.run/##y08sziz@///wgjwtbcP///8bGvzX9QcA "Oasis – Try It Online")
```
# to compute the nth telephone number f(n):
à      # push the telephone numbers f(n-1) and f(n-2)
 n     # push n
  *    # multiply: n * f(n-2)
   +   # add: n * f(n-2) + f(n-1)
1      # base case: f(0) = 1
```
[Answer]
# [cQuents](https://github.com/stestoltz/cQuents), 10 bytes
```
=1:Z+Y($-2
```
1-indexed.
[Try it online!](https://tio.run/##Sy4sTc0rKf7/39bQKko7UkNF1@j/fwA "cQuents – Try It Online")
## Explanation
```
=1           first term in sequence is 1
  :          given n, output nth term in sequence (1-indexed)
             each term is
   Z+                     (n-1) term +
     Y                                 (n-2) term *    
      ($-2                                          (index - 2)
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 6 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Œ!ỤƑ€S
```
A monadic Link accepting a non-negative integer which yields a positive integer.
**[Try it online!](https://tio.run/##y0rNyan8///oJMWHu5ccm/ioaU3w////LQE "Jelly – Try It Online")** Or see the [first 10](https://tio.run/##y0rNyan8///oJMWHu5ccm/ioaU3w/6O7j@453A5kqrj//28JAA "Jelly – Try It Online") (`n=10` is too slow)
### How?
Builds all permutations of `[1...n]` (or if `n=0` just `[[]]`) and counts the number which are involutions.
```
Œ!ỤƑ€S - Link: integer, n     e.g.  0        3
Œ!     - all permutations          [[]]     [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    €  - for each:
   Ƒ   -   is invariant under:
  Ụ    -     grade                ( []       [1,2,3] [1,3,2] [2,1,3] [3,1,2] [2,3,1] [3,2,1] )
       -   }                        [1]     [1,      1,      1,      0,      0,      1]
     S - sum                        1       4
```
[Answer]
# TI-BASIC, ~~28~~ 22 bytes
```
∑((Ans nCr (2K))(2K)!/(2^KK!),K,0,int(.5Ans
```
Input is *n* in Ans.  
Output is the *n*th telephone number.
I was going to use the first formula mentioned in the challenge, but testing it resulted in **ERROR: OVERFLOW**s even on smaller numbers because TI-BASIC handles `n!!` as two successive factorials instead of a [double factorial](https://whatis.techtarget.com/definition/double-factorial).  
At least it has a builtin for summation notation!
**Update:**
I found that \$(2k-1)!!=\frac{(2k)!}{2^kk!}\$, so i replaced the function i was using to \${{n}\choose{2k}}\frac{(2k)!}{2^kk!}\$, which is represented as `(Ans nCr (2K))(2K)!/(2^KK!)` in TI-BASIC.
**Explanation:**
```
∑((Ans nCr (2K))(2K)!/(2^KK!)               ;sum the equation mentioned above
                             ,K             ;using K as the loop variable
                               ,0           ;starting at 0
                                 ,int(.5Ans ;and ending at the floor of half of the input
                                            ;leave the result in Ans
                                            ;implicit print of Ans
```
**Examples:**
```
10:prgmCDGF26
            9496
5:prgmCDGF26
              26
```
**Note:** TI-BASIC is a tokenized language. Character count does *not* equal byte count.
[Answer]
# JavaScript (ES6), 25 bytes
0-indexed. Uses the recurrence relation.
```
f=n=>n<2||f(--n)+n*f(n-1)
```
[Try it online!](https://tio.run/##y0osSyxOLsosKNHNy09J/f8/zTbP1i7PxqimJk1DVzdPUztPK00jT9dQ839yfl5xfk6qXk5@ukaahoGmJheqiCEWITMMISMjTc3/AA "JavaScript (Node.js) – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~12~~ 8 bytes
*-4 bytes by porting [Stephen's cQuent answer](https://codegolf.stackexchange.com/a/198243/6484)*
```
1λèsN<*+
```
[Try it online!](https://tio.run/##yy9OTMpM/f/f8NzuwyuK/Wy0tIFsAwA "05AB1E – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), 29 bytes
```
f n|n<2=1|m<-n-1=f m+m*f(n-2)
```
[Try it online!](https://tio.run/##BcE7DoAgDADQq3Rw8BMIMMNJjENDrBJpQ8TRs1vfO7Ffe62qBPJKDMm/HI0Ynwh44ZlGMWFSxiKQoN1FHhiAsQHB6qz1btMvU8Wjq8mt/Q "Haskell – Try It Online")
Implements the recursive formula.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 40 bytes
```
long f(long n){n=n<2?1:f(--n)+n*f(n-1);}
```
[Try it online!](https://tio.run/##NcvNCoJAEAfw@zzFIAi75YK7yrRm1ot0CW0XwaYQO4XPvk1Fpx/8P3oT@z6l6c4Rg/rC@sUdH9zJ7oMyhvWWN0GxsbpdU1RSAz7mkZeAKssH7I6YT8OZs4IL2WndwgogPd4uI6vPPKpSUsH@pZ/OiTBfl@fMWMoxWWjqhqAmV9KuIiDrva@p8o11bw "C (gcc) – Try It Online")
Merely copied from [@Arnauld answer](https://codegolf.stackexchange.com/a/198244/84844) 
[Answer]
# [Perl 6](https://github.com/nxadm/rakudo-pkg), 26 bytes
```
{{(1,1,++$×*+*...*)[$_]}}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/ulrDUMdQR1tb5fB0LW0tPT09Lc1olfjY2tr/xYmVCnpARWn5RQoGOgqGIGymo2Bk9B8A "Perl 6 – Try It Online")
[Answer]
# [Python 3](https://docs.python.org/3/), ~~81~~ \$\cdots\$ ~~57~~ 56 bytes
```
def f(n):
 a=b=i=1
 while i<n:a,b=a+i*b,a;i+=1
 return a
```
[Try it online!](https://tio.run/##FcxBCoMwEEDRvacYXCV1hCalCqnxLglNcKCMEqaUIp49rau/ePC3rywr32p9pgxZsXYNBB89edPAZ6FXAprYBYw@dHSJGB7UnVaSvAtDqHktIEAM6ooG72j@GdBatOM52wqxqNzu4iZ7QN/PsGcl2s1mOFpdfw "Python 3 – Try It Online")
Uses 0 based indexing and implements the recursive formula.
[Answer]
# [J](http://jsoftware.com/), 25 bytes
```
($:+]*$:@<:)@<:`1:@.(<&2)
```
[Try it online!](https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/NVSstGO1VKwcbKw0gTjB0MpBT8NGzUjzvyYXV2pyRr5CmpKBQqaeocF/AA "J – Try It Online")
`$:` is J's recursion operator, so this is a fairly straightforward impl of the recursive def.
I tried a couple other approaches (including using `^:` power of operator) but wasn't able to get shorter than this.
Am curious if anyone can improve it...
[Answer]
# [PHP](https://php.net/), 48 bytes
```
function f($n){return$n<2?1:f(--$n)+$n*f($n-1);}
```
[Try it online!](https://tio.run/##K8go@G9jXwAk00rzkksy8/MU0jRU8jSri1JLSovyVPJsjOwNrdI0dHWBgtoqeVogWV1DTeva/6nJGfkKSgYKCrp2Ckp6aRoGmnpKMXlK1lwQCUMDmIQhuowZXMYMVcbICCZjZASV@Q8A "PHP – Try It Online")
Implementation of the recursive function.
**Original version: 54 bytes** (port of @Noodle9 answer):
```
for($i=$j=1;++$n<$argn;$j=$k){$k=$i;$i+=$n*$j;}echo$i;
```
[Try it online!](https://tio.run/##K8go@G9jXwAk0/KLNFQybVWybA2ttbVV8mxUEovS86yBfJVszWqVbFuVTGuVTG1blTwtlSzr2tTkjHygyP//hgb/8gtKMvPziv/rugEA "PHP – Try It Online")
[Answer]
# Mathematica ~~46~~ 42 bytes
```
f=2^(#/2)HypergeometricU[-#/2,.5,-.5]I^-#&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78/z/N1ihOQ1nfSNOjsiC1KD01Pze1pCgzOTRaFyioo2eqo6tnGusZp6us9j@gKDOvJDot2iA2lgvGNkThmCFxjIxiY/8DAA)
Thanks to mabel for helping me shave 4 bytes by using what I think is an anonymous function.
As seen in <https://www.wolframalpha.com/input/?i=OEIS+A000085> and <http://mathworld.wolfram.com/ConfluentHypergeometricFunctionoftheSecondKind.html>
[Answer]
# [Red](http://www.red-lang.org), 53 bytes
```
f: func[n][either 1 > n: n - 1[1][n *(f n - 1)+ f n]]
```
[Try it online!](https://tio.run/##JYtBCoQwEAS/0nhalaDxIIsHH@F1mEMwExSWWQnx/Toi9KGroLLEa5FIfKUJ6dSVlEn2skmGxwydoHDw5JkUzSe9WLewx1b9s4R1M0s9vG1kOvKuBXSEaHpA5dxcwaj7SSpPh6@VNw "Red – Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 20 bytes
```
⊞υ¹ＦＮ⊞υ⁺§υι×ι§υ⊖ιＩ⊟υ
```
[Try it online!](https://tio.run/##TYm7DsIwDAD3foVHRwpDF5ZOCJYuKAM/EFKjRsqjcmzE3wdlQOK2uwu751B96t1p21EtzGaZXpUB13Ko3DU/idEY@H2XtOFF1rLRZ3g0Fh4xU8No4a/fKDBlKkIbRjNYJsexCF59E3T1QB2x9/ncT@/0BQ "Charcoal – Try It Online") Link is to verbose version of code. Uses the recurrence relation. Explanation:
```
⊞υ¹
```
`T(0)=1`
```
ＦＮ
```
Loop `n` times.
```
⊞υ⁺§υι×ι§υ⊖ι
```
`T(i+1)=T(i)+iT(i-1)`
```
Ｉ⊟υ
```
Output `T(n)`.
[Answer]
# [Keg](https://github.com/JonoCode9374/Keg), 21 bytes
```
:1≤[_1|;:@Tƒ^:;@Tƒ*+]
```
[Try it online!](https://tio.run/##y05N/@8QomBY89/K8FHnkuh4wxprK4eQY5PirKxBlJZ27P9jk7gSDBR07RQSdB41LDQACeuZmmrrcCUYIoQNUcTNEOJmSOJGRnBxIyOw@P//upl5AA "Keg – Try It Online")
Simply implements the formula in a recursive manner. The footer is mainly for testing purposes
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 80 bytes
```
.+
$*_;;_;
{`^_(_*;)(_*;_+)
$1_$2,$2
+`(,_*)_(;_+;(_*))|,
$3$1$2
^;_*;(_*).*
$.1
```
[Try it online!](https://tio.run/##FYqhDoAwDAV9v6Ni3ZYlHQmm/8IbAoFBEBz8e@nMibu7j@e8dvdWiDPMYPSODQnZZAJFiBXcK3cqI1VkQQptUUW@SrywRtss7ulaJm7qrusP "Retina 0.8.2 – Try It Online") Explanation:
```
.+
$*_;;_;
```
Initialise the work area with `n`, `i=0`, and `T=[1]` (note that the list indices are reversed, so that the first element of `T` is `T[i]` and the last is `T[0]`) converted to unary.
```
{`
```
Loop `n` times (actually until the buffer stops changing, but see below).
```
^_(_*;)(_*;_+)
$1_$2,$2
```
Decrement `n`, increment `i`, and make extra copies of `i` and `T[i]`.
```
+`
```
Repeat `i` times.
```
(,_*)_(;_+;(_*))|,
$3$1$2
```
Decrement the copy of `i` and add `T[i-1]` to the copy of `T[i]`, stopping when the copy reaches zero by deleting the `,` entirely, causing the repeat to terminate. The result is therefore `T[i+1]=T[i]+iT[i-1]`.
```
^;_*;(_*).*
$.1
```
When `n` is zero, replace the work area with `T[i]` converted to decimal. This causes the loop to terminate as the stages can no longer match.
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~28~~ 26 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
_pZÌ+(ZÊÉ *ZgJÑ}g´U1õ ï)gJ
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=X3BazCsoWsrJICpaZ0rRfWe0VTH1IO8pZ0o&input=WzAsMTAsMTYsMjJdCi1t)
```
pZÌ+(ZÊÉ *ZgJÑ   make sequence with next element from previous sequence
_    ...  }g´U    repeat input -1 times 
  1õ ï)          starting with [[1,1]]
       gJ        implicit output last element of resulting sequence
```
[Answer]
# [GolfScript](http://www.golfscript.com/golfscript/), 16 bytes
This is inspired by the Fibonacci GolfScript program.
```
~,1.@{)*1$+\}/\;
```
[Try it online!](https://tio.run/##S8/PSStOLsosKPn/v07HUM@hWlPLUEU7plY/xvr/f7P/AA "GolfScript – Try It Online")
## Explanation
```
~,               # Generate exclusive range from input to 0
  1.             # Make 2 copies of 1
    @            # Make the each target on the top
     {      }/   # Foreach over the range
      )          # Increment the current item
       *         # Multiply top by the current item
        1$+      # And add by the second-to-top
           \     # Swap items
              \; # Swap & discard the bottom item
```
[Answer]
# [Elm](https://elm-lang.org/), 45 bytes
```
f n = if n<2 then 1 else (n-1)*f(n-2)+f(n-1)
```
[Try it online!](https://ellie-app.com/7Q49bz3NyrPa1)
Implementation of the recursive function.
[Answer]
# k4, 53 bytes
```
{+/{*/[1+!x]*%*/[y#2]**/*/'1+(!x-2*y;!y)}[x]'!1+_x%2}
   {                                    }[x]'!1+_x%2 /pass inner lambda 2 args - x and each (') enumerate (!) 1+floor float-div 2
                             (!x-2*y;!y)             /enumerate
                           1+                        /add 1 to both list items
                        */'                          /multiply over each - this gives both denominator factorials
                      */                             /multiply them
              */[y#2]                                /make list of 2s of y-length and multiply over - gives y^2
                     *                               /multiply left and right args
             %                                       /reciprocal
    */[1+!x]                                         /x factorial
 +/                                                  /sum
```
examples:
```
  {+/{*/[1+!x]*%*/*/[y#2],*/'1+(!x-2*y;!y)}[x]'!1+_x%2}'[0 3 10 14]
1 4 9496 2390480f
```
[Answer]
# [K (ngn/k)](https://bitbucket.org/ngn/k), 27 bytes
```
{*|x{x,+/(2#|x)*1,#2_x}/!2}
```
[Try it online!](https://tio.run/##y9bNS8/7/z/NqlqrpqK6QkdbX8NIuaZCU8tQR9kovqJWX9Go9n@auoGCIRCZKRgZ/QcA "K (ngn/k) – Try It Online")
* `x{...}/!2` setup a do-reduction with `x` (the input) as the number of iterations to run, seeded with `0 1` (the first two terms of the sequence)
* `1,#2_x` build list containing how to multiply the previous values (i.e. `T(n-1)` by 1, and `T(n-2)` by n-1). Note that this infers the value of `n` from the length of the sequence so far.
* `(2#|x)*` get the last two values of the reversed sequence (i.e. `(x[n-1];x[n-2])`)
* `x,+/` take their sum, and append to the sequence
* `*|` return the last value of the generated sequence
[Answer]
# [Husk](https://github.com/barbuz/Husk), 7 bytes
```
#S=ηÖPḣ
```
[Try it online!](https://tio.run/##yygtzv7/XznY9tz2w9MCHu5Y/P//f3MA "Husk – Try It Online") or [Verify first 10 values](https://tio.run/##ARwA4/9odXNr/23igoHFgDn/4bmBUz3Ot8OWUOG4o/// "Husk – Try It Online")
Same idea as the Jelly answer, and equally as slow.
0-indexed.
## Explanation
```
#S=ηÖPḣ
      ḣ range 1..n
     P  permutations
#       number of arrays which satisfy:
 S      self
  =     equals
   η    indices of
    Ö   ordered elements?
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 7 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
öƒ◙─v◙6
```
[Run and debug it](https://staxlang.xyz/#p=949f0ac4760a36&i=0%0A1%0A2%0A3%0A4%0A5&m=2)
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 37 bytes
```
{⍵<2:1⋄+/(2⍵-1)×∇¨⍵-⍳2}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///v/pR71YbIyvDR90t2voaRkCerqHm4emPOtoPrQBxHvVuNqr9n/aobcKj3r5HXc2Petc86t1yaL3xo7aJj/qmBgc5A8kQD89gsEk6j3pXpYE11hoA2ZsNDQA "APL (Dyalog Unicode) – Try It Online")
-1 byte from Adám.
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~16~~ ~~12~~ 11 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
1-indexed
```
È+T°*ZÔÅÎ}g
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=yCtUsCpa1MXOfWc&input=MTE)
]