[Question]
  [
In combinatorics, the [**rook polynomial**](https://en.wikipedia.org/wiki/Rook_polynomial) \$R\_{m,n}(x)\$ of a \$m \times n\$ chessboard is the generating function for the numbers of arrangements of non-attacking rooks. To be precise:
$$R\_{m,n}(x) = \sum\_{k=0}^{\min(m,n)} r\_k x^k,$$
where \$r\_k\$ is the number of ways to place \$k\$ rooks on an \$m \times n\$ chessboard such that no two rooks attack each other; that is, no two rooks are in the same row or column.
The first few rook polynomials on square chessboards are:
* \$R\_{1,1}(x) = x + 1\$
* \$R\_{2,2}(x) = 2 x^2 + 4 x + 1\$
* \$R\_{3,3}(x) = 6 x^3 + 18 x^2 + 9 x + 1\$
* \$R\_{4,4}(x) = 24 x^4 + 96 x^3 + 72 x^2 + 16 x + 1\$
For example, there are \$2\$ ways to place two rooks on a \$2 \times 2\$ chessboard, \$4\$ ways to place one rook, and \$1\$ way to place no rooks. Therefore, \$R\_{2,2}(x) = 2 x^2 + 4 x + 1\$.
![Rook placements on a 2x2 chessboard](https://mathworld.wolfram.com/images/eps-svg/RookPolynomial_701.svg)
(The image above comes from [Wolfram MathWorld](https://mathworld.wolfram.com/RookPolynomial.html).)
The rook polynomials are closely related to the [generalized Laguerre polynomials](https://en.wikipedia.org/wiki/Laguerre_polynomials#Generalized_Laguerre_polynomials) by the following formula:
$$R\_{m,n}(x) = n! x^n L\_n^{(m-n)}(-x^{-1}).$$
## Task
Your task is to write a program or function that, given two positive integers \$m\$ and \$n\$, outputs or returns the rook polynomial \$R\_{m,n}(x)\$.
You may output the polynomials in any reasonable format. Here are some example formats:
* a list of coefficients, in descending order, e.g. \$24 x^4 + 96 x^3 + 72 x^2 + 16 x + 1\$ is represented as `[24,96,72,16,1]`;
* a list of coefficients, in ascending order, e.g. \$24 x^4 + 96 x^3 + 72 x^2 + 16 x + 1\$ is represented as `[1,16,72,96,24]`;
* a function that takes an input \$k\$ and gives the coefficient of \$x^k\$;
* a built-in polynomial object.
You may also take three integers \$m\$, \$n\$, and \$k\$ as input, and output the coefficient of \$x^k\$ in \$R\_{m,n}(x)\$. You may assume that \$0 \leq k \leq \min(m,n)\$.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest code in bytes wins.
## Test Cases
Here I output lists of coefficients in descending order.
```
1,1 -> [1,1]
1,2 -> [2,1]
1,3 -> [3,1]
1,4 -> [4,1]
1,5 -> [5,1]
2,1 -> [2,1]
2,2 -> [2,4,1]
2,3 -> [6,6,1]
2,4 -> [12,8,1]
2,5 -> [20,10,1]
3,1 -> [3,1]
3,2 -> [6,6,1]
3,3 -> [6,18,9,1]
3,4 -> [24,36,12,1]
3,5 -> [60,60,15,1]
4,1 -> [4,1]
4,2 -> [12,8,1]
4,3 -> [24,36,12,1]
4,4 -> [24,96,72,16,1]
4,5 -> [120,240,120,20,1]
5,1 -> [5,1]
5,2 -> [20,10,1]
5,3 -> [60,60,15,1]
5,4 -> [120,240,120,20,1]
5,5 -> [120,600,600,200,25,1]
```
  
[Answer]
# JavaScript (ES6), 31 bytes
Expects `(m)(n)(k)`.
```
m=>n=>g=k=>k?m--*n--/k*g(--k):1
```
[Try it online!](https://tio.run/##NYxBCoMwEEX3nmKWM2pSXHSjTaTnKKWIjdLGTCSKUIpnTwNtV@/D479nt3VLHx7zKtjfTRxUdEqz0qOyStvWCZGzEAebjyiEpbqKgw84mRUcKKiahJOCY2JRELwzgL/nr@ef578H6D0vfjJy8iO6EriEi5TyHEL3wpRLlzZlC6igTjuRrtJ1M@KtBEugNAzoCJnQEslgNhMWg0RNqu/ZHj8 "JavaScript (Node.js) ‚Äì Try It Online")
### How?
Like other answers, this is based on [the formula from Wikipedia](https://en.wikipedia.org/wiki/Rook_polynomial#The_rook_polynomial_as_a_generalization_of_the_rooks_problem), but re-arranged in a recursive-friendly form:
$$k!\times \binom{m}{k}\times\binom{n}{k}=\prod\_{i=1}^{k}\frac{(m+1-i)\times(n+1-i)}{i}$$
[Answer]
# [Python](https://www.python.org), ~~63~~ 50 bytes
```
lambda m,n,k:comb(m,k)*perm(n,k)
from math import*
```
[Attempt This Online!](https://ato.pxeger.com/run?1=ZY1BDoIwEEX3nGKWHawLXBhD4knERZEiDcy0GauJZ3FDYvRO3kYo7lz95OX9_x_vcI-d5_Ep--p1je1699kMhurGAGnWfXnyVCvSPebBCqkJYdaKJyATO3AUvMT81xxaL0DgGMTw2apCb7HMAGbM_xggiOM4rQNrOIhKj5j0Pun2ZuViG7X0yPGs4KpAPOLyOY5LfgE)
To place \$k\$ rooks on an \$m\times n\$ chessboard, we choose \$k\$ out of the \$m\$ rows, \$k\$ of the \$n\$ colums and a permutation of the numbers from \$1\$ to \$k\$ representing which rook will be at which place in each row. This gives a total of \$\binom{m}{k}\cdot\binom{n}{k}\cdot k!\$ options.
*-13 bytes thanks to matteo\_c*
[Answer]
# [Thunno 2](https://github.com/Thunno/Thunno2), 5 [bytes](https://github.com/Thunno/Thunno2/blob/main/docs/codepage.md)
```
c·π≠s∆á√ó
```
[Try it online!](https://Not-Thonnu.github.io/run#aGVhZGVyPSZjb2RlPWMlRTElQjklQURzJUM2JTg3JUMzJTk3JmZvb3Rlcj0maW5wdXQ9NSUwQTUlMEE1JmZsYWdzPQ==)
Port of xigoi's Python answer. Takes `k`, then `m`, then `n`.
#### Explanation
```
c·π≠s∆á√ó  # Implicit input
c      # Compute nCr(m, k)
 ·π≠s    # Swap to get the right order
   ∆á   # Compute nPr(n, k)
    √ó  # Multiply together
       # Implicit output
```
[Answer]
# [Python](https://docs.python.org/2/), 41 bytes
```
f=lambda m,n,k:k<1or f(m-1,n-1,k-1)*m*n/k
```
[Try it online!](https://tio.run/##ZY2xDsIwDER3vsJj3LpCZmCo4EsQQ1ATiIzdKlRIfH1Iyshwy927u@WzPmY7lBLPT6@3yYOSkYxy4jlDdDowWZUMjJ12tpcSa6CQDLK3e3BMRxx3AM22fxtgycnWOgtGcOnrZDvAjZeND@@QX2Fyv6Imawj2jHgtXw "Python 2 ‚Äì Try It Online")
Based on the formula in [Arnauld's answer](https://codegolf.stackexchange.com/a/263835/20260). Test cases [from xigoi](https://codegolf.stackexchange.com/a/263831/20260). Outputs `True` for `1` when `k=0`. The code also works in Python 2 or 3, but gives floats in Python 3 that can become imprecise for large outputs.
[Answer]
# [Julia 1.0](http://julialang.org/), ~~39~~ 33 bytes
```
f(k,m,n)=k<1||m*f(k-1,m-1,n-1)n/k
```
[Try it online!](https://tio.run/##bZDRboIwFIbvfYozLwwsB0ZLy3QZZi@wJzBe1FiTDuxMYcsufHfW9qBitoaT8v05/Xrg46s1iv0MwyFp8Ig2rZtXdj4fHz1nDI@@bMZS@9QMh08HBowFp9W@NVZ3SToDvxTCDmrQ36rNk3fdq/ykXKfzpDu1pk8MwjxbzyFNqf3kjO1bmyio17CjLLib4C5eZAzCcl4axgKV53k6iR9qKGCxuJqaYHL/dbyprtOuD6oadhtt91mzhdjo32ehBoYMsjVs/L6dMeQROEEZoSQQEQSBjCAD8FHACS4CQUiKCitCkjCOS2Ly8AJZEYJydJUEfHq4vLrYEleUkI4LLH3KKSNlVaB/WJxQjFZBwO9mEKN2KhE38arCZ59VFMvxaIFceHvY49xyvEES8PuvkpfJJzPJ66/467rdUhVUPFQ49ws "Julia 1.0 ‚Äì Try It Online")
*-6 bytes and test cases due to @MarcMush*
Similar in spirit to @The Thonnu 's answer. Given a triple \$(k,m,n)\$, there are \$m\times n\$ ways of placing the first rook, and then the problem is reduced to that of the triple \$(k-1, m-1, n-1)\$ since we can just eliminate the file and rank that we placed the first rook on. By the end we will have over-counted by a factor of \$k!\$, since the order of placement of the rooks does not matter.
edit: I made a mistake when copying the code from my IDE so the original solution of 32 bytes was defective :X
[Answer]
# [Jelly](https://github.com/DennisMitchell/jellylanguage), 5 bytes
```
!;c@P
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m700KzUnp3LBgqWlJWm6FksVrZMdApYUJyUXQ0XWRisZKekoRZvqmMQqxUIFAQ)
Takes arguments in the form `k [m,n]`. I didn't manage to come up with anything shorter, but feel like it's possible‚Ä¶ But at least this is ASCII-only as a bonus.
```
!;c@P
!     Factorial of k
 ;    Join that with
  c@  [m,n] choose k (vectorized)
    P Product
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 37 bytes
```
f(m,n,k){m=k?m--*n--*f(m,n,k-1)/k:1;}
```
[Try it online!](https://tio.run/##Xc3RCsIgFMbx@z3FxyDQptRuuthme5DqIhbGUbQY3Q2f3ZTGVoGei/PDv4O8D0OMmjnhheWTU7Z3Um59uvNS1nxnm7oNkfwL7kqecUwFoB8jWN6RqltQd0ijqj72pSaryWpWBZ5jQs3KzQ3pnFAKkIDh7ezLe6sYdaanJhnsUe3TlHIN/aRSRbPcEbB8aYW/Py9nX86YKRQhvgE "C (gcc) ‚Äì Try It Online")
My first C answer (yay!)
Port of Arnauld's JavaScript answer.
*Fixed thanks to @mousetail*
[Answer]
# [Desmos](https://desmos.com/calculator), 25 bytes
```
f(m,n,k)=nCr(n,k)nPr(m,k)
```
[Try It On Desmos!](https://www.desmos.com/calculator/anojjythum)
Takes in \$m,n,k\$ as input. Port of like most of the answers here.
[Answer]
# [R](https://www.r-project.org)\*, ~~37~~ 35 bytes
```
f=\(l)prod(if(l)c(f(l-1)/l[1]^2,l))
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72waMFNp4TMtATbtNK85JLM_DyNCp1KW79QHx-dKjClmZRYnGplBVKjUREdbRgbC5SvBEpWaXIV5ednF-TnVNouLS1J07W4qZxmG6ORo1lQlJ-ikZkGZCVrAEldQ039HKDGOCOdHE1NqFLN4sSCgpxKDQMrEx241dmaMBM1kjWydUx0TDRhGhYsgNAA)\*
or [Try it Online](https://tio.run/##K/pflJ@fXZCfU2n7P802rTQvuSQzP08jR7OgKD9FIzMNyErWAJK6hpr6OdGGsXFGOjmamv@LEwsKcio1DKxMdOB6sjVhRmkka2TrmOiYaAJVAgA) using `function` instead of the shorter `\` notation.
Input is a vector `(k,m,n)`. This allows a compact function definition of `f(l)`, and lets us perform a recursive call with all arguments decremented using just `f(l-1)`, saving quite a few bytes compared to `f(k,m,n)` and `f(k-1,m-1,n-1)`.  
To get `m*n/k` we now need to use `prod(l)/l[1]^2`, which may initially seem a bit verbose, but it brings the useful property that `prod(NULL)` is equal to `1`, nicely solving the base case when `k==0` (so `if(l)` doesn't return anything).
\*ATO uses a version of R (version 4.3.1) in which the `if` function errors when the condition has length >1. Versions between 4.1.0 and <4.2.0 just give a warning for this without halting with an error, and the header in the ATO link redefines the `if` function to mimic this behaviour.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 5 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
cI¬πe*
```
Inputs in the order \$k,m,n\$.
[Try it online](https://tio.run/##yy9OTMpM/f8/2fPQzlSt//@NuUy5TAA) or [verify all test cases](https://tio.run/##ATAAz/9vc2FiaWX/NUzDo3Z5w5/GknlOwqrDgj8iIOKGkiAiP8SHVWDCqf9jWMKuZSr/LP8).
Or alternatively:
```
c¬π!¬™P
```
Inputs in the order \$k,[m,n]\$.
[Try it online](https://tio.run/##yy9OTMpM/f8/OeDQTkWt//@NuaJNdUxiAQ) or [verify all test cases](https://tio.run/##yy9OTMpM/W/qc3hxWeXh@ccm@dkrKSTmpSgo2VcCWY/aJoFYfv@T/RQPrQr4r/MfAA).
Both are port of [*@xigoi*'s Python answer](https://codegolf.stackexchange.com/a/263831/52210).
**Explanation:**
```
c     # Push the first (implicit) input `nCr` the second (implicit) input,
      # aka the number of combinations; aka the binomial coefficient; aka `k choose m`
 I    # Push the third input
  ¬π   # Push the first input again
   e  # Pop both, and push their `nPr`, aka the number of permutations
    * # Multiply them together: (k nCr m)*(k nPr n)
      # (which is output implicitly as result)
```
```
c     # Push the first (implicit) input `nCr` the second (implicit) input-pair:
      #  [k nCr m,k nCr n]
   ¬™  # Append
  !   # the factorial of
 ¬π    # the first input `k`: [k nCr m,k nCr n,k!]
    P # Get the product of this list: (k nCr m)*(k nCr n)*k!
      # (which is output implicitly as result)
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 5 bytes
```
∆à?¬°JŒ†
```
[Try it Online!](https://vyxal.pythonanywhere.com/?v=2#WyIiLCIiLCLGiD/CoUrOoCIsIiIsIjRcbjUsIDUiXQ==)
Port of xigoi's Jelly answer. Takes `k`, then `[m, n]`.
*-2 thanks to @JonathanAllan*
#### Explanation
```
∆à?¬°JŒ†  # Implicit input
∆à      # Compute nCr of both
 ?¬°    # Factorial of k
   J   # Appended to the list
    Œ†  # Take the product
       # Implicit output
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 17 bytes
```
‚âî‚Ä¶‚Å∞ÔºÆŒ∏Ôº©√∑Œ†Œ£Ôº•¬≤‚ÅªÔºÆŒ∏Œ†‚äïŒ∏
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m70iOSOxKDk_MWfBgqWlJWm6FjebHYuLM9PzNIIS89JTNQx0FDzzCkpL_Epzk1KLNDQ1dRQKNa25Aooy80o0nBOLSzQ880pcMssyU1I1AoryU0qTSzSCS3M1fBMLNIx0FHwz80qLNVBMABmgCTIHptwzL7koNTc1ryQ1RQMspWm9pDgpuRjqoOXRSrplOUqxS40VTBRMIWIA) Link is to verbose version of code. Takes `k` as the first input. Explanation: Uses the same formula as @Arnauld's answer, but works by taking the product of lists instead of recursing.
```
 ‚Ä¶                  List from
  ‚Å∞                 Literal integer `0` to
   ÔºÆ                Input `k`
‚âî   Œ∏               Store in variable
          ¬≤         Literal integer `2`
         Ôº•          Map over implicit range
            ÔºÆ       Next input `m` or `n`
           ‚Åª        Vectorised subtract
             Œ∏      Stored range
        Œ£           Concatenate the lists
       Œ†            Take the product
      √∑             Integer divided by
                Œ∏   0-indexed range
               ‚äï    Increment to 1-indexed range
              Œ†     Take the product
     Ôº©              Cast to string
                    Implicitly print
```
[Answer]
# [Mathematica 12.2 or later](https://reference.wolfram.com/legacy/language/v13/guide/SummaryOfNewFeaturesIn122), ~~38~~ 26 bytes
Saved 12 bytes thanks to the comment of [@alephalpha](https://codegolf.stackexchange.com/users/9288/alephalpha)
---
26 bytes version:
```
1##&@@{##2}~Binomial~# #!&
```
---
‚ÄÉ
‚ÄÉ
38 bytes version:
```
{n,m,k}|->k!Binomial[m,k]Binomial[n,k]
```
How to use it?
```
f={n,m,k}|->k!Binomial[m,k]Binomial[n,k]
f[4,3,2]
```
[Answer]
# [Ruby](https://www.ruby-lang.org/), 42 bytes
```
->(m,n,k){k>0?f.call(m-1,n-1,k-1)*m*n/k:1}
```
[Try it online!](https://tio.run/##VY6xCoMwGIR3n@LQxUiSmqFLofZBrIO1BkrMr2gdiuTZ06h16HD8/x0fx43z4@M1rrh7UaSWEzdsMUV@07Kpuy61QnEKMkKxzGZ0MhflvO5HWLwISsoznn0ErBH9R0DTt1pPob2sNr9CZoVyKUvLQZW0wf3og5f1MLT0xDEhcByGbUzItzvM7wlxmizWcSQLOQYhivDtFS6OdjbIfwE "Ruby ‚Äì Try It Online")
I had an idea with a recursive lambda, much like a few others here. My answer is probably the most similar to [xnor's](https://codegolf.stackexchange.com/a/263848/119199) (and falls only one byte short of it :P)
]