# Introduction

The telephone numbers 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 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 and OEIS 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 rules apply
• No standard loopholes
• This is so shortest code in bytes wins

# Python, 33 bytes

f=lambda n:n<2or~-n*f(n-2)+f(n-1)


Try it online!

Uses the recursive formula.

# Oasis, 76 5 bytes

àn*+1


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

• 5 bytes in what charset? in UTF-8 the à character is 2 bytes, so it's 6 bytes in UTF-8. - is it Windows-1252 perhaps? Jan 23 '20 at 15:23
• @hanshenrik 5 bytes in Oasis' charset, which is certainly not UTF-8. I'm not sure what exactly that charset is, but I don't see why that would matter. You can see all available characters here, maybe you can guess the charset from that. Jan 23 '20 at 17:11
• can you provide a base64 or hex encoded copy of the source code? Jan 23 '20 at 17:21
• @hanshenrik gosh, I'd have to actually download Oasis for that. I only ever used it through TIO, and TIO doesn't provide that functionality. But TIO does tell you the byte count, and that's what matters for code golf, right? Jan 23 '20 at 17:24
• well just to be sure i checked the source code (specifically line 620), it's Windows-1252 indeed, which makes it 5 bytes. and hex-encoded it's e06e2a2b31 Jan 23 '20 at 17:34

# cQuents, 10 bytes

=1:Z+Y($-2  1-indexed. 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)


# Jelly, 6 bytes

Œ!ỤƑ€S


A monadic Link accepting a non-negative integer which yields a positive integer.

Try it online! Or see the first 10 (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

• I tried doing something like this in 05AB1E, but it ended up longer than the recurrence relation. Really clever use of "grade"! Jan 21 '20 at 13:09

# TI-BASIC, 28 22 bytes

∑((Ans nCr (2K))(2K)!/(2^KK!),K,0,int(.5Ans


Input is n in Ans.
Output is the nth telephone number.

I was going to use the first formula mentioned in the challenge, but testing it resulted in ERROR: OVERFLOWs even on smaller numbers because TI-BASIC handles n!! as two successive factorials instead of a 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.

# JavaScript (ES6), 25 bytes

0-indexed. Uses the recurrence relation.

f=n=>n<2||f(--n)+n*f(n-1)


Try it online!

# 05AB1E, 12 8 bytes

-4 bytes by porting Stephen's cQuent answer

1λèsN<*+


Try it online!

f n|n<2=1|m<-n-1=f m+m*f(n-2)


Try it online!

Implements the recursive formula.

• Nice use of pattern guards! Jan 20 '20 at 22:13

# C (gcc), 40 bytes

long f(long n){n=n<2?1:f(--n)+n*f(n-1);}


Try it online!

# Python 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!

Uses 0 based indexing and implements the recursive formula.

# Perl 6, 26 bytes

{{(1,1,++$×*+*...*)[$_]}}


Try it online!

• Why does this require two sets of {}? The behavior of {(1,1,++$×*+*...*)[$_]} is different and I don't understand why. Jan 26 '20 at 20:38
• @SirBogman With out the double braces, the state variable $ isn't reset across multiple runs of the function. The inner braces create a separate lexical scope for $ causing it to be reset whenever the function is run. Jan 27 '20 at 13:13

# J, 25 bytes

($:+]*$:@<:)@<:1:@.(<&2)


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... • Hint: generating function Jan 21 '20 at 12:29 • I actually tried this approach with the t. adverb but got a domain error on the Wikipedia generating function Jan 21 '20 at 12:47 • Yeah I found J being restrictive too, but messing around gave (^*^@(]*-:))t.*! which works tio.run/##y/r/P83WSiNOK85BI1ZL10pTs0RPSxEoqJCpZ2RQAQA Jan 21 '20 at 12:50 • Interesting... ty! Feel free to post as separate answer, otherwise Ill update mine in a few hours when Im back on my laptop Jan 21 '20 at 12:54 • I'll leave it to you. And I forgot, ]*-: can obviously become *-: Jan 21 '20 at 13:05 # PHP, 48 bytes function f($n){return$n<2?1:f(--$n)+$n*f($n-1);}


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!

# Mathematica 46 42 bytes

f=2^(#/2)HypergeometricU[-#/2,.5,-.5]I^-#&


Try it online!

Thanks to mabel for helping me shave 4 bytes by using what I think is an anonymous function.

• hi! you may want to add a link to Try It Online so other people can test out your code. (I've also saved a few trivial bytes) Jan 22 '20 at 21:17
• @mabel Ty for the suggestion and the 4 bytes off ;)
– RGS
Jan 23 '20 at 0:43
• no problem @RGS Jan 23 '20 at 7:21

# Red, 53 bytes

f: func[n][either 1 > n: n - 1[1][n *(f n - 1)+ f n]]


Try it online!

• @RGS Oh, I totally forgot that the function is recusrsive! You're right, I need to include f:  to the bytecount. Thanks! Jan 23 '20 at 8:41
• don't worry ^^ I'm just vouching for clarity :)
– RGS
Jan 23 '20 at 8:47

# Charcoal, 20 bytes

⊞υ¹ＦＮ⊞υ⁺§υι×ι§υ⊖ιＩ⊟υ


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).

# Keg, 21 bytes

:1≤[_1|;:@Tƒ^:;@Tƒ*+]


Try it online!

Simply implements the formula in a recursive manner. The footer is mainly for testing purposes

# Retina 0.8.2, 80 bytes

.+
$*_;;_; {^_(_*;)(_*;_+)$1_$2,$2
+(,_*)_(;_+;(_*))|,
$3$1$2 ^;_*;(_*).*$.1


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.

# Japt, 28 26 bytes

_pZÌ+(ZÊÉ *ZgJÑ}g´U1õ ï)gJ


Try it

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


# GolfScript, 16 bytes

This is inspired by the Fibonacci GolfScript program.

~,1.@{)*1$+\}/\;  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


# Elm, 45 bytes

f n = if n<2 then 1 else (n-1)*f(n-2)+f(n-1)


Try it online!

Implementation of the recursive function.

# 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


# K (ngn/k), 27 bytes

{*|x{x,+/(2#|x)*1,#2_x}/!2}


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

# Husk, 7 bytes

#S=ηÖPḣ


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?


# Stax, 7 bytes

öƒ◙─v◙6


Run and debug it

# APL (Dyalog Unicode), 37 bytes

{⍵<2:1⋄+/(2⍵-1)×∇¨⍵-⍳2}


Try it online!

• 1, can be 2
È+T°*ZÔÅÎ}g
`