来自讨论组的计数题，4种坚果装5个不同袋子

kuing

鱼子(5755*****) 2024/3/13 10:40:27
小林同学喜欢吃 4 种坚果：核桃、腰果、杏仁、榛子，他有 5 种颜色的坚果袋，每种袋子中至少装 1 种坚果，至多装 4 种坚果。小林同学希望五个袋子中所装坚果种类各不相同，且每种坚果在袋子里出现的总次数均为偶数，那么不同的方案数为（   ）

真难，数也难数……

首先用表来表示方案，比如
$\begin{array}{c|c|c|c|c|c|}
  & A & B & C & D & E \\ \hline
a & * & * &   &   &   \\ \hline
b & * &   & * &   &   \\ \hline
c & * &   &   & * &   \\ \hline
d & * &   &   &   & * \\ \hline
\end{array}$
行为 4 坚果，列为 5 袋子，上表即表示 坚果a 装在 袋A、袋B 中，坚果b 装在 袋A、袋C 中等等……

为了操作方便，我利用之前关灯游戏里写的 html，改写成可以记下状态，这样也数了挺久才数完。
数的时候为了避免重复，总是从上至下、从左至右点。
每点一行时，需观察上方的状态，对于同理的情况，只列靠左的。
举个栗子，以下两种情况是同理的，则只列左边的，因为最后会乘以列的全排列 `5!`，就包含了右边。
$\begin{array}{c|c|c|c|c|c|}
  & A & B & C & D & E \\ \hline
a & * & * &   &   &   \\ \hline
b & * &   & * &   &   
\end{array}\qquad\begin{array}{c|c|c|c|c|c|}
  & A & B & C & D & E \\ \hline
a & * & * &   &   &   \\ \hline
b &   & *  & * &   &   
\end{array}$

kuing

每行都 2 个的：

一共 25 个

4,2,2,2 的：

一共 19 个

4,4,2,2 的：

一共 9 个

4,4,4,2 的：

一共 3 个

4,4,4,4 的：

一共 1 个

所以答案为 \[(25 + 19\times C_4^1 + 9\times C_4^2 + 3\times C_4^1 + 1)\times5!=20160.\]

kuing

然而当我数完了，准备发帖时，考虑到群里那图片拍得不是很清晰，我就想不如在网上搜一个文字版的题目复制过来好了。

然而一搜却发现，原来有非常巧妙的计算方法！见：
zhuanlan.zhihu.com/p/617022557
（虽然开头有不少笔误，但还是能看懂的，有空得重新叙述一遍）

kuing

另外，要是用 MMA 验证，代码怎么写？

Czhang271828

记号尽量与主楼一致.

考虑二元域 $k=\mathbb F_2$ 上的线性空间. 定义 $k^4$ 中的五个 (列) 向量 $\{A,B,C,D,E\}$, 使得 $A_i=0$ 当且仅当 $A$ 装了第 $i$ 种坚果.

这五个向量求和为 $0$ 向量. 但依照题意, 任意两个向量和非 $0$, 因此任意三个向量和非零. 任意一个或四个向量和也非零. 从而向量组 $\{A,B,C,D,E\}$ 的秩为 $4$. 由于 $E=A+B+C+D$, 故题中每种方案对应一个 $4\times 4$ 可逆矩阵 $(A\,\,B\,\,C\,\,D)$.

$A$ 取 $k^4$ 中非零向量, 有 $2^4-2^0$ 种取法;
$B$ 取 $k^4\setminus \mathrm{span}(A)$ 中向量, 有 $2^4-2^1$ 种取法;
$C$ 取 $k^4\setminus \mathrm{span}(A,B)$ 中向量, 有 $2^4-2^2$ 种取法;
$D$ 取 $k^4\setminus \mathrm{span}(A,B,C)$ 中向量, 有 $2^4-2^3$ 种取法.

kuing

Czhang271828 发表于 2024-3-15 13:38
记号尽量与主楼一致.

考虑二元域 $k=\mathbb F_2$ 上的线性空间. 定义 $k^4$ 中的五个 (列) 向量 $\{A,B, ...

看起来比 3# 链接讲得更专业（本质应该是差不多的吧？