4 个 A 国人、4 个 B 国人、4 个 C 国人排成一列，同国人不得相邻，共有几种排法？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

4個美國人，4個台灣人，4個日本人排成一列，且同一國的人不得相鄰

請問有幾種排法？

luyuanhong

下面是我过去在《数学中国》发表过的一个帖子：

fungarwai

clc;clear;
a=[1;2;3];
for t=1:11
        temp=[];
        for i=1:size(a,1)
                for k=1:3
            l=length(find(a(i,: )==k));
                        if(a(i,end)~=k && l<=3)
                temp=[temp;a(i,: ) k];
                        end
                end
        end
        a=temp;
end
size(a,1)

ans =

        1092

luyuanhong

谢谢楼上 fungarwai 的解答。我已将此帖转贴到“陆老师的《数学中国》园地”。

天山草

当最左边与最右边的人可以是同一国籍时，答案为 1092；若最左边与最右边的人不能是同一国籍时，答案为804。
    本人是用 VB 编程算的。编程思路是：
编程方法：用四个 1，四个 2，四个 3 代表 12 个分属于三个国籍的人。他们站成一排体现出一个由四个 1、四个 2、四个 3 组成的 12 位数。
无论这些人如何站排，他们反映的 12 位数一定介于 111111111111 与 333333333333 之间。
因此可以采用类似三进制的方法，从最小的数 111111111111 每次加 1，逢 4 进位且本位减 3，一直加到最大的数 333333333333 为止。总共得到 531441 个由 1 至 3 组成的 12 位的“三进制”数。从中筛选出符合下列条件的数：① 相邻数字不相等；②每个数中的 1、2、3 各有 4 个。
   符合上述条件的数共有 1092 个。也就是说，共有 1092 种站队方法。
   编程技巧：12 位数的长度超过了 Long（长整型，最大 2147483647）的限制，因此采用字符串的方式。字符串加 1 时，1 不必加引号。
   本程序运行时间约 5 秒钟。

程序如下：
Open "12 人站队方法.txt" For Output As #1   
     x = "111111111111"         '最小的 12 位数大于 111111111111。最大的小于 333333333333。
     n = 0
     For i = x To x + 1000000   '实际上只有 531441 个循环。
         x = x + 1        '从最小的数字开始依次加 1，把不符合要求的去掉，符合要求者写入文件。
        For j = 12 To 2 Step -1    '将字符串变换成“三进制”串(由1，2，3 组成，不是由 0，1，2 组成)
         If Mid(x, j, 1) = 4 Then
           Mid(x, j, 1) = 1
           Mid(x, j - 1, 1) = 1 + Mid(x, j - 1, 1)
         End If
        Next j
        If Mid(x, 1, 1) = 4 Then GoTo 999   '控制结束的语句
        '以下筛选出符合要求的字串：
          For k = 1 To 11
          If Mid(x, k, 1) = Mid(x, k + 1, 1) Then GoTo 222  '相邻位上的数码不能相同。
          Next k
        m1 = 0: m2 = 0      '统计该字符串中有几个 1，几个 2。
        For k = 1 To 12
          If Mid(x, k, 1) = 1 Then m1 = m1 + 1
          If Mid(x, k, 1) = 2 Then m2 = m2 + 1
        Next k
          If m1 = 4 And m2 = 4 Then
            GoTo 111
            Else
            GoTo 222
          End If
111:  n = n + 1
       Print #1, n; "=>"; Trim(x)
222:  Next i
999:  Close
      End Sub

运行结果：

1 =>121213132323
2 =>121213231323
3 =>121213232313
4 =>121231231323
5 =>121231232313
6 =>121231312323
7 =>121231313232
8 =>121231321323
9 =>121231323123
10 =>121231323132
11 =>121231323213
12 =>121231323231
13 =>121232131323
14 =>121232132313
15 =>121232312313
16 =>121232313123
17 =>121232313132
18 =>121232313213
19 =>121232313231
20 =>121232321313
21 =>121232323131
22 =>121312132323
23 =>121312312323
……………………………………
1076 =>323212131312
1077 =>323212131321
1078 =>323212132131
1079 =>323212312131
1080 =>323212313121
1081 =>323213121213
1082 =>323213121231
1083 =>323213121312
1084 =>323213121321
1085 =>323213123121
1086 =>323213131212
1087 =>323213132121
1088 =>323213212131
1089 =>323213213121
1090 =>323231212131
1091 =>323231213121
1092 =>323231312121
------------------------------------------------

天山草

飘飘说："4 个 A 国人、4 个 B 国人、4 个 C 国人围成一圈跳舞，同国人不得相邻，共有几种围法？ （答案为804种。）"
-----------------------------------
飘飘说得应该没错。至所以要考虑最左边与最右边的人不同国籍，就是想让他们首尾连接成一个圈圈。不过这样出题可能造成两种不一样的理解，例如，1 个 A，1 个 B，1 个 C 围成一圈，算是 2 种围法呢，还是 6 种呢？有点说不清。如果强调这个圆圈有【方向性】，那是 6 种。如果不管【方向性】，那三人原地旋转着跳舞，那就成 2 种了。