【转帖】由红球、蓝球组成的金字塔有几种建造方案？

TSC999

有大小相同的红球 15 个，蓝球 21个（共36个）。
将它们排成一个金字塔，如下图。要求如下：
（1）最上面一个球，最下面 8 个球，共排 8 层；
（2）最下层红球、蓝球各 4 个；
（3）红球下面的两个球，颜色必须相同（都是红球或者都是蓝球）；
（4）蓝球下面的两个球，颜色必须不同（一个红球，一个蓝球)。

问：共有几种不同的排列方案？（下图是其中一个符合要求的方案）

zhcosin

具体结果是多少尚没得出，我只有一个思路，但是还有些问题要解决
解答：因为每一层的相邻小球的颜色是否一样就决定了上一层相应小球的颜色，所以整个图案完全由最底层的小球排列所决定，我们来讨论最底层的排列是如何决定整个金字塔中的红球和蓝球数目的，然后由给定的数字 15 和 21 看看对底层的排列有什么限制条件，进而计算符合这限制条件的排列个数就可以了。

规则（3）和（4）非常符合 1 和 -1 的乘法规则，所以约定用 1 表示红球，用 -1 表示蓝球，于是每一层中的数，等于它脚下两个数之乘积。我们假设最底层的排列是 $a_1, a_2, \ldots, a_8, a_i=1$ 或 $a_i=-1$ ，并且其中有 4 个为 1 ，另外 4 个为 -1 ，那么倒数第二层的数显然就是
$$
a_1 a_2, a_2 a_3, \ldots, a_7 a_8
$$

而倒数第三层则是
$$
a_1 a_2^2 a_3, a_2 a_3^2 a_4, \ldots, a_6 a_7^2 a_8
$$

依次下去，会发现每一层中的数，都是最底层中各数的一些乘积，我们假定倒数第 $m$ 层的第 $k$ 个数是
$$
a_1^{r_{k 1}} a_2^{r_{k 2}} \ldots a_8^{r_{k 8}}
$$

那么显见最底层的各数的指数是
$$
\left(\begin{array}{llll}
1 & 0 & \cdots & 0
\end{array}\right),\left(\begin{array}{llll}
0 & 1 & \cdots & 0
\end{array}\right), \cdots,\left(\begin{array}{llll}
0 & 0 & \cdots & 1
\end{array}\right)
$$

而倒数第二层则是
$$
\left(\begin{array}{lllllllll}
1 & 1 & 0 & \cdots & 0
\end{array}\right),\left(\begin{array}{llllllll}
0 & 1 & 1 & \cdots & 0
\end{array}\right), \cdots,\left(\begin{array}{lllll}
0 & 0 & \cdots & 1 & 1
\end{array}\right)
$$

为了便于表示这个过程，我们把这些指数写进一个矩阵里，对于最底层，这个矩阵
$$
\left(\begin{array}{rrrr}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots \\
0 & 0 & \cdots & 1
\end{array}\right)
$$

共有 8 行，倒数第二层的矩阵是
$$
\left(\begin{array}{cccccc}
1 & 1 & 0 & \cdots & 0 & 0 \\
0 & 1 & 1 & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots & & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 1 & 1
\end{array}\right)
$$

共有 7 行，如此这般，每一层的矩阵都将比下一层的矩阵行数少一，而且它的某一行，是由它下面那一层的矩阵的对应两行之和，比如说，倒数第三层的矩阵的第 4 行，是倒数第二层的矩阵的第 4 行和第 5 行相加而得到的。容易发现这样加下去，跟联系上二项式系数了，比如说倒数第三层的矩阵就是这样的
$$
\left(\begin{array}{cccccc}
1 & 2 & 1 & \cdots & 0 & 0 \\
0 & 1 & 2 & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots & & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 2 & 1
\end{array}\right)
$$

每一行都是 $1,2,1$ 不断向后轮换直到触尾，那么最顶层的矩阵就将是
$$
\left(\begin{array}{llllll}
1 & C_7^1 & C_7^2 & \cdots & C_7^6 & 1
\end{array}\right)
$$
于是最顶层的数是 $a_1^1 a_2^7 a_3^{21} a_4^{35} a_5^{35} a_6^{21} a_7^7 a_8^1$ ，可见是偶数，所以最底层一定是红球。
所以倒数第 $m$ 层的矩阵中的非零元素是 $1, C_m^1, C_m^2, \ldots, C_m^m$ 及其向后轮换，明确的写出来就是
$$
\left(\begin{array}{l}
1 & C_m^1 & C_m^2 & \cdots & C_m^m & 0 & \cdots & 0 & 0 \\
0 & 1 & C_m^1 & \cdots & C_m^{m-1} & 1 & \cdots & 0 & 0 \\
\vdots & & \vdots & \vdots & & \vdots & \vdots & & \vdots \\
0 & 0 & 0 & \cdots & & \cdots & \cdots & C_m^{m-1} &1 &
\end{array}\right)
$$

