请教一个组合数学问题

  1. 2月前

    这道题是一个算法竞赛题,出自2018年 ICPC 北京网络赛,题目链接

    题目大意:
    一个 \(n\times n\) 的棋盘。有 $2n$ 个黑棋,$n$ 个白棋。现在要把这 $3n$ 个棋子放到棋盘上,使得每行每列都恰有两个黑棋和一个白棋。求放置棋子的方案数。

    目前已经知道两个相关问题的结果:
    放置 $2n$ 个黑棋,使得每行每列恰有两个黑棋。答案是 OEIS A001499
    放置 $n$ 个黑棋和 $n$ 个白棋,使得每行每列恰有一个黑棋和一个白棋。答案是 $n! \times d_n$,$d_n$ 表示错排数,对应于 OEIS A082491

  2. 2月前lostboy 重新编辑

    已经解决了。
    答案是 \(n!\times\)A007107

    注意到 $n$ 个白子位置确定以后,$2n$ 个黑子的放置方案的数目是一定的,跟 $n$ 的白字的具体位置无关。
    所以我们所要求的方案数 $f(n)$ 可以写成 \(f(n) = n! \times g(n)\) 。而 $g(n)$ 就是A007107

    \[
    g(n) = \sum_{k=0}^n \sum_{s=0}^k \sum_{j=0}^{n-k} \frac{(-1)^{k+j-s} n! (n-k)! (2n-k-2j-s)!}{s!(k-s)!(n-k-j)!^2j!2^{2n-2k-j}}
    \]

    $g(n)$ 有一个更便于计算的递推式,当 $n\ge 5$ 时
    \[
    g(n) = \frac{(n-1)(\frac{2(n^3-2n^2+n+1)g(n-1)}{n-2}+ (n^2-2n+2)(n+1)g(n-2) +(2n^2-6n+1)ng(n-3)+(n-3)(g(n-4)(n^3-5n^2+3)-(n-4)(n-1)(n+1)g(n-5)))}{2n}
    \]

 

后才能发言