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.

Source: codewars | Difficulty: EASY
Tags: Number theory

Fundamentals

Complete search

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

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)