悠闲数学娱乐论坛(第2版)'s Archiver

Tesla35 发表于 2017-12-10 10:17

组合计数

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

student_qwh 发表于 2017-12-10 11:02

13

student_qwh 发表于 2017-12-10 11:03

不知对不对

student_qwh 发表于 2017-12-10 11:04

好像不对,等等

Tesla35 发表于 2017-12-10 11:04

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=24443&ptid=5048]3#[/url] [i]student_qwh[/i] [/b]

好像听说答案是102

student_qwh 发表于 2017-12-10 11:06

[i=s] 本帖最后由 student_qwh 于 2017-12-10 11:11 编辑 [/i]

26种

student_qwh 发表于 2017-12-10 11:09

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

student_qwh 发表于 2017-12-10 11:09

[i=s] 本帖最后由 student_qwh 于 2017-12-10 11:11 编辑 [/i]

共26种

student_qwh 发表于 2017-12-10 11:10

这个,有点尴尬

student_qwh 发表于 2017-12-10 11:29

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

realnumber 发表于 2019-2-15 11:34

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=24450&ptid=5048]10#[/url] [i]student_qwh[/i] [/b]

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

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

Infinity 发表于 2019-2-15 16:07

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

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

realnumber 发表于 2019-2-28 15:34

[quote]回复  student_qwh

好像听说答案是102
[size=2][color=#999999]Tesla35 发表于 2017-12-10 11:04[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=24445&ptid=5048][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
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.

业余的业余 发表于 2019-3-2 06:28

[i=s] 本帖最后由 业余的业余 于 2019-3-2 22:21 编辑 [/i]

手工数法, 不考虑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 发表于 2019-4-22 11:46

[quote]回复  student_qwh

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

问题若改为$4\times 4$又怎么办?或增加为3色? ...
[size=2][color=#999999]realnumber 发表于 2019-2-15 11:34[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=29879&ptid=5048][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
这个问题值得思考,不过结果就变得更多了。比如2种颜色染3x3虽然只有102种,但变为4x4时,结果激增至22874种。[code]n = 4;
u = ArrayReshape[Tuples[{1, -1}, n^2], {2^(n^2), n, n}]; v =
Select[u,
  FreeQ[Total[#, {1}], n] && FreeQ[Total[#, {1}], -n] &&
    FreeQ[Total[#, {2}], n] && FreeQ[Total[#, {2}], -n] &];
v // Length
(* 绘制前16个结果 *)
ArrayPlot[#, ColorRules -> {1 -> LightRed, -1 -> LightBlue},
   ImageSize -> Tiny, Mesh -> All, Frame -> None,
   FrameTicks -> None] & /@ v[[1 ;; 16]][/code][attach]7183[/attach]

青青子衿 发表于 2019-4-22 18:47

[i=s] 本帖最后由 青青子衿 于 2019-4-22 18:55 编辑 [/i]

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30964&ptid=5048]15#[/url] [i]Infinity[/i] [/b]
[quote]用红蓝两种颜色给3*3方格染色,每格一种颜色,则每行每列都有红蓝格的染法有几种 ...
[size=2][color=#999999]Tesla35 发表于 2017-12-10 10:17[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=24441&ptid=5048][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
[quote]这个问题值得思考,不过结果就变得更多了。比如2种颜色染3x3虽然只有102种,但变为4x4时,结果激增至22874 ...
[size=2][color=#999999]Infinity 发表于 2019-4-22 11:46[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30964&ptid=5048][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
如果[b]不考虑题主的“每行每列都有红蓝格”[/b]的要求,就是

[组合] 两色染九宫格(旋转翻转等价)
[url]http://kuing.orzweb.net/viewthread.php?tid=5979[/url]

这个问题前些日子研究过
要么是你的代码有点问题,要么是漏了哪些判断条件~(所以多出了那么多解)
根据计数通项公式有
\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 发表于 2019-4-23 12:40

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30971&ptid=5048]16#[/url] [i]青青子衿[/i] [/b]
楼主题目并没认定旋转翻转等价,我给的程序没考虑旋转翻转等价的。

Infinity 发表于 2019-4-23 19:12

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30971&ptid=5048]16#[/url] [i]青青子衿[/i] [/b]
如果考虑旋转翻转等价,4x4方格红蓝染色,要求每行每列都有红蓝格的染色方式有3034种,而3x3的情况则是22种。

Infinity 发表于 2019-4-24 14:44

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

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.