<h3>subfactorial</h3>
<h5>sympy.functions.combinatorial.factorials.subfactorial</h5>
<a href="https://en.wikipedia.org/wiki/Derangement#Counting_derangements">subfactorial</a>
$$!n=n!\sum_{i=0}^n\frac{(-1)^i}{i!},\quad n\geq 0$$
$$!n=n!-\sum_{i=1}^n{n\choose i}\cdot{!(n-i)},\quad\ n \ge 1$$
<a href="https://mathworld.wolfram.com/Subfactorial.html">recurrence relation</a>
$$!n=(n-1)\left(!(n-2)+!(n-1)\right)$$


```python
from typing import TypeVar

import treefactorial

Numeric = TypeVar('Numeric', int, float, complex)
EMPTY_SUM = 0
MINUS_ONE = -1

factorial = treefactorial.factorial
#binom = treefactorial.binom

def binom(n: int, k: int) -> int:
    """Pure Python binomial coefficient, using treefactorial."""
    return int(factorial(n)/(factorial(k)*factorial(n - k)))


def round(number: Numeric) -> int:
    """Round a floating point number to nearest integer."""
    if number < 0:
        return int(number - 0.5)
    else:
        return int(number + 0.5)


def _subfactorial1(n: int) -> int:
    """Pure Python subfactorial.
    Also called derangement number or de Montmort number or rencontres numbers.
    Published by Remond de Montmort in 1713.
    """
    sum = EMPTY_SUM
    for i in range(n + 1):
        sum += MINUS_ONE**i/factorial(i)
    return round(factorial(n)*sum)


def _subfactorial(n: int) -> int:
    """Pure Python subfactorial.
    Also called derangement number or de Montmort number or rencontres numbers.
    Published by Remond de Montmort in 1713.
    """
    if not n:
        #return round(factorial(n)*MINUS_ONE**0/factorial(0)) #cutdown version of _subfactorial for n=0
        return _subfactorial1(n)
    sum = EMPTY_SUM
    for i in range(1, n + 1):
        sum += binom(n, i)*_subfactorial(n - i)
    return factorial(n) - sum


def subfactorial(number: int) -> int:
    """Pure Python subfactorial.
    Also called derangement number or de Montmort number or rencontres numbers.
    Published by Remond de Montmort in 1713.
    Algorithm using recurrence by Euler.
    """
    result = list()
    for n in range(11):
        result += [_subfactorial(n)]
    if number < 11:
        return result[number]
    for n in range(11, number + 1):
        result += [(n - 1)*(result[n - 2] + result[n - 1])]
    return result[number]
```


```python
for n in range(52):
    print(n, subfactorial(n))
```

    0 1
    1 0
    2 1
    3 2
    4 9
    5 44
    6 265
    7 1854
    8 14833
    9 133496
    10 1334961
    11 14684570
    12 176214841
    13 2290792932
    14 32071101049
    15 481066515734
    16 7697064251745
    17 130850092279664
    18 2355301661033953
    19 44750731559645106
    20 895014631192902121
    21 18795307255050944540
    22 413496759611120779881
    23 9510425471055777937262
    24 228250211305338670494289
    25 5706255282633466762357224
    26 148362637348470135821287825
    27 4005791208408693667174771274
    28 112162153835443422680893595673
    29 3252702461227859257745914274516
    30 97581073836835777732377428235481
    31 3025013288941909109703700275299910
    32 96800425246141091510518408809597121
    33 3194414033122656019847107490716704992
    34 108610077126170304674801654684367969729
    35 3801352699415960663618057913952878940514
    36 136848697178974583890250084902303641858505
    37 5063401795622059603939253141385234748764684
    38 192409268233638264949691619372638920453057993
    39 7503961461111892333037973155532917897669261726
    40 300158458444475693321518926221316715906770469041
    41 12306496796223503426182275975073985352177589230680
    42 516872865441387143899655590953107384791458747688561
    43 22225533213979647187685190410983617546032726150608122
    44 977923461415104476258148378083279172025439950626757369
    45 44006555763679701431616677013747562741144797778204081604
    46 2024301565129266265854367142632387886092660697797387753785
    47 95142173561075514495155255703722230646355052796477224427894
    48 4566824330931624695767452273778667071025042534230906772538913
    49 223774392215649610092605161415154686480227084177314431854406736
    50 11188719610782480504630258070757734324011354208865721592720336801
    51 570624700149906505736143161608644450524579064652151801228737176850



