# Permutation Coefficient

## What is Permutation Coefficient

Permutation refers to the process of arranging all the members of a given set to form a sequence. The number of permutations on a set of n elements is given by n! , where “!” represents factorial. The Permutation Coefficient represented by P(n, k) is used to represent the number of ways to obtain an ordered subset having k elements from a set of n elements.

Mathematically,

### Examples:

P(10, 2) = 90
P(10, 3) = 720
P(10, 0) = 1
P(10, 1) = 10

To Calculate the Permutation Coefficient, you can use the following recursive approach:

P(n, k) = P(n-1, k) + k * P(n-1, k-1)

Though, this approach can be slow at times. So Dynamic approach is preferred mostly.

{n} {k}

### Output Format

{PermutationCoefficient}

### Test Cases

INPUT - 100 2
OUTPUT - 9900

INPUT - 69 5
OUTPUT - 1348621560

INPUT - 20 19
OUTPUT - 2432902008176640000

INPUT - 15 11
OUTPUT - 54486432000

### Constraints in input

N will always be greater than or equal to K.

• Our site support LaTeX if wrapped with $. Like this:$P(n, k)=\underbrace{n \cdot (n -1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)}_{k\text{ factors}}\$Commented Feb 4, 2021 at 14:23 • By the way, it's recommended that you post challenges in the "sandbox for proposed challenges" first for at least 72 hours before posting it on main. Commented Feb 4, 2021 at 14:27 • Does this answer your question? Fun With Permutations Commented Feb 4, 2021 at 19:41 • @rak1507 Well, the only difference is that the other challenge has a cumbersome input format. Maybe we can close the older challenge as a dupe of this one, but having both doesn't seem right. Commented Feb 4, 2021 at 23:04 • @Arnauld and that the old challenge bans builtins. I would prefer closing the older one over this one personally Commented Feb 4, 2021 at 23:11 ## 28 Answers # APL (Dyalog Extended), 5 bytes ⊣÷⍥!- ⊣ left argument ÷⍥! divide over factorial, apply factorial to both arguments and then divide - subtract Try it online! # Python 3.8 (pre-release), 5123 21 bytes import math math.perm Try it online! No builtins: # Python 3.8 (pre-release), 31 bytes f=lambda n,k:k<1or n*f(n-1,k-1) Try it online! • If you're doing this, why not from math import*? Commented Feb 4, 2021 at 16:01 • This sort of thing where a builtin in an import solves a problem has always been a bit of a grey area for a function submission. I don't know what the solution should be, but I disagree that from math import* should be acceptable in the same way an empty program would be unacceptable if the solution was the bin builtin function - just having the program in the namespace should not be enough. Commented Feb 4, 2021 at 23:58 • I think the right way is to submit the reusable name of the function (separate from the import line), just like how an anonymous lambda is submitted. So from math import perm is not valid, but from math import*\nperm or import math\nmath.perm is valid (the latter being 21 bytes). Commented Feb 5, 2021 at 7:17 # C (gcc), 34 32 27 bytes Saved 2 bytes thanks to Davide who credits Irratix's JavaScript answer!!! f(n,k){n=k?n*f(n-1,k-1):1;} Try it online! • I can't find anything to golf. If you want you can add this recursive one giving credit to Irratix Commented Feb 4, 2021 at 15:01 • @Davide Nice one - thanks! :D Commented Feb 4, 2021 at 15:06 # Husk, 4 bytes Π↑↔ḣ Try it online! Π # product of ↑ # the first k elements (k is 2nd argment) of ↔ # the reverse of ḣ # 1...n (n is 1st argument) # Jelly, 3 bytes ḶạP A dyadic Link accepting, the non-negative integers, n on the right and k on the left which yields P(n,k). Try it online! ### How? ḶạP - Link: k, n e.g. 3, 10 Ḷ - lowered range (k) [0, 1, 2] ạ - absolute difference (n) [10,9, 8] P - product 720 # JavaScript ES6, 25 bytes c=(n,k)=>k?n*c(n-1,k-1):1 • You can save a byte by using currying syntax: 24 bytes Commented Feb 4, 2021 at 13:46 • And you can save 2 more bytes by taking the arguments the other way around: 22 bytes Commented Feb 4, 2021 at 14:52 # 05AB1E, 1 byte e Builtins ftw ¯\_(ツ)_/¯ First input is $$\k\$$, second input is $$\n\$$. e is a builtin for the number of permutations, so $$\P(n,k) = \frac{n!}{(n-k)!}\$$. • I was 5 hours late... Commented Feb 4, 2021 at 19:08 # Whispers v2, 34 bytes > Input > Input >> 1P2 >> Output 3 Try it online! Builtins for the win # R, 26 25 bytes Edit: -1 byte by using scan() to take input prod(diff(x<-scan())+1:x) Try it online! Input in reverse order ( k first, then n). • I concede defeat!!! Commented Feb 5, 2021 at 17:11 • @Xi'an - Ha! Too soon! I just managed to sneak-away another byte! Commented Feb 6, 2021 at 15:45 # MathGolf, 5 bytes ‼!-!/ Input in the order $$\k\text{ }n\$$. Try it online. Explanation: ‼ # Apply the following two commands on the stack separately: ! # Take the factorial of the second (implicit) input-integer - # Subtract the second from the first (implicit) input-integers ! # Take the factorial of (n-k) as well / # Integer-divide n! by (n-k)! # (after which the entire stack is output implicitly as result) • +1 to MathGolf for calling the first command !! in this context Commented Feb 7, 2021 at 2:31 # PowerShell, 28 bytes param($a,$b)'$a--*'*$b+1|iex Try it online! # PowerShell 7, 43 bytes$f={param($a,$b)$b ?$a*(&$f($a-1)($b-1)):1} no TIO link because TIO still runs on PS 6, which does not support the ternary operator. # Pyth, 4 .P.* Try it online! # Explanation Q Implicit input of 2-tuple .* splat .P nPr Explicit output • .PF works too. technically this would be a fold operation (so for input [1,2,3,4] it'd return P(P(P(1,2),3),4)), but if the input is a 2 element sequence, it acts identical to the splatting operator. Commented Feb 4, 2021 at 19:33 # x86 Machine Language, 14 bytes 86 31 C0 40 29 F7 4E 78 05 47 F7 E7 EB F8 C3 Try it online! The above bytes of code define a function that calculates and returns the Permutation Coefficient, according to the formula given in the challenge. The function accepts two arguments, n and k, in the EDI and ESI registers, respectively.* The result is returned in the EAX register, as is conventional. * Note that the selection of these two registers is quite flexible. EDI and ESI were chosen to match some standard C calling conventions, but since this is machine code, they can be changed to any other registers of your choice, except for EAX (which is used for the return value) and EDX (which is clobbered by the MUL instruction). Ungolfed assembly mnemonics: PermutationCoefficient: 31 C0 xor eax, eax # \ assume 40 inc eax # / result = 1 29 F7 sub edi, esi # n -= k Top: # <======================\ 4E dec esi # --k | 78 05 js End # terminate if k < 0 | 47 inc edi # ++n | F7 E7 mul edi # result *= n | EB F8 jmp Top # =======================/ End: C3 ret There's nothing especially fancy here. Just machine code at its finest, performing iterative arithmetic with a minimal number of bytes required to encode the instructions. The key innovation is basically just effective use of registers to track the appropriate changes in values of n and k across iterations, which allows the use of extremely small INCrement and DECrement instructions (which can be encoded in only 1 byte). This reduces the number of 2-byte and 3-byte arithmetic operations that must be done inside of the loop, which in turn reduces overall code size. It is probably also a pretty efficient implementation, as far as iterative loops go. ## R, 36 35 bytes Several attempts hitting the same number: function(n,r)choose(n,r)*gamma(r)*r or function(n,r)gamma(r)/beta(n-r+1,r) or yet function(n,r)"if"(r,n*f(n-1,r-1),1) with function(n,r)dpois(n-r,1)/dpois(n,1) doing even worse (by 1). Try it online! • The R battle is on! Commented Feb 5, 2021 at 15:59 • @DominicvanEssen: too bad there is no perm(n,r) R command available. I tried with various densities but they all seem to require more characters. Commented Feb 6, 2021 at 9:03 • There is permutations(n,r) in gtools, but unfortunately it's long name (as well as the need to count the permutations, rather than just return them) makes it the least golfy of all... Commented Feb 6, 2021 at 14:24 # Charcoal, 7 bytes ＩΠ⁻Ｎ…⁰Ｎ Try it online! Link is to verbose version of code. Explanation: Ｎ Input k …⁰ Range from 0 to k-1 Ｎ Input n ⁻ Subtract i.e. range from n-k+1 to n (inclusive) Π Product Ｉ Cast to string Implicitly print # Julia, 20 bytes nothing fancy here, just applying the basic definition P(n,k)=prod(n-k+1:n) Try it online! # Retina, 37 bytes \d+ * ~[".+¶$.("|""L$v(_*)_ \1$.'$* Try it online! Link includes test cases. Takes input in the order k n. Explanation: \d+ * Convert the inputs to unary. L$v(_*)_ \1
$.'$*

List the numbers from n-k+1 to n, with a * suffixed to each.

|""

Don't separate the results with the default newline.

[".+¶$.(" Prefix the results with the given string. ~ Evaluate that as a Retina 1 expression. Example: For the input 2 100, there are two matches, where$.' takes the values 99 and 100. The result of the L command is therefore

.+

Try it online!

# Java (JDK), 45 bytes

(n,k)->{var r=1;for(;k-->0;)r*=n--;return r;}

Try it online!

Works only for results <= Integer.MAX_VALUE.

If f(_,0) wasn't a requirement, it could go down one byte:

(n,k)->{for(var x=n;k-->1;)n*=x--;return n;}

p(n,k)=n!/(n-k)!

Try it online!

# Python 2, 54 bytes

lambda n,k:g(n)/g(n-k)
from math import factorial as g

Try it online!

There's a better python solution already.....