19
\$\begingroup\$

In combinatorics, the 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

(The image above comes from Wolfram MathWorld.)

The rook polynomials are closely related to the 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 , 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]
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Related: Laguerre Polynomials. \$\endgroup\$
    – alephalpha
    Aug 7 at 13:31
  • \$\begingroup\$ Am I missing something? For example, there are 2 ways to place two rooks on a 2×2 chessboard, 4 ways to place one rook, and 1 way to place no rooks. Therefore, 𝑅2,2(𝑥)=2𝑥2+4𝑥+1 This doesn't make any sense to me. It's saying that R2,2(2) should be 2, but based on the provided polynomial, subbing in x for 2 it would be 17. Not even close. I must be misunderstanding something here? \$\endgroup\$
    – Cruncher
    Aug 9 at 17:31
  • \$\begingroup\$ @Cruncher you have misunderstood what the polynomial represents. Each coefficient corresponds to the number of ways to place the corresponding number of rooks so that they don’t attack each other. So on a 2x2 board, 2 rooks can be placed 2 ways without attacking each other, so the coefficient of the \$x^2\$ term is 2. Similarly for 1 rook there are 4 ways, so the coefficient for the \$x\$ term is 4. \$\endgroup\$
    – Aiden Chow
    Aug 9 at 20:50
  • 1
    \$\begingroup\$ So plugging in a particular x value has nothing to do with the challenge at hand, though I’m sure in some mathematical context it does have useful implications. \$\endgroup\$
    – Aiden Chow
    Aug 9 at 20:51

14 Answers 14

12
\$\begingroup\$

JavaScript (ES6), 31 bytes

Expects (m)(n)(k).

m=>n=>g=k=>k?m--*n--/k*g(--k):1

Try it online!

How?

Like other answers, this is based on the formula from Wikipedia, 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}$$

\$\endgroup\$
9
\$\begingroup\$

Python, 63 50 bytes

lambda m,n,k:comb(m,k)*perm(n,k)
from math import*

Attempt This Online!

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

\$\endgroup\$
1
7
\$\begingroup\$

Thunno 2, 5 bytes

cṭsƇ×

Try it online!

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
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Why the downvote? It passes the test cases. \$\endgroup\$
    – The Thonnu
    Aug 7 at 13:57
6
\$\begingroup\$

Python, 41 bytes

f=lambda m,n,k:k<1or f(m-1,n-1,k-1)*m*n/k

Try it online!

Based on the formula in Arnauld's answer . Test cases from xigoi. 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.

\$\endgroup\$
6
\$\begingroup\$

Julia 1.0, 39 33 bytes

f(k,m,n)=k<1||m*f(k-1,m-1,n-1)n/k

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Aug 10 at 20:13
  • 1
    \$\begingroup\$ 33 bytes with the && operator Try it online! also added testcases \$\endgroup\$
    – MarcMush
    Aug 11 at 7:49
4
\$\begingroup\$

Jelly, 5 bytes

!;c@P

Attempt This Online!

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
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Unless there's another mathematical trick we can pull I think five is it. With swapped order c;!}P (or c;R}P) or c׃!} would do the same thing. \$\endgroup\$ Aug 7 at 18:53
4
\$\begingroup\$

C (gcc), 37 bytes

f(m,n,k){m=k?m--*n--*f(m,n,k-1)/k:1;}

Try it online!

My first C answer (yay!)

Port of Arnauld's JavaScript answer.

Fixed thanks to @mousetail

\$\endgroup\$
3
4
\$\begingroup\$

Desmos, 25 bytes

f(m,n,k)=nCr(n,k)nPr(m,k)

Try It On Desmos!

Takes in \$m,n,k\$ as input. Port of like most of the answers here.

\$\endgroup\$
4
\$\begingroup\$

R*, 37 35 bytes

f=\(l)prod(if(l)c(f(l-1)/l[1]^2,l))

Attempt This Online!* or Try it Online 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.

\$\endgroup\$
2
  • \$\begingroup\$ it appears that the adjusted syntax for the short function definition was introduced in 4.1.0 and the if() erroring out instead of giving a warning was changed in 4.2.0, so this code only works in versions 4.1.x! \$\endgroup\$
    – Giuseppe
    Aug 11 at 14:24
  • 1
    \$\begingroup\$ @Giuseppe - Aha - my local installation is still 4.1.3, and everything works happily, but I hadn't realized that the 'happy zone' was so narrow. I'll add an edit to note this.. Thanks. \$\endgroup\$ Aug 11 at 18:32
3
\$\begingroup\$

05AB1E, 5 bytes

cI¹e*

Inputs in the order \$k,m,n\$.

Try it online or verify all test cases.

Or alternatively:

c¹!ªP

Inputs in the order \$k,[m,n]\$.

Try it online or verify all test cases.

Both are port of @xigoi's Python answer.

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)
\$\endgroup\$
3
  • \$\begingroup\$ @TheThonnu Triple swap in 05AB1E with implicit inputs will simply take the last input twice. So with inputs [1,3,5] my current answers will correctly result in 15, but cŠe* will incorrectly become 360, since the Še will be 5 nPr 5 instead of 1 nPr 5. \$\endgroup\$ Aug 8 at 12:12
  • \$\begingroup\$ @TheThonnu Btw, are you sure your own answer is correct, or there isn't a bug in your language itself? If your input-order is the same as mine (\$k,m,n\$), I'm confused why your program results in 9 instead of 15. Your triple-swap does work as intended: try it online, but your Ƈ seems to result in 3 instead of 5 in your program: try it online, even though Ƈ works correctly with 1 and 5 as inputs: try it online. 🤔 Maybe I'm doing something wrong with the inputs, though? \$\endgroup\$ Aug 8 at 12:13
  • \$\begingroup\$ Oh, thanks. We actually needed a swap after the triple swap in Thunno 2, since the top two items were in the wrong order. I've updated my answer, which now ties with 05AB1E, Jelly, and Vyxal :) \$\endgroup\$
    – The Thonnu
    Aug 8 at 12:57
2
\$\begingroup\$

Vyxal, 5 bytes

ƈ?¡JΠ

Try it Online!

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
\$\endgroup\$
2
  • \$\begingroup\$ ƈ?¡JΠ or ƈ?ɾJΠ TIO works as a port of xigoi's Jelly answer. (Vyncode increases the code size to over 5 bytes though, so maybe there is a "better" implementation that doesn't.) \$\endgroup\$ Aug 7 at 19:09
  • \$\begingroup\$ @JonathanAllan thanks, updated \$\endgroup\$
    – The Thonnu
    Aug 7 at 20:42
1
\$\begingroup\$

Charcoal, 17 bytes

≔…⁰NθI÷ΠΣE²⁻NθΠ⊕θ

Attempt This Online! 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
   N                Input `k`
≔   θ               Store in variable
          ²         Literal integer `2`
         E          Map over implicit range
            N       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
     I              Cast to string
                    Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Mathematica 12.2 or later, 38 26 bytes

Saved 12 bytes thanks to the comment of @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]
\$\endgroup\$
1
  • \$\begingroup\$ 26 bytes: 1##&@@{##2}~Binomial~# #!&, take input in the order k,m,n. \$\endgroup\$
    – alephalpha
    Aug 11 at 4:36
1
\$\begingroup\$

Ruby, 42 bytes

->(m,n,k){k>0?f.call(m-1,n-1,k-1)*m*n/k:1}

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 (and falls only one byte short of it :P)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.