# 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.

### Input Format

{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}}\$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. Feb 4, 2021 at 14:27 • Does this answer your question? Fun With Permutations 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. 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 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*? 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. 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). 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 Feb 4, 2021 at 15:01 • @Davide Nice one - thanks! :D 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 Feb 4, 2021 at 13:46 • And you can save 2 more bytes by taking the arguments the other way around: 22 bytes 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... 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!!! Feb 5, 2021 at 17:11 • @Xi'an - Ha! Too soon! I just managed to sneak-away another byte! 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 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. 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! 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. 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... 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

.+
$.(99*100*  When executed as a Retina program, this then replaces the input with the desired result. # Wolfram Language (Mathematica), 11 bytes #!/(#-#2)!&  Try it online! # Jelly, 4 bytes _Ɱ‘P  Try it online!  Ɱ For each x in 1 .. k, _ subtract it from n ‘ and increment. P Take the product.  Alternatively, # Jelly, 4 bytes c×!}  Try it online! c nCk × times !} k!  Bonus solution, 5 bytes, all ASCII: ,_!:/ # MATL, 7 bytes Xn0G:p*  Because snog :p* Xn % compute nchoosek 0G:p % compute k! * % multiply  Try it online! # Factor, 28 21 bytes [ [0,b) n-v product ]  Try it online! Inspired by Jonathan Allan's Jelly answer. Now beats the built-in solution! Takes two numbers n k from the stack, subtracts 0..k-1 from n, and computes the product. The product of an empty sequence is 1. # Factor, 27 bytes USE: math.combinatorics nPk  Try it online! There's a built-in for this ... except that the import is horribly long. # Vyxal, 2 bytes ∆ƈ  Try it Online! Another built-in, like 05AB1E, but not quite as concise. First input is k, second input is n. # Excel, 14 bytes =PERMUT(A1,A2)  An Excel built-in. # Japt, 6 bytes o áV l  Try it here # Perl 5 -MList::Util=reduce, 36 bytes sub f{reduce{$a*$b}$_[0]+1-pop..pop}


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;}


# Pari/GP, 16 bytes

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.....