```python
import sympy
for n in range(51):
    print(n, subfactorial(n), sympy.functions.combinatorial.factorials.subfactorial(n))
```

    0 1 1
    1 0 0
    2 1 1
    3 2 2
    4 9 9
    5 44 44
    6 265 265
    7 1854 1854
    8 14833 14833
    9 133496 133496
    10 1334961 1334961
    11 14684570 14684570
    12 176214841 176214841
    13 2290792932 2290792932
    14 32071101049 32071101049
    15 481066515734 481066515734
    16 7697064251745 7697064251745
    17 130850092279664 130850092279664
    18 2355301661033953 2355301661033953
    19 44750731559645106 44750731559645106
    20 895014631192902121 895014631192902121
    21 18795307255050944540 18795307255050944540
    22 413496759611120779881 413496759611120779881
    23 9510425471055777937262 9510425471055777937262
    24 228250211305338670494289 228250211305338670494289
    25 5706255282633466762357224 5706255282633466762357224
    26 148362637348470135821287825 148362637348470135821287825
    27 4005791208408693667174771274 4005791208408693667174771274
    28 112162153835443422680893595673 112162153835443422680893595673
    29 3252702461227859257745914274516 3252702461227859257745914274516
    30 97581073836835777732377428235481 97581073836835777732377428235481
    31 3025013288941909109703700275299910 3025013288941909109703700275299910
    32 96800425246141091510518408809597121 96800425246141091510518408809597121
    33 3194414033122656019847107490716704992 3194414033122656019847107490716704992
    34 108610077126170304674801654684367969729 108610077126170304674801654684367969729
    35 3801352699415960663618057913952878940514 3801352699415960663618057913952878940514
    36 136848697178974583890250084902303641858505 136848697178974583890250084902303641858505
    37 5063401795622059603939253141385234748764684 5063401795622059603939253141385234748764684
    38 192409268233638264949691619372638920453057993 192409268233638264949691619372638920453057993
    39 7503961461111892333037973155532917897669261726 7503961461111892333037973155532917897669261726
    40 300158458444475693321518926221316715906770469041 300158458444475693321518926221316715906770469041
    41 12306496796223503426182275975073985352177589230680 12306496796223503426182275975073985352177589230680
    42 516872865441387143899655590953107384791458747688561 516872865441387143899655590953107384791458747688561
    43 22225533213979647187685190410983617546032726150608122 22225533213979647187685190410983617546032726150608122
    44 977923461415104476258148378083279172025439950626757369 977923461415104476258148378083279172025439950626757369
    45 44006555763679701431616677013747562741144797778204081604 44006555763679701431616677013747562741144797778204081604
    46 2024301565129266265854367142632387886092660697797387753785 2024301565129266265854367142632387886092660697797387753785
    47 95142173561075514495155255703722230646355052796477224427894 95142173561075514495155255703722230646355052796477224427894
    48 4566824330931624695767452273778667071025042534230906772538913 4566824330931624695767452273778667071025042534230906772538913
    49 223774392215649610092605161415154686480227084177314431854406736 223774392215649610092605161415154686480227084177314431854406736
    50 11188719610782480504630258070757734324011354208865721592720336801 11188719610782480504630258070757734324011354208865721592720336801



```python

```

67d4152633674924921fc071b9b276c7dc6fe378
ipynb
Jupyter Notebook
subfactorial.ipynb
ectomancer/pure_python
9a9edd3e448ea3b90b15d5f980a8c9f40f4b3e98
MIT
subfactorial.ipynb
ectomancer/pure_python
9a9edd3e448ea3b90b15d5f980a8c9f40f4b3e98
MIT
subfactorial.ipynb
ectomancer/pure_python
9a9edd3e448ea3b90b15d5f980a8c9f40f4b3e98
MIT
Qwen/Qwen-72B
1. YES
2. YES