论坛 › 难题征解 › 一道排列组合题

葡萄糖 发表于 2014-2-22 15:51:40

一道排列组合题

ABCD四个字母填入4行4列的正方形，要求每行每列不允许字母重复，又旋转重合认为同一种，有多少种不同办法？

倪举鹏 发表于 2014-2-22 20:48:38

编程穷举比八后问题简单

葡萄糖 发表于 2019-3-25 22:12:15

本帖最后由 葡萄糖 于 2019-3-26 08:10 编辑

先不考虑\(\,A\,\),\(\,B\,\),\(\,C\,\),\(\,D\,\)的差异
先考虑每行每列有且仅有一个\(\,1\,\)的\(\,4\times4\,\)二进制方阵；
若考虑旋转等价（http://oeis.org/A263685），那么这样的二进制方阵有9个：
\begin{align*}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}\\
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\end{align*}
e = Identity;
f = Reverse;
g = Transpose;
Grot = {e, f@*g, g@*f, f@*g@*f@*g};
MatrixPlot[#, ImageSize -> Tiny, ColorFunction -> "Monochrome"] & /@
DeleteDuplicates[
SparseArray@Thread, #}] -> 1] & /@
   Permutations@Range, MemberQ, #2] &]
若考虑旋转翻转等价（http://oeis.org/A000903），那么这样的二进制方阵有7个：
\begin{align*}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\\
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\end{align*}
e = Identity;
f = Reverse;
g = Transpose;
Grotflip = {e, f, g, f@*g, g@*f, f@*g@*f, g@*f@*g, f@*g@*f@*g};
MatrixPlot[#, ImageSize -> Tiny, ColorFunction -> "Monochrome"] & /@
DeleteDuplicates[
SparseArray@Thread, #}] -> 1] & /@
   Permutations@Range, MemberQ, #2] &]

kastin 发表于 2019-3-25 22:24:38

跟我之前提到的拉丁方问题有些像：https://bbs.emath.ac.cn/thread-15764-1-1.html

查看完整版本: 一道排列组合题