四个美国人、四个日本人、四个德国人排成一列，同国籍的人不相邻的排列方法有几种？

luyuanhong

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

四個美國人，四個日本人，四個德國人排成一列，只看國籍，求同國籍不相鄰的排法有幾種?

luyuanhong

[这个贴子最后由luyuanhong在 2013/09/23 07:17pm 第 1 次编辑]

天山草

这种排列组合问题，思考起来还是比较困难的。是否可以考虑编程解决？应该可以，但是如何编程呢？如何编程最容易理解、而且不容易出错呢？

luyuanhong

下面引用由天山草在 2013/09/23 05:25pm 发表的内容： 这种排列组合问题，思考起来还是比较困难的。是否可以考虑编程解决？应该可以，但是如何编程呢？如何编程最容易理解、而且不容易出错呢？

下面是我用 Pascal（Delphi）语言编写的程序，显得比较“笨”， 但算起来还是非常快的，算出结果是 1092 ，与楼上结果一致： var i,j,s:integer; a:array[1..3] of integer; n:array[1..12] of integer; begin s:=0; for n[1]:=1 to 3 do for n[2]:=1 to 3 do for n[3]:=1 to 3 do for n[4]:=1 to 3 do for n[5]:=1 to 3 do for n[6]:=1 to 3 do for n[7]:=1 to 3 do for n[8]:=1 to 3 do for n[9]:=1 to 3 do for n[10]:=1 to 3 do for n[11]:=1 to 3 do for n[12]:=1 to 3 do begin for i:=1 to 3 do a:=0; for j:=1 to 12 do a[n[j]]:=a[n[j]]+1; if (a[1]=4) and (a[2]=4) and (a[3]=4) then if (n[1]<>n[2]) and (n[2]<>n[3]) and (n[3]<>n[4]) and (n[4]<>n[5]) and (n[5]<>n[6]) and (n[6]<>n[7]) and (n[7]<>n[8]) and (n[8]<>n[9]) and (n[9]<>n[10]) and (n[10]<>n[11]) and (n[11]<>n[12]) then s:=s+1; end; writeln(s); readln; end.

ataorj

问:12位3进制数,12位平均分配数字0,1,2;相邻数字不同的数有多少个?注:高位可为0
答:相同数字最多间隔2位,最少间隔1位
其实是如下两位并一位的"三进制数"6位
1 01,02,12 3^6=729
2 10,20,21
3 10,12,02
4 01,21,20
则答案是:
4*729=2916

ataorj

3^6=729需要改正

ataorj

1 01,02,12,新数字必须出现两次,6个元素两两相同的排列有
6!/(2!*2!*2!)=90
2 10,20,21
3 10,12,02
4 01,21,20
则答案是:
4*90=360
------------
与陆教授差异大,哪里遗漏了呢?

luyuanhong

[这个贴子最后由luyuanhong在 2013/09/24 06:03pm 第 1 次编辑]

下面引用由ataorj在 2013/09/24 11:42am 发表的内容：
1 01,02,12,新数字必须出现两次,6个元素两两相同的排列有
6!/(2!*2!*2!)=90
2 10,20,21
3 10,12,02
4 01,21,20
则答案是:
4*90=360
------------
与陆教授差异大,哪里遗漏了呢?.

例如，像 01,02,12,10,20,21 或 01,21,20,10,12,02 这样的排列就遗漏了。

ataorj

先舍弃"2",看其余8人排列:
01010101
10101010
---------
4个"2"如何插入呢:
01010101
1 占据首位,舍弃末位,3个"2"有7处空隙可钻,则(7+3-1)!/(3!(7-1)!)=84
2 占据末位,舍弃首位,则也84
3 占据首,末位,2个"2"有7处空隙可钻,则(7+2-1)!/(2!(7-1)!)=28
4 舍弃首,末位,4个"2"有7处空隙可钻,则(7+4-1)!/(4!(7-1)!)=210
10101010
...
---------
2*(84+84+28+210)=812
========
连续3,4个"2"若夹住2,3个非2,则"0""1"可互换位置
连续3,4个"1"...
...
这些情形各不同,所以不会重复统计吧...
这些真麻烦,我放弃思考.

天山草

陆教授在 4 楼给出的程序，思路很好，很清晰。定义一个 n 数组表示 12 个位置，每个位置可以放置 1，2，3 三个数。相邻位置的数字不能是一样的，有多少种放置方法？
我也将照此思路写个其它语言的程序。