组合计数

Tesla35

用红蓝两种颜色给3*3方格染色，每格一种颜色，则每行每列都有红蓝格的染法有几种

Tesla35

回复 3# student_qwh

好像听说答案是102

student_qwh

26种

student_qwh

首先最少的蓝6红3    1种
然后蓝5红4      6种
蓝4红5      3*6种
蓝3红6      1种

student_qwh

共26种

student_qwh

稍稍算了一下，从蓝的来考虑
蓝6红3   1
蓝5红4   10
蓝4红5   40
反过来还有51种
不知是否

realnumber

回复 10# student_qwh

思路应该对的，蓝6红3就有6种了。

问题若改为$4\times 4$又怎么办？或增加为3色？

Infinity

这个问题楼主需要澄清一下是否考虑旋转后重合算不算同一种染色方案的问题，或者直接回答2x2有几种填色方案，是1种还是2种。

如果对于旋转重合算一种，那么这个问题一般情况解要用到波利亚计数定理。

realnumber

回复  student_qwh

好像听说答案是102
Tesla35 发表于 2017-12-10 11:04

102对的，程序验证过
var
a,b,c,d,e,f,g,h,i:longint;
m:longint;
begin
  m:=0;
  for a:=0 to 1 do
    for b:=0 to 1 do
      for c:=0 to 1 do
        for d:=0 to 1 do
          for e:=0 to 1 do
            for f:=0 to 1 do
              for g:=0 to 1 do
                for h:=0 to 1 do
                  for i:=0 to 1 do
                  begin
                  if (a*b*c=1) or (d*e*f=1) or (g*h*i=1) then continue;
                  if (a*d*g=1) or (b*e*h=1) or (c*f*i=1) then continue;
                  if ((a-1)*(b-1)*(c-1)=-1) or ((d-1)*(e-1)*(f-1)=-1) or ((g-1)*(h-1)*(i-1)=-1) then continue;
                  if ((a-1)*(d-1)*(g-1)=-1) or ((b-1)*(e-1)*(h-1)=-1) or ((c-1)*(f-1)*(i-1)=-1) then continue;
                  m:=m+1;
                  end;
   writeln(m);
end.

业余的业余

手工数法， 不考虑Infinity 提的顺转对称的合并问题。

分而治之。

考虑左上角的 $2\times 2$ 的子方块，显然，左上角子块不同的两个着色方案不可能是同一种方案。分四种情形考虑:

1. 每行每列都满足题中的要求，显然左上角确定后其它都唯一确定，只有两种。再考虑从这种类型派生出最终着色方案，左上角确定后，有 $5$ 的待确定单元格，但要除去最右列或最底行同色的非法情形，$2\times (2^5-2\times 2\times 2^2+2)=36$.  

2. 两行(列)分别相同, 但两列(行)不同。有 $4$ 种情形，这种情形派生出完整着色方案时，有两个单元格已被决定，只有 $3$ 个可以变动，合法的派生方案有 $4\times (2^3-2)=24$ 种

3. 仅有一行和一列不同，显然只能是一种颜色 $1$ 格， 另外一种颜色 $3$ 格， 有 $2\times 4=8$ 种。从这种类型派生出完整着色方案时有两个单元格已经决定，三个可以变动 $8\times(2^3-2\times 2^1+1)=40$ 种

4. 所有格子同色。只有两种。从这样的子方块每个只能派生出一种 (第一个格子确定后所有其它格子都确定了), 显然最后派生出 $2$ 种。

综上， 总数 = $36+24+40+2=102$ 种。

Infinity

回复  student_qwh

思路应该对的，蓝6红3就有6种了。

问题若改为$4\times 4$又怎么办？或增加为3色？ ...
realnumber 发表于 2019-2-15 11:34

这个问题值得思考，不过结果就变得更多了。比如2种颜色染3x3虽然只有102种，但变为4x4时，结果激增至22874种。

1. n = 4;
2. u = ArrayReshape[Tuples[{1, -1}, n^2], {2^(n^2), n, n}]; v =
3. Select[u,
4.   FreeQ[Total[#, {1}], n] && FreeQ[Total[#, {1}], -n] &&
5.     FreeQ[Total[#, {2}], n] && FreeQ[Total[#, {2}], -n] &];
6. v // Length
7. (* 绘制前16个结果 *)
8. ArrayPlot[#, ColorRules -> {1 -> LightRed, -1 -> LightBlue},
9.    ImageSize -> Tiny, Mesh -> All, Frame -> None,
10.    FrameTicks -> None] & /@ v[[1 ;; 16]]

Copy the Code

4x4部分结果

青青子衿

Tesla35 发表于 2017-12-10 02:17
用红蓝两种颜色给3*3方格染色，每格一种颜色，则每行每列都有红蓝格的染法有几种

Infinity 发表于 2019-4-22 03:46
这个问题值得思考，不过结果就变得更多了。比如2种颜色染3x3虽然只有102种，但变为4x4时，结果激增至22874 ...

如果不考虑题主的“每行每列都有红蓝格”的要求，就是

[组合] 两色染九宫格（旋转翻转等价）
forum.php?mod=viewthread&tid=5979

这个问题前些日子研究过
要么是你的代码有点问题，要么是漏了哪些判断条件~（所以多出了那么多解）
根据计数通项公式有
\begin{align*}
a(4)&=\,\dfrac{1}{8}\left(2^{4^2}+2\cdot2^{4^2/4}+3\cdot2^{4^2/2}+2\cdot2^{(4^2+4)/2}\right)\\
&=\,\dfrac{1}{8}\left(2^{16}+2\cdot2^4+3\cdot2^8+2\cdot2^{10}\right)=\dfrac{2^{16}+2^5+3\cdot2^8+2^{11}}{8}=\,\quad{\large\color{red}{8548}}
\end{align*}

\[a(n) =\begin{cases}\dfrac{1}{8}\left(2^{n^2}+2\cdot2^{n^2/4}+3\cdot2^{n^2/2}+2\cdot2^{(n^2+n)/2}\right) & n= 0\pmod2 \\
\dfrac{1}{8}\left(2^{n^2}+2\cdot2^{(n^2+3)/4}+2^{(n^2+1)/2}+4\cdot2^{(n^2+n)/2}\right)& n= 1\pmod2\end{cases}\]

Infinity

回复 16# 青青子衿
楼主题目并没认定旋转翻转等价，我给的程序没考虑旋转翻转等价的。

Infinity

回复 16# 青青子衿
如果考虑旋转翻转等价，4x4方格红蓝染色，要求每行每列都有红蓝格的染色方式有3034种，而3x3的情况则是22种。

Infinity

这个问题的一般情况估计没有显式表达。特别地，当颜色数等于棋盘阶数时，就是拉丁方了，而拉丁方的种类数也是没有显示表达，甚至连递推公式都没有。
见Douglas S. Stones的论文The many formulae for the number of Latin rectangles
combinatorics.org/ojs/index.php/eljc/article/view/v17i1a1/pdf