在 5×5 方格棋盘中，要求每一行和每一列都恰有 3 个格子被涂黑，有几种不同的涂法？

wintex

王守恩

在 5×5 方格棋盘中,  要求每一行和每一列都恰有 3 个格子被涂黑,  有几种不同的涂法？

a(0) = 1,
a(1) = 0,
a(2) = 0,
a(3) = 1,
a(4) = 24,
a(5) = 2040, —— 在 5×5 方格棋盘中,  要求每一行和每一列都恰有 3 个格子被涂黑,  有 2040 种不同的涂法。
a(6) = 297200,  
a(7) = 68938800,  
a(8) = 24046189440,
a(9) = 12025780892160,

\(a(n) = \frac{9 n (n - 1) (3 n^2 - 5 n + 4)}{12 (3 n - 5)}*a(n-1) +\frac{3 n (n - 1)^2 (n - 2) (3 n + 1)}{12 (3 n - 5)}*a(n-2)+ \frac{n (n - 1)^2 (n - 2)^2 (9n^2 - 30 n + 13)}{12 (3 n - 5)}*a(n-3) - \frac{n (n - 1)^2 (n - 2)^2 (n - 3)^2 (3 n - 2)}{12 (3 n - 5)}*a(n-4)\)

有 "好的" 算法吗？！！！谢谢各位！！！！

{1, 0, 0, 1, 24, 2040, 297200, 68938800, 24046189440, 12025780892160,
8302816499443200,
7673688777463632000,
9254768770160124288000,
14255616537578735986867200,
27537152449960680597739468800,
65662040698002721810659005184000,
190637228506535883540302038364160000,
665825560532772251175492202972938240000,
2767806480542211571651550187279222472704000,
13564406360915457771720399143711430952267776000,
77705104689340239554388061645133412621507133440000,
516344916592465985916193132955634668149853314252800000,
3952235963968636235373920011837764082275323312165683200000,
34625865751056601786040939091232067925054065762034992087040000,
345216770035327687605585138615897466610184682080602693354127360000,
3895853457976677864867654321956818370072419601979789614154252288000000,
49522400455794179580272274423460997875494831300307832047532880691200000000,
705862350216147733268489640719768814435847229884328960929338869116108800000000,
11233957698968897356370426894487157802018583847602368650341701891184158834688000000,
198858506430615502152143521114808572875022859223822600561777840124945712964698112000000,
3900984140604043576114981345521436871243170324129369314291839620429490882080140165120000000}

王守恩

楼上的数字串。
{1, 0, 0, 1, 24, 2040, 297200, 68938800, 24046189440, 12025780892160,
8302816499443200,
7673688777463632000,
9254768770160124288000,
14255616537578735986867200,
27537152449960680597739468800,
65662040698002721810659005184000,
190637228506535883540302038364160000,
665825560532772251175492202972938240000,
2767806480542211571651550187279222472704000,
13564406360915457771720399143711430952267776000,
77705104689340239554388061645133412621507133440000}

T[n_, k_] := T[n, k] = Module[{u = <||>}, canonical[t_] := Sort[Select[t, # > 0 &]]; search[r_, t_] := Module[{R, s, w, v}, If[r > n, Return[If[Total[t] == 0, 1, 0]]]; R = canonical[t];
If[KeyExistsQ[u, R], Return[u[R]]]; v = 0; Do[If[And @@ (t[[#]] > 0 & /@ s), w = t; Scan[(w[[#]]--) &, s]; v += search[r + 1, w]], {s, Subsets[Range[n], {k}]}]; u[R] = v; v]; search[1, Table[k, {n}]]];
Table[T[m, 3], {m, 0, 20}] ——用这个代码也可以。只是速度慢了。好处是 "3" 可以改。

luyuanhong

luyuanhong