模型建立起来了，然后接下来是计算金字塔中有多少是 1 ，有多少是 -1 ，这个从这个模型来看，似乎并不容易求。

乌贼

没细想，我的思路正相反，自上而下，不知可否

TSC999

回复 2# zhcosin

金字塔的结构取决于底层的 4 个红球、4 个蓝球如何排列。对极了！支持一下。

TSC999

回复 3# 乌贼


    自上而下考虑，一开始还好办，越往下层可能性越多。既要考虑红球（或蓝球）的个数，又要考虑最底层红球必须是 4 个。

游客

总共就4种符合要求，第8层颜色可互换。

realnumber

free pasacl程序找的，应该是26个解，只显示最下层,红色偶数0，蓝色是奇数1
01001101
01011110
01101110
01101111
01110001
01110110
01111010
01111011
10001110
10010111
10011011
10011101
10100111
10101101
10110010
10110101
10111001
11000111
11001011
11010011
11011001
11011110
11100011
11100101
11101001
11110110

1. var
2. a:array[1..7,1..7]of integer;
3. k,i,j,b1,b2,b3,b4,b5,b6,b7,b8 :integer;
4. begin
5.   for b1:=0 to 1 do
6.    for b2:=0 to 1 do
7.     for b3:=0 to 1 do
8.      for b4:=0 to 1 do
9.       for b5:=0 to 1 do
10.        for b6:=0 to 1 do
11.         for b7:=0 to 1 do
12.          for b8:=0 to 1 do
13.           begin
14.           k:=0;
15.           if b1 mod 2=0 then k:=k+1;
16.           if b2 mod 2=0 then k:=k+1;
17.           if b3 mod 2=0 then k:=k+1;
18.           if b4 mod 2=0 then k:=k+1;
19.           if b5 mod 2=0 then k:=k+1;
20.           if b6 mod 2=0 then k:=k+1;
21.           if b7 mod 2=0 then k:=k+1;
22.           if b8 mod 2=0 then k:=k+1;
23.           a[7,1]:=b1+b2;
24.           a[7,2]:=b2+b3;
25.           a[7,3]:=b3+b4;
26.           a[7,4]:=b4+b5;
27.           a[7,5]:=b5+b6;
28.           a[7,6]:=b6+b7;
29.           a[7,7]:=b7+b8;
30.            for i:=1 to 7 do
31.            if a[7,i] mod 2=0 then k:=k+1;
32.            for i:=6 downto 1 do
33.             for j:=1 to i  do
34.             begin
35.             a[i,j]:=a[i+1,j]+a[i+1,j+1];
36.             if a[i,j] mod 2=0 then k:=k+1;
37.            end;
38.            if k=15 then writeln(b1,b2,b3,b4,b5,b6,b7,b8);
39.           end;
40.           end.

Copy the Code

kuing

回复 7# realnumber

你忘了第（2）条要求。

PS、程序输出的结果不能复制出来吗

realnumber

修改了1楼问题的第一行  有大小相同的红球 15 个，蓝球 21个（共36个）
改为红球m个(0<=m<=36)
结果如下
0  0
1  0
2  0
3  0
4  0
5  0
6  0
7  0
8  0
9  0
10  0
11  0
12  3
13  0
14  9
15  26
16  42
17  60
18  40
19  18
20  15
21  6
22  15
23  12
24  0
25  6
26  0
27  0
28  3
29  0
30  0
31  0
32  0
33  0
34  0
35  0
36  1

1. var
2. a:array[1..7,1..7]of integer;
3. k,i,j,m,n,b1,b2,b3,b4,b5,b6,b7,b8 :integer;
4. begin
5. for m:=0 to 36 do
6.   begin
7.   n:=0;
8.   for b1:=0 to 1 do
9.    for b2:=0 to 1 do
10.     for b3:=0 to 1 do
11.      for b4:=0 to 1 do
12.       for b5:=0 to 1 do
13.        for b6:=0 to 1 do
14.         for b7:=0 to 1 do
15.          for b8:=0 to 1 do
16.           begin
17.           k:=0;
18.           if b1 mod 2=0 then k:=k+1;
19.           if b2 mod 2=0 then k:=k+1;
20.           if b3 mod 2=0 then k:=k+1;
21.           if b4 mod 2=0 then k:=k+1;
22.           if b5 mod 2=0 then k:=k+1;
23.           if b6 mod 2=0 then k:=k+1;
24.           if b7 mod 2=0 then k:=k+1;
25.           if b8 mod 2=0 then k:=k+1;
26.           a[7,1]:=b1+b2;
27.           a[7,2]:=b2+b3;
28.           a[7,3]:=b3+b4;
29.           a[7,4]:=b4+b5;
30.           a[7,5]:=b5+b6;
31.           a[7,6]:=b6+b7;
32.           a[7,7]:=b7+b8;
33.            for i:=1 to 7 do
34.            if a[7,i] mod 2=0 then k:=k+1;
35.            for i:=6 downto 1 do
36.             for j:=1 to i  do
37.             begin
38.             a[i,j]:=a[i+1,j]+a[i+1,j+1];
39.             if a[i,j] mod 2=0 then k:=k+1;
40.            end;
41.            if k=m then n:=n+1;
42.           end;
43.           writeln(m,'  ',n);
44.       end;
45.           end.

Copy the Code

realnumber

回复 8# kuing


    没看见（2），9楼结果也是没看到（2），这样6楼结果是对的。
程序结果输入到文本文件，怕麻烦没编写，语句忘了，懒得查

kuing

回复 10# realnumber

直接在你现在输出的界面上右键不能复制咩？

realnumber

试了下，不能，我其实也不熟悉

zhcosin

回复 12# realnumber
不能复制内容的终端恐怕这世界上就只有 Windows 的 cmd 了，其实 cmd 也是可以复制的，在窗口左上角图标上右击，选择“标记”，然后就可以复制了，只是不太好使，微软的东西嘛，就这鸟样。。。。

色k

回复 13# zhcosin

右键，选择标记，左键拖选内容，再点右键，此时已经复制了所选内容。

zhcosin

回复 14# 色k
恩，一点都不好用，跟记事本里的随意选择复制差远了。

realnumber

试了下，标记的办法，果然可行
又学了一招，谢谢

TSC999

下面是用 mathematica 写的程序：

1. Clear["Global`*"];
2. n = 0;
3. n1 = 21; (* 蓝球总数 *)
4. w = 1; While[w <= 70,
5. c[8] = {1}; c[7] = {1, 1}; c[6] = {1, 1, 1}; c[5] = {1, 1, 1, 1};
6. c[4] = {1, 1, 1, 1, 1};
7. c[3] = {1, 1, 1, 1, 1, 1}; c[2] = {1, 1, 1, 1, 1, 1, 1};
8. c[1] = {1, 1, 1, 1, 1, 1, 1, 1};
9. aa = Permutations[{1, 1, 1, 1, 2, 2, 2, 2}];
10. c[1] = aa[[w]];
11. j = 1; While[j <= 7,
12.   i = 1; While[i <= 8 - j,
13.    If[Part[c[j], i] == Part[c[j], i + 1],
14.     c[j + 1] = ReplacePart[c[j + 1], 2, i]];
15.    If[Part[c[j], i] != Part[c[j], i + 1],
16.     c[j + 1] = ReplacePart[c[j + 1], 1, i]];
17.    i++]; j++];
18. s = Tally[Join[c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8]]] ;
19. s1 = s[[1]];    (* 共有多少个 1 *)
20. If[s1[[2]] == n1, n = n + 1; Print[c[1]]]; (* 对称的图案不计入的方案数目 *)
21. w++;
22. ]
23. If[n == 0, Print["无解！"], Print["n = ", n]];

Copy the Code

运行结果（对称的图案不计入）：

{1,2,1,1,2,2,1,2}

{1,2,2,2,1,1,1,2}

n = 2

如果对称图形也计入，那么程序的最后几句要改成：

1. Join[c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8]];
2. s1 = s[[1]];   (* 共有多少个 1 *)
3. s2 = s[[2]];
4. If[s1[[2]] == n1 || s2[[2]] == n1 , n = n + 1;
5.   Print[c[1]]];(* 对称的图案也计入的方案数目 *)
6. w++;
7. ]
8. If[n == 0, Print["无解！"], Print["n = ", n]];

Copy the Code

这样，上述程序的运行结果将是：

{1,2,1,1,2,2,1,2}

{1,2,2,2,1,1,1,2}

{2,1,1,1,2,2,2,1}

{2,1,2,2,1,1,2,1}

n = 4

【说明】程序上述输出结果，说的是最底层的排列方法。底层一旦确定，上面各层就随之确定了。