We have an integer array with unique elements and we want to do the permutations that have an element fixed, in other words, these permutations should have a certain element at the same position than the original.

These permutations will be called: **permutations with one fixed point**.

Let's see an example with an array of four elements and we want the permutations that have a coincidence **only at  index 0**, so these permutations are (the permutations between parenthesis):
``` 
arr = [1, 2, 3, 4]
      (1, 3, 4, 2)
      (1, 4, 2, 3)
Two permutations matching with arr only at index 0
``` 

Let's see the permutations of the same array with only one coincidence at index **1**:
``` 
arr = [1, 2, 3, 4]
      (3, 2, 4, 1)
      (4, 2, 1, 3)
Two permutations matching with arr only at index 1
```
Once again, let's see the permutations of the same array with only one coincidence at index **2**:
``` 
arr = [1, 2, 3, 4]
      (2, 4, 3, 1)
      (4, 1, 3, 2)
Two permutations matching with arr only at index 2
```
Finally, let's see the permutations of the same array with only one coincidence at index **3**:
``` 
arr = [1, 2, 3, 4]
      (2, 3, 1, 4)
      (3, 1, 2, 4)
Two permutations matching with arr only at index 3
```
For this array given above (arr) :

- We conclude that we have 8 permutations with one fixed point (two at each index of arr).

- We may do the same development for our array, `arr`, with two fixed points and we will get `6` permutations.

- There are no permutations with coincidences only at three indexes.

- It's good to know that the amount of permutations with no coincidences at all are `9`. See the kata Shuffle It Up!!

In general:

- When the amount of fixed points is equal to the array length, there is only one permutation, the original array.

- When the amount of fixed points surpasses the length of the array, obvously, there are no permutations at all.

Create a function that receives the length of the array and the number of fixed points and may output the total amount of permutations for these constraints.

Features of the random tests:
```
length of the array = l
number of fixed points = k
10 ≤ k ≤ l ≤ 9000
```
See the example tests!
Enjoy it!!

Ruby versin will be released soon.

#Note: This kata was published previously but in a version not well optimized.

Difficulty: introductory

Starter code:

def fixed_points_perms(n,k):
	

Solutions:
def fixed_points_perms(n, k):
    if k > n:
        return 0
    if k == n:
        return 1
    if k == 0:
        subf = lambda n: 1 if n == 0 else n * subf(n - 1) + (-1)**n
        return subf(n)
    return fixed_points_perms(n-1, k-1) * n // k


from functools import lru_cache
from math import factorial as f
@lru_cache(maxsize=None)
def all_permuted(n) : return [1,0][n] if n<2 else (n-1)*(all_permuted(n-1)+all_permuted(n-2))
fixed_points_perms=lambda n,k:all_permuted(n - k)*f(n)//(f(k)*f(n-k)) if n>=k else 0

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
    return (n-1) * (f(n-1) + f(n-2)) if n > 2 else int(n != 1)

def fixed_points_perms(n,k):
    return n * fixed_points_perms(n-1, k-1) // k if k else f(n)

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
    if n <= 2:
        return n - 1
    return (n-1) * (f(n-1) + f(n-2))

def fixed_points_perms(n,k):
    if n == k:
        return 1
    elif k >= n - 1:
        return 0
    elif k == 0:
        return f(n)
    return n * fixed_points_perms(n-1, k-1) // k

subfactorial, factorial = [1, 0], [1]
for n in range(1, 10 ** 4):
    subfactorial.append(n * (subfactorial[-1] + subfactorial[-2]))
    factorial.append(n * factorial[-1])

def fixed_points_perms(n, k):
    return factorial[n] // factorial[n-k] // factorial[k] * subfactorial[n-k]


from math import factorial as fact
A000166 = [1,0]
for n in range(2,9000): A000166.append((n-1)*(A000166[n-1]+A000166[n-2]))


# this is just A000166(n-k)*binomial(n,k)
def fixed_points_perms(n,k):
    if n<k: return 0
    return A000166[n-k]*fact(n)//(fact(k)*fact(n-k))

from collections import deque
from math import factorial 

def fixed_points_perms(n,m): 
    if m >= n : return [1,0][m>n]
    
    def dear(n):
        arr, i  = deque([1,0,1]), 3 
        while i < n+1 :
            arr.append((i-1)*(arr[-1] + arr[-2]))
            arr.popleft()
            i+=1
        return arr[-1]

    de = [1,0,1][n-m] if n-m<=2  else dear(n-m)

    return (factorial(n)*de)//(factorial(n-m)*factorial(m))

def fixed_points_perms(n,k):
    fact_list = [0,1]
    dearr_list = [1, 0]
    if k==n:
        return 1
    elif k>n:
        return 0
        
    if k != 0:
        for i in range(2, n+1):
            fact_list.append(i*fact_list[-1])
        combinations = fact_list[-1]//(fact_list[k]*fact_list[n-k])
    else:
        combinations = 1
    
    for i in range(2, n-k+1):
        dearr_list.append((i-1)*(dearr_list[-1]+dearr_list[-2]))
    print(combinations, dearr_list[-1])
    return int(combinations) * dearr_list[-1]

f=[1,0,1,2,9,44]
for i in range(6,10000):
    f.append(i*f[-1]+(-1)**i)


def c(x,y):
    if y>x: return 0
    if y>(x//2): y=x-y
    mul=1
    for i in range(1,y+1):
        mul = mul*(x-i+1) // i
    print(mul)
    return mul


def fixed_points_perms(n,k):
    
    return c(n,k) * f[n-k]

from math import factorial
fac = factorial  
subfac = lambda n: n * subfac(n-1)+(-1) ** n if not n == 0 else 1
def fixed_points_perms(n,k):
    if n < k: return 0
    return (fac(n)//(fac(n-k)*fac(k))) * subfac(n-k)