一道排列组合题

葡萄糖 · 发表于 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[Transpose[{Range[4], #}] -> 1] & /@
Permutations@Range[4], MemberQ[Through@Grot[#1], #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[Transpose[{Range[4], #}] -> 1] & /@
Permutations@Range[4], MemberQ[Through@Grotflip[#1], #2] &]

复制代码

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

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

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 一道排列组合题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评

点评