[Question]
  [
The **subfactorial** or **rencontres numbers** ([A000166](https://oeis.org/A000166)) are a sequence of numbers similar to the factorial numbers which show up in the combinatorics of permutations. In particular the **n**th subfactorial **!n** gives the number of [derangements](https://en.wikipedia.org/wiki/Derangement) of a set of **n** elements. A derangement is a permutation in which no element remains in the same position. The subfactorial can be defined via the following recurrence relation:
```
!n = (n-1) (!(n-1) + !(n-2))
```
In fact, the same recurrence relation holds for the factorial, but for the subfactorial we start from:
```
!0 = 1
!1 = 0
```
(For the factorial we'd have, of course, **1! = 1**.)
Your task is to compute **!n**, given **n**.
## Rules
Like the factorial, the subfactorial grows very quickly. It is fine if your program can only handle inputs **n** such that **!n** can be represented by your language's native number type. However, your *algorithm* must in theory work for arbitrary **n**. That means, you may assume that *integral* results and intermediate value can be represented exactly by your language. Note that this excludes the constant **e** if it is stored or computed with finite precision.
The result needs to be an exact integer (in particular, you cannot approximate the result with scientific notation).
You may write a [program or a function](https://codegolf.meta.stackexchange.com/q/2419) and use any of the [standard methods](https://codegolf.meta.stackexchange.com/q/2447) of receiving input and providing output.
You may use any [programming language](https://codegolf.meta.stackexchange.com/q/2028), but note that [these loopholes](https://codegolf.meta.stackexchange.com/q/1061/) are forbidden by default.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest valid answer ‚Äì measured in *bytes* ‚Äì wins.
## Test Cases
```
n     !n
0     1
1     0
2     1
3     2
4     9
5     44
6     265
10    1334961
12    176214841
13    2290792932
14    32071101049
20    895014631192902121
21    18795307255050944540
100   34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601
```
  
[Answer]
## [Funciton](https://github.com/Timwi/Funciton), 336 bytes
Byte count assumes UTF-16 encoding with BOM.
```
‚îå‚îÄ‚ïñ‚îå‚îÄ‚ïñ  ‚îå‚îÄ‚ïñ 
‚îÇf‚ïü‚î§‚ô≠‚ïü‚îê‚îå‚î§‚ô≠‚ïü‚îê
‚ïò‚ï§‚ïù‚ïò‚ïê‚ïù‚îú‚îò‚ïò‚ïê‚ïù‚îú‚îÄ‚îÄ‚îÄ‚îÄ‚îê
 ‚îÇ‚îå‚îÄ‚ïñ ‚îÇ ‚îå‚îê‚îå‚îò‚ïî‚ïê‚ïó‚ïì‚î¥‚ïñ
 ‚îÇ‚îÇf‚ïü‚îÄ‚î¥‚îê‚îî‚î¥‚îº‚îÄ‚ï¢0‚ïë‚ïëf‚ïë
 ‚îÇ‚ïò‚ï§‚ïù  ‚îÇ  ‚îÇ ‚ïö‚ïê‚ïù‚ïô‚îÄ‚ïú
 ‚îÇ‚îå‚î¥‚ïñ ‚îå‚î¥‚ïñ‚îå‚î¥‚ïñ ‚ïî‚ïê‚ïó
 ‚îÇ‚îÇ+‚ïü‚îê‚îÇ√ó‚ïü‚î§?‚ïü‚îê‚ïë1‚ïë
 ‚îÇ‚ïò‚ï§‚ïù‚îÇ‚ïò‚ï§‚ïù‚ïò‚ï§‚ïù‚îò‚ïö‚ï§‚ïù
 ‚îî‚îÄ‚îò ‚îî‚îÄ‚îò  ‚îî‚îÄ‚îÄ‚îÄ‚îò
```
This defines a function `f` which takes one integer and outputs another integer at a 90 degree turn to the left. It works for arbitrarily large inputs.
[Try it online!](https://tio.run/nexus/funciton#dVIxDsIwDNz7iuwssLDym0osDMADqg5MDC3YNCAQEurKxsjGT/yR4thJk4oi3XBxbN/ZSUewJygITz0xJtKMoMwJ7wQtnZ9CKrmNx4zQEraENyGVI3AlsMNjkaDKWKKMKnxQTe3NZSCVDeGR4MUpvsB7KVzQJYOQt7R5TAlrBqfUmh58GRFQFbx4T3iWqmu08lIrniWh4CaYmIQ9lJ9Gd7PwEaxnP@oDHoNWrDju0kGGsgnrqcJ2wYaiMfw2WBvOY8EwVqvD8Z2Mm/kVuyUVI@C9uqVstmvaHZarre9lk16/uI31Tn7NP7gUkctNeERGa1iX1dlDDPceqjDPMDBiqpt/AQ "Funciton ‚Äì TIO Nexus")
Considering this is Funciton it's even *reasonably* fast (n = 20 takes about 14 seconds on TIO). The main slowdown comes from the double-recursion, as I don't think the Funciton interpreter automatically memoises functions.
Unfortunately, some monospaced fonts don't correctly monospace the `‚ô≠` and/or insert small gaps between the lines. Here's a screenshot of the code from TIO in all its beauty:
[![enter image description here](https://i.stack.imgur.com/25gz6.png)](https://i.stack.imgur.com/25gz6.png)
I think it might be possible to golf this some more, e.g. by changing the condition from `>0` to `<1` and swapping the branches of the conditional, so that I could reuse the number literal, or maybe by using a completely different formula, but I'm quite happy with how compact it is already.
### Explanation
This basically implements the recursion given in the challenge, although it uses the base case **!(-1) = !0 = 1**. **n-1** and **n-2** are computed with the predecessor function `‚ô≠`, and the intermediate result **n-1** is reused in three places. There isn't much more to it, so I'll just quickly go through the control flow:
```
               ‚îÄ‚îê
               ‚ïì‚î¥‚ïñ
               ‚ïëf‚ïë
               ‚ïô‚îÄ‚ïú
```
This is the function header which emits the function's input **n** long the attached line. This immediately reaches T-junction, which simply duplicates the value.
```
        ‚îå‚îê‚îå‚îò‚ïî‚ïê‚ïó
        ‚îî‚î¥‚îº‚îÄ‚ï¢0‚ïë
          ‚îÇ ‚ïö‚ïê‚ïù
```
The `0` box is just a numeric literal. A 4-way junction computes two functions: the path that leads off the bottom computes **0 < n**, which we'll use to determine the base case. The path that goes left separately computes **0 << n** (a left-shift), but we discard this value with the [Starkov construct](http://esolangs.org/wiki/Funciton#The_Starkov_construct).
```
         ‚îå‚î¥‚ïñ ‚ïî‚ïê‚ïó
         ‚î§?‚ïü‚îê‚ïë1‚ïë
         ‚ïò‚ï§‚ïù‚îò‚ïö‚ï§‚ïù
          ‚îî‚îÄ‚îÄ‚îÄ‚îò
```
We lead this into the three-way conditional `?`. If the value is false, we return the constant result `1`. The loose end right of the `?` is the function output. I'm twisting it around by 180 degrees here, so that the relative orientation of input and output of `f` is more convenient in the rest of the program.
If the condition was true, then the other value will be used. Let's look at the path that leads to this branch. (Note that Funciton's evaluation is actually lazy so that this branch will never be evaluated if it's not needed, which makes the recursion possible in the first place.)
```
        ‚îå‚îÄ‚ïñ 
      ‚îê‚îå‚î§‚ô≠‚ïü‚îê
      ‚îú‚îò‚ïò‚ïê‚ïù
      ‚îÇ
     ‚îÄ‚î¥‚îê
```
In the other branch we first compute **n-1** and then split the path twice so we get three copies of the value (one for the coefficient of the recurrence, one for the first subfactorial, the last for **n-2**).
```
‚îå‚îÄ‚ïñ‚îå‚îÄ‚ïñ
‚îÇf‚ïü‚î§‚ô≠‚ïü
‚ïò‚ï§‚ïù‚ïò‚ïê‚ïù
 ‚îÇ‚îå‚îÄ‚ïñ
 ‚îÇ‚îÇf‚ïü
 ‚îÇ‚ïò‚ï§‚ïù
 ‚îÇ‚îå‚î¥‚ïñ
 ‚îÇ‚îÇ+‚ïü
 ‚îÇ‚ïò‚ï§‚ïù
 ‚îî‚îÄ‚îò 
```
Like I said, we decrement one copy again with another `‚ô≠`, then we feed both **n-1** and **n-2** recursively to `f` and finally add the two results together in the `+`.
```
       ‚îê
       ‚îÇ
      ‚îå‚î¥‚ïñ
     ‚îê‚îÇ√ó‚ïü
     ‚îÇ‚ïò‚ï§‚ïù
     ‚îî‚îÄ‚îò
```
All that's left is to multiply **n-1** by **!(n-1) + !(n-2)**.
[Answer]
# [Oasis](https://github.com/Adriandmen/Oasis), 5 bytes
Uses the formula given by Martin. Code:
```
+n<*X
```
Dissected version:
```
+n<*
```
with `a(0) = 1` and `a(1) = 0`.
Explanation, `a(n) =`:
```
+       # Add the previous two terms, a(n - 1) + a(n - 2).
 n<     # Compute n - 1.
   *    # Multiply the top two elements.
```
[Try it online!](https://tio.run/nexus/oasis#@6@dZ6MV8f//f0MDAA "Oasis ‚Äì TIO Nexus")
[Answer]
# [Haskell](https://www.haskell.org/), 25 bytes
```
f 0=1
f n=n*f(n-1)+(-1)^n
```
[Try it online!](https://tio.run/nexus/haskell#@5@mYGBryJWmkGebp5WmkadrqKmtASTi8v7nJmbmKdgqFKUmpvjkKdjZ2SoUFGXmlSjoKaT9NzQAAA "Haskell ‚Äì TIO Nexus") Uses the other recurrence from the [OEIS](https://oeis.org/A000166) page.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 7 bytes
```
R=≈í!·∏Ñƒã0
```
This approach constructs the derangements, so it's rather slow.
[Try it online!](https://tio.run/nexus/jelly#ARsA5P//Uj3FkiHhuITEizD/MHI4wrXFvMOH4oKsR/8 "Jelly ‚Äì TIO Nexus")
### How it works
```
R=≈í!·∏Ñƒã0  Main link. Argument: n
R        Range; yield [1, ..., n].
  ≈í!     Yield all permutations of [1, ..., n].
 =       Perform elementwise comparison of [1, ..., n] and each permutation.
    ·∏Ñ    Unbinary; convert each result from base 2 to integer. This yields 0 for
         derangements, a positive value otherwise.
     ƒã0  Count the number of zeroes.
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog) (2), 11 bytes
```
‚ü¶‚ÇÅ{p:?\‚â†·µê}·∂ú
```
[Try it online!](https://tio.run/nexus/brachylog2#ARsA5P//4p@m4oKBe3A6P1ziiaDhtZB94bac//82/1o "Brachylog ‚Äì TIO Nexus")
## Explanation
This is basically just a direct translation of the spec from English to Brachylog (and thus has the advantage that it could easily be modified to handle small changes to the specification, such as finding the number of derangements of a specific list).
```
‚ü¶‚ÇÅ{p:?\‚â†·µê}·∂ú
‚ü¶‚ÇÅ           Start with a list of {the input} distinct elements
  {      }·∂ú  Then count the number of ways to
   p         permute that list
      \      such that taking corresponding elements
    :?       in {the permutation} and the list of distinct elements
       ‚â†     gives different elements
        ·µê    at every position
```
[Answer]
# Languages with built-in solutions
Following [xnor's suggestion](https://codegolf.meta.stackexchange.com/a/11218/8478) this is a CW answer into which trivial solutions based on a single built-in to compute the subfactorial or generate all derangements should be edited.
## Mathematica, 12 bytes
```
Subfactorial
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~35~~ 32 bytes
```
f=lambda n:n<1or(-1)**n+n*f(n-1)
```
This uses the recurrence relation **!n = n !(n-1) + (-1)n** from [@Laikoni's Haskell answer](https://codegolf.stackexchange.com/a/113942/12012), with base case **!0 = 1**.
[Try it online!](https://tio.run/nexus/python3#FczBCsIwEIThs32KuYTu1gSaVRCK@iKlh5QYKditBM@@el0PH8Nc/r3cXmmdc4IOeo1b/QbtqJCGyMf/CPNetgrFohi7mvT5oAt7xN6IOZmzh9iXOA3N4V0X/VDrJCPc4aTPLRxIPSzI1vsB "Python 3 ‚Äì TIO Nexus")
[Answer]
# [M](https://github.com/DennisMitchell/m), 9 bytes
```
o2!√∑√òe+.·∏û
```
As you can see by removing the `·∏û`, **M** uses symbolic math, so there will be no precision issues.
[Try it online!](https://tio.run/nexus/m#@59vpHh4@@EZqdp6D3fM@390z@H2R01rsoD4UeO2rEeN2///N9BRMNRRMNJRMNZRMNFRMNVRMAOKgESBYoZAQUOgqBGQb2QIEjcAAA "M ‚Äì TIO Nexus") Not the shortest solution that has been posted, but *fast*.
### How it works
```
o2!√∑√òe+.·∏û  Main link. Argument: n
o2         Replace input 0 with 2, as the following formula fails for 0.
  !        Compute the factorial of n or 2.
   √∑√òe     Divide the result by e, Euler's natural number.
      +.   Add 1/2 to the result.
        ·∏û  Floor; round down to the nearest integer.
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), ~~9~~ 8 bytes
```
:tY@-!As
```
Similarly to [@Dennis' Jelly answer](https://codegolf.stackexchange.com/a/113937/36398), this actually builds the permutations and counts how many of them are derangements; so it is slow.
[Try it online!](https://tio.run/nexus/matl#@29VEumgq@hY/P@/oQEA "MATL ‚Äì TIO Nexus")
```
:     % Input n implicitly: Push [1 2 ... n]
t     % Duplicate 
Y@    % Matrix of all permutations, each on a row
-     % Element-wise subtract. A zero in a row means that row is not a derangement
!     % Transpose
A     % True for columns that don't contain zeros
s     % Sum. Implicitly display
```
[Answer]
# [Mathics](http://mathics.github.io/), 21 bytes
```
Round@If[#>0,#!/E,1]&
```
I am *very* new to this and have no idea what I'm doing...
[Try it online!](https://tio.run/nexus/mathics#S1Ow/R@UX5qX4uCZFq1sZ6CjrKjvqmMYq/Y/oCgzr8ShOs3BQCfNwRCIjYDYGMQ2qP0PAA "Mathics ‚Äì TIO Nexus")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 8 bytes
```
√é∆íN*¬ÆNm+
```
[Try it online!](https://tio.run/nexus/05ab1e#@3@479gkP61D6/xytf//NzQwAAA "05AB1E ‚Äì TIO Nexus")
**Explanation**
```
√é         # initialize stack with 0 and input
 ∆í        # for N in range [0 ... input]:
  N*      # multiply top of stack with N
    ¬ÆNm   # push (-1)^N
       +  # add
```
[Answer]
# Ruby, 27 bytes
```
f=->n{n<1?1:n*f[n-1]+~0**n}
```
`~0**n` is shorter than `(-1)**n`!
[Answer]
## CJam (10 bytes)
```
1qi{~*)}/z
```
[Online demo](http://cjam.aditsu.net/#code=1qi%7B~*)%7D%2Fz&input=5).
This uses the recurrence `!n = n !(n-1) + (-1)^n`, which I derived from `n! / e` and then discovered was already in OEIS.
### Dissection
The loop calculates `(-1)^n !n`, so we need to take the absolute value at the end:
```
1     e# Push !0 to the stack
qi{   e# Read an integer n and loop from 0 to n-1
  ~   e#   Bitwise not takes i to -(i+1), so we can effectively loop from 1 to n
  *   e#   Multiply
  )   e#   Increment
}/
z     e# Take the absolute value
```
[Answer]
# [Quipu](https://github.com/cgccuser/quipu), 73 bytes
```
\/1&1&2&1&
1&++++^^[]
++2&0&--1&
2&[][]1&++
??**%%??/\
  3&4&
  []==
  --
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m720sDSzoHTBgqWlJWm6Fjc9Y_QN1QzVjICYy1BNGwji4qJjubS1jdQM1HR1gaJGatGx0bEgOS57ey0tVVV7e_0YLgUFYzUTNSAVHWtrC6R0dSEGQs1dsMjQAMICAA)
Based on [Aaroneous Miller's factorial answer](https://codegolf.stackexchange.com/a/234986/9288).
Equivalent pseudocode:
```
  a = [0, 0, 0, 0, 0]    // implicitly
0:
  a[0] = input + 1
  goto 2
1:
  a[1] = (a[1] + 1) * a[2] - a[3]
2:
  a[2] = (a[2] + 1) % a[0]
  if a[2] == 0 goto 4
3:
  a[3] = 2 - a[3]
  goto 1
4:
  a[4] = a[1] + 1
  print a[4]
```
[Answer]
# MATLAB, 33 bytes
```
@(n)(-1)^n*hypergeom([1 -n],[],1)
```
Anonympus function that uses the formula in Section 3 of [*Derangements and applications*](https://eudml.org/doc/51444) by Mehdi Hassani.
Example use:
```
>> @(n)(-1)^n*hypergeom([1 -n],[],1)
ans = 
    @(n)(-1)^n*hypergeom([1,-n],[],1)
>> ans(6)
ans =
   265
```
[Answer]
## JavaScript (ES6), 26 bytes
```
f=n=>!n||n*f(n-1)-(~n%2|1)
```
Uses the recurrence relation from @Laikoni's answer. In ES7 you can save a byte by using `+(-1)**n` instead of `-(~n%2|1)`.
[Answer]
### PostScript, ~~81~~ ~~76~~ 69 bytes
Here are implementations of both formulae.
n\*f(n-1)+(-1)^n
~~/f{dup 0 eq{pop 1}{dup dup 1 sub f mul exch 2 mod 2 mul 1 sub sub}ifelse}def~~
```
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def
```
That version outputs a float. If it's necessary to output an integer:
```
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp cvi add}ifelse}def
```
which weighs in at 73 bytes.
The other formula is a little longer: 81 bytes.
(n-1)\*(f(n-1)+f(n-2))
```
/f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def
```
These functions get their argument from the stack, and leave the result on the stack.
You can test the functions, either in a file or at an interactive PostScript prompt (eg GhostScript) with
```
0 1 12{/i exch def [i i f] ==}for
```
**output**
```
[0 1]
[1 0.0]
[2 1.0]
[3 2.0]
[4 9.0]
[5 44.0]
[6 265.0]
[7 1854.0]
[8 14833.0]
[9 133496.0]
[10 1334961.0]
[11 14684570.0]
[12 176214848.0]
```
Here's a complete PostScript file which renders the output to the screen or a printer page. (Comments in PostScript start with `%`).
```
%!PS-Adobe-3.0
% (n-1)*(f(n-1)+f(n-2))
% /f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def
% n*f(n-1)+(-1)^n
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def
% 0 1 12{/i exch def [i i f] ==}for
/FS 16 def              %font size
/LM 5 def               %left margin
/numst 12 string def    %numeric string buffer
/Newline{currentpoint exch pop FS sub LM exch moveto}def
/Courier findfont FS scalefont setfont
LM 700 moveto
(Subfactorials) Newline
0 1 12{
    dup numst cvs show (: ) show f numst cvs show Newline
}for
showpage
quit
```
[Answer]
# [Raku](http://raku.org/), 22 bytes
```
1,{++$*$_+($*=-1)}...*
```
[Try it online!](https://tio.run/##K0gtyjH7r1ecWKmQll@koPHfUKdaW1tFSyVeW0NFy1bXULNWT09P679mdJyRYaxVwX8A "Perl 6 ‚Äì Try It Online")
This is an expression for the infinite sequence of subfactorials.
[Answer]
# [Python 3](https://docs.python.org/3/), 27 bytes
```
f=lambda n:n<1or f(n-1)*n^1
```
[Try it online!](https://tio.run/##XYw9DoAgGEN3T8HI508isqlcxQQjoIlWgyyeHkU3p5f0tT2uMO@QMVq16m2cNEOLXuyeWY5KUI5BRPdzn@HuZZHQEGX2GYEtYF7DGS5ravV5Gh/SFSn19Kg7/ILAUaaI4g0 "Python 3 ‚Äì Try It Online")
Based on [@Laikoni's formula](https://codegolf.stackexchange.com/a/113942/107561) and the observation that *n* and !*n* always have opposite parity.
Broken down:
n odd -> n x !(n-1) also odd -> adding (-1)^n=-1 is the same as unsetting the lowest bit
n even -> n x !(n-1) also even -> adding (-1)^n=1 is the same as setting the lowest bit
therefore flipping the lowest bit works in either case
[Answer]
# PHP, 69 Bytes
```
function f($i){return$i>1?$i*f($i-1)+(-1)**$i:1-$i;}echo f($argv[1]);
```
use this way `a(n) = n*a(n-1) + (-1)^n`
[Answer]
# PHP, 50 44
```
for(;$i++<$argn;)$n=++$n*$i-$i%2*2;echo$n+1;
```
Run with `echo <n> | php -nR '<code>`
The beauty of `a(n) = n*a(n-1) + (-1)^n` is that it depends only on the previous value. This allows it to be implemented iteratively instead of recursively. This saves a long *function* declarition.
*-6 bytes* by @Titus. Thanks !
[Answer]
# [Alice](https://github.com/m-ender/alice), ~~20~~ 18 bytes
```
1/o
k\i@/&wq*eqE+]
```
[Try it online!](https://tio.run/##S8zJTE79/99QP58rOybTQV@tvFArtdBVOxYoZmAAAA "Alice ‚Äì Try It Online")
### Explanation
This uses the recursion from [Laikoni's answer](https://codegolf.stackexchange.com/a/113942/8478), **!n = n !(n-1) + (-1)n**. Similar to the Funciton answer, I'm using the base case **!(-1) = 1**. We put that **1** on the stack with `1.`. Then this...
```
.../o
...\i@/...
```
... is just the usual decimal I/O framework. The main code is actually
```
&wq*eqE+]k
```
Broken down:
```
&w    Push the current IP address N times to the return address stack, which
      effectively begins a loop which will be executed N+1 times.
  q     Push the position of the tape head, which we're abusing as the
        iterator variable n.
  *     Multiply !(n-1) by n.
  e     Push -1.
  q     Retrieve n again.
  E     Raise -1 to the nth power.
  +     Add it to n*!(n-1).
  ]     Move the tape head to the right.
k     Jump back to the w, as long as there is still a copy of the return
      address on the return address stack. Otherwise, do nothing and exit
      the loop.
```
[Answer]
# [Julia 1.0](http://julialang.org/), 21 bytes
```
!n=n<1||n*!~-n+(-1)^n
```
[Try it online!](https://tio.run/##yyrNyUw0rPj/XzHPNs/GsKYmT0uxTjdPW0PXUDMu739afpFCpkJmnkJSZrqGgaaVoYEBlwIQFBRl5pXk5GkoKapkKtgqKOkoKGZqcqXmpfwHAA "Julia 1.0 ‚Äì Try It Online")
with the following formula from the [OEIS page](https://oeis.org/A000166):
$$ a(0)=1,\ a(n) = n\*a(n-1) + (-1)^n $$
[Answer]
# TI-Basic, ~~12~~ 19 bytes
```
Ans!‚àë((-1)^K/K!,K,0,Ans
```
with the following formula from the [OEIS page](https://oeis.org/A000166):
$$ a(n) = n!\*\sum\_{k=0..n}(-1)^k/k! $$
![screenshot of demo on calculator](https://i.stack.imgur.com/xIvxgm.jpg)
### previous answer (12 bytes)
```
round(Ans!/ùìÆ,0)+not(Ans
```
this is invalid because `ùìÆ` (euler number) is stored with limited precision, which is explicitly forbiden by the challenge
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 8 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
0LŒª√®+N<*
```
I know there is already [a great 8 bytes 05AB1E answer](https://codegolf.stackexchange.com/a/113955/52210), but this uses a completely different approach.
[Try it online](https://tio.run/##yy9OTMpM/f/fwOfc7sMrtP1stP7/NwMA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeV/A59zuw@v0Paz0fpfq/M/2kDHUMdIx1jHRMdUx0zHEMg10jE01jE00TEy0DEyBIoYxAIA).
**Explanation:**
```
  Œª       # Start a recursive environment,
   √®      # to output the (implicit) input'th value
0L        # Starting with a(0)=1 and a(1)=0
          # Where every following a(n) is calculated as:
    +     #  Add two values together
          #  (since + requires 2 arguments, it implicitly uses a(n-2) and a(n-1))
     N<*  #  Multiplied by n-1
          # (after which the result of a(input) is output implicitly)
```
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 26 bytes
```
n->n!*sum(k=0,n,(-1)^k/k!)
```
[Try it online!](https://tio.run/##K0gsytRNL/ifpmD7P0/XLk9Rq7g0VyPb1kAnT0dD11AzLls/W1Hzf1p@kUaegq2CgY6CERAXFGXmlQAFlBR07YBEmkaepqbmfwA "Pari/GP ‚Äì Try It Online")
---
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 28 bytes
```
f(n)=if(n,n*f(n-1)+(-1)^n,1)
```
[Try it online!](https://tio.run/##K0gsytRNL/j/P00jT9M2E0jq5GkBSV1DTW0NIBGXp2Oo@T8tv0gjT8FWwUBHwQiIC4oy80qAAkoKunZAAqRVU/M/AA "Pari/GP ‚Äì Try It Online")
---
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 15 bytes (invalid because of finite precision)
```
n->n!\/exp(!!n)
```
[Try it online!](https://tio.run/##K0gsytRNL/ifpmD7P0/XLk8xRj@1okBDUTFP839afpFGnoKtgoGOghEQFxRl5pUABZQUdO2ARJpGnqam5n8A "Pari/GP ‚Äì Try It Online")
[Answer]
## Mathematica, 40 bytes
```
¬±0=1;¬±1=0;¬±n_:=(n-1)(¬±(n-1)+¬±(n-2))
```
Which comes in at 31 bytes under the default ISO 8859-1 encoding.
[Answer]
# C, 34 bytes
```
a(n){return n?n*a(n-1)-n%2*2+1:1;}
```
Explanation:
```
a(n){                            } define a function called a of n
     return                     ;  make the function evaluate to...
            n?                :1   set the base case of 1 when n is 0
              n*a(n-1)             first half of the formula on the page
                      -n%2*2+1     (-1)**n
```
[Answer]
# R, 47 bytes
```
n=scan();`if`(!n,1,floor(gamma(n+1)/exp(1)+.5))
```
Uses the same formula as [Mego's answer](https://codegolf.stackexchange.com/a/113975/67312).
Alternate method, 52 bytes using the `PerMallows` library
```
n=scan();`if`(!n,1,PerMallows::count.perms(n,n,'h'))
```
[Answer]
# [Actually](https://github.com/Mego/Seriously), 18 bytes
```
;!@ur‚å†;!@0D‚Åø/‚å°MŒ£*‚âà
```
[Try it online!](https://tio.run/nexus/actually#@2@t6FBa9KhnAZA2cHnUuF//Uc9C33OLtR51dvz/b2gAAA)
Explanation:
```
;!@ur‚å†;!@0D‚Åø/‚å°MŒ£*‚âà
;                   duplicate input
 !                  n!
  @ur               range(0, n+1) (yields [0, n])
     ‚å†;!@0D‚Åø/‚å°M     for each i in range:
      ;               duplicate i
       !              i!
        @0D‚Åø          (-1)**i
            /         (-1)**i/i!
               Œ£    sum
                *   multiply sum by n!
                 ‚âà  floor into int
```
---
A 12-byte version that would work if Actually had more precision:
```
;!‚ï†@/1¬Ω+L@Y+
```
[Try it online!](https://tio.run/nexus/actually#@2@t@GjqAgd9w0N7tX0cIrX//zc0AgA "Actually ‚Äì TIO Nexus")
Unlike all of the other answers (as of posting), this solution uses neither the recursive formula nor the summation formula. Instead, it uses the following formula:
[![derangement formula](https://i.stack.imgur.com/3VmLu.png)](https://i.stack.imgur.com/3VmLu.png)
This formula is relatively easy to implement in Actually:
```
!‚ï†@/1¬Ω+L
!         n!
 ‚ï†        e
  @/      divide n! by e
    1¬Ω+   add 0.5
       L  floor
```
Now, the only problem is that the formula only holds for positive `n`. If you try to use `n = 0`, the formula incorrectly yields `0`. This is easily fixed, however: by applying boolean negation to the input and adding that to the output of the formula, the correct output is given for all non-negative `n`. Thus, the program with that correction is:
```
;!‚ï†@/1¬Ω+L@Y+
;             duplicate input
 !            n!
  ‚ï†           e
   @/         divide n! by e
     1¬Ω+      add 0.5
        L     floor
         @Y   boolean negate the other copy of the input (1 if n == 0 else 0)
           +  add
```
]