在 2×n 的方格中，放入黑棋子，棋子不相邻的放法有几种？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，
欢迎大家一起来想想如何解答：

ataorj

先放第1列,有2*1+1种放法;[注,不放子也符合题意.+1表示不放子算一种]
第2列,有2*1+2+1=2*2+1种放法;[注,考虑与上列如何组合成新即可]
3:2*2+2+1=2*3+1
4:2*4+1
...
n:2*n+1
---------
总数=2*1+2*2+2*3+...+2*n+1=n(n+1)+1

ataorj

更正
n:2*n
---------
总数=2*1+2*2+2*3+...+2*n+n-1=n(n+2)-1

luyuanhong

[这个贴子最后由luyuanhong在 2013/10/02 06:27pm 第 2 次编辑]

ataorj

看附件,穷举法,n=4时,放法总数=3+5+7+8=23=n(n+2)-1,与我的公式相符.

luyuanhong

[这个贴子最后由luyuanhong在 2013/10/02 08:49pm 第 1 次编辑]

下面引用由ataorj在 2013/10/02 08:03pm 发表的内容：
看附件,穷举法,n=4时,放法总数=3+5+7+8=23=n(n+2)-1,与我的公式相符.

下面是 n=4 时的全部 41 个解：
（1）白白白白
      白白白白
（2）白白白白
      白白白黑
（3）白白白黑
      白白白白
（4）白白白白
      白白黑白
（5）白白白黑
      白白黑白
（6）白白黑白
      白白白白
（7）白白黑白
      白白白黑
（8）白白白白
      白黑白白
（9）白白白白
      白黑白黑
（10）白白白黑
       白黑白白
（11）白白黑白
       白黑白白
（12）白白黑白
       白黑白黑
（13）白黑白白
       白白白白
（14）白黑白白
       白白白黑
（15）白黑白黑
       白白白白
（16）白黑白白
       白白黑白
（17）白黑白黑
       白白黑白
（18）白白白白
       黑白白白
（19）白白白白
       黑白白黑
（20）白白白黑
       黑白白白
（21）白白白白
       黑白黑白
（22）白白白黑
       黑白黑白
（23）白白黑白
       黑白白白
（24）白白黑白
       黑白白黑
（25）白黑白白
       黑白白白
（26）白黑白白
       黑白白黑
（27）白黑白黑
       黑白白白
（28）白黑白白
       黑白黑白
（29）白黑白黑
       黑白黑白
（30）黑白白白
       白白白白
（31）黑白白白
       白白白黑
（32）黑白白黑
       白白白白
（33）黑白白白
       白白黑白
（34）黑白白黑
       白白黑白
（35）黑白黑白
       白白白白
（36）黑白黑白
       白白白黑
（37）黑白白白
       白黑白白
（38）黑白白白
       白黑白黑
（39）黑白白黑
       白黑白白
（40）黑白黑白
       白黑白白
（41）黑白黑白
       白黑白黑

ataorj

我的罗列遗漏了若干00

luyucheng1

ataorj

purebasic运行: ddd=1 For a=0 To 2:If aaa*a=1ebug "3位数内数数量:"+Str(m):EndIf For b=0 To 2:If a<>0 And a=b:Goto bb:EndIf:If bbb*b=1ebug "2位数内数数量:"+Str(m):bbb=0:aaa=1:EndIf For c=0 To 2:If b<>0 And b=c:Goto cc:EndIf:If ccc*c=1ebug "1位数内数数量:"+Str(m):ccc=0:bbb=1:EndIf For d=0 To 2:If c<>0 And c=d:Goto dd:EndIf:If ddd*d=1:Debug "0位数内数数量:"+Str(m):ddd=0:ccc=1:EndIf Debug Str(a)+Str(b)+Str(c)+Str(d):m+1 dd:Next:cc:Next:bb:Next:Next Debug "4位数内数数量:"+Str(m) ============= 0000 0位数内数数量:1 0001 0002 1位数内数数量:3 0010 0012 0020 0021 2位数内数数量:7 0100 0101 0102 0120 0121 0200 0201 0202 0210 0212 3位数内数数量:17 1000 1001 1002 1010 1012 1020 1021 1200 1201 1202 1210 1212 2000 2001 2002 2010 2012 2020 2021 2100 2101 2102 2120 2121 4位数内数数量:41

ataorj

大家都试验展开递推,看谁先出结果.... ============ n位内的3进制数,1和1不相邻,并且2和2不相邻,共多少个数符合? 0后可跟0,1,2;1后可跟0,2;2后可跟0,1. 规定:m1时,答案即: n~=2(n-1)~+(n-2)~ 大家都试验展开递推,看谁先出结果....