杨辉三角形

杨辉三角形，又称帕斯卡三角形、贾宪三角形、海亚姆三角形、巴斯卡三角形，是二项式系数的一种写法，形似三角形，在中国首现于南宋杨辉的《详解九章算法》得名，其在书中说明是引自贾宪的《释锁算书》，故又名贾宪三角形。前 9 行写出来如下：

《永乐大典》一页：杨辉引用贾宪《释锁算书》中的贾宪三角形

${\begin{array}{c}1\\1\quad 1\\1\quad 2\quad 1\\1\quad 3\quad 3\quad 1\\1\quad 4\quad 6\quad 4\quad 1\\1\quad 5\quad 10\quad 10\quad 5\quad 1\\1\quad 6\quad 15\quad 20\quad 15\quad 6\quad 1\\1\quad 7\quad 21\quad 35\quad 35\quad 21\quad 7\quad 1\\1\quad 8\quad 28\quad 56\quad 70\quad 56\quad 28\quad 8\quad 1\\\end{array}}$

杨辉三角形第 $n$ 层（顶层称第 0 层，第 1 行，第 $n$ 层即第 $n+1$ 行，此处 $n$ 为包含 0 在内的自然数）正好对应于二项式 $\left(a+b\right)^{n}$ 展开的系数。例如第二层 1 2 1 是幂指数为 2 的二项式 $\left(a+b\right)^{2}$ 展开形式 $a^{2}+2ab+b^{2}$ 的系数。

性质

每个数是它左上方和右上方的数的和

各条线穿过的数之和均为斐波那契数

用杨辉三角形做成的谢尔宾斯基三角形

杨辉三角形以正整数构成，数字左右对称，每行由1开始逐渐变大，然后变小，回到1。
杨辉三角形每一行的平方和在杨辉三角出现奇数次。
杨辉三角形第2的幂行所有数都是奇数^{[注 1]}，此为卢卡斯定理的特殊情况。
第 $n$ 行的数字个数为 $n$ 个。
第 $n$ 行的第 $k$ 个数字为组合数 $C_{k-1}^{n-1}$ 。
第 $n$ 行数字和为 $2^{n-1}$ ，因为第 $n$ 行是 $\left(1+1\right)^{n-1}$ 的二项展开。
第 $n$ 行的数字按顺序写下所形成的数字为 $11^{n-1}$ ，因为该数字是 $\left(10+1\right)^{n-1}$ 的二项展开。例如第二行 $11=11^{1}$ ，第三行 $121=11^{2}$ ，第四行 $1331=11^{3}$ ，第五行 $14641=11^{4}$ ，第六行 $161051=11^{5}$ （第六行之后需进位）。该规律可推广至任何进位制，例如在九进制下： $121_{9}=100_{10}$ ， $1331_{9}=1000_{10}$ 。
除每行最左侧与最右侧的数字以外，每个数字等于它的左上方与右上方两个数字之和（也就是说，第 $n$ 行第 $k$ 个数字等于第 $n-1$ 行的第 $k-1$ 个数字与第 $k$ 个数字的和）。这是因为有组合恒等式： $C_{k+1}^{n+1}=C_{k}^{n}+C_{k+1}^{n}$ 。可用此性质写出整个杨辉三角形。
如果 $n$ 为素数，则第 $\left(n+1\right)$ 行的数中除了两端的1以外均为 $n$ 的整数倍数。若 $n$ 为合数则不然。^{[注 2]}
按照该三角形的斜边以及与之平行的斜线上的数所形成的数列为第 $\left(n-1\right)$ 维度的单纯形数。即第一列全为1（0维），第二列为自然数形成的数列，第三列为三角形数形成的数列，第四列为四面体数形成的数列，第五列为五胞体数形成的数列，以此类推。
第 $p$ 行（第 $n$ 层）的所有的数的平方和为第 $\left(2p-1\right)$ 行（第 $2n$ 层）正中央的数字。可用该式得出 $\sum _{k=0}^{n}{n \choose k}^{2}={2n \choose n}$ 。例如第五行（第四层）所有的数的平方和 $1^{2}+4^{2}+6^{2}+4^{2}+1^{2}=70$ 是第九行（第八层）正中央的数字。
将三角形左端对齐之后，沿右斜45度的对角线方向（不改变三角形形状的话则需要按照中国象棋的马的走法）取得的数之和为斐波那契数。
将第奇数行正中央的数减去其左侧（或右侧）第二个数，得到的差为卡塔兰数。
将杨辉三角形中所有的奇数与所有的偶数以不同颜色涂色的话，可以形成一个类似谢尔宾斯基三角形的图形。

历史

印度手稿中使用的 Meru Prastaara (मेरु प्रस्तार)，源自宾伽罗 的公式。拉古纳特图书馆J&K手稿；公元755年

朱世杰《四元玉鉴》中的“古法七乘方图”

波斯数学家Al-Karaji和天文学家兼诗人欧玛尔·海亚姆（عمر خیام,Omar Khayyám）在10世纪都发现了这个三角形，而且还知道可以借助这个三角形找 $n$ 次根，和它跟二项式的关系。但他们的著作已不存。^[2]

11世纪北宋数学家贾宪发明了贾宪三角，并发明了增乘方造表法，可以求任意高次方的展开式系数。贾宪还对贾宪三角表（古代称数字表为“立成”）的构造进行描述。^[3]贾宪的三角表图和文字描写，仍保存在大英博物馆所藏《永乐大典》卷一万六千三百四十四。

13世纪中国南宋数学家杨辉在《详解九章算术》里解释这种形式的数表，并说明此表引自11世纪前半贾宪的《释锁算术》^[4]。

1303年元代数学家朱世杰在《四元玉鉴》卷首绘制《古法七乘方图》^[5]。

意大利人称之为“塔塔利亚三角形”（Triangolo di Tartaglia）以纪念在16世纪发现一元三次方程解的塔塔利亚。

布莱士·帕斯卡的著作Traité du triangle arithmétique（1655年）介绍了这个三角形。帕斯卡搜集了几个关于它的结果，并以此解决一些概率论上的问题，影响面广泛，Pierre Raymond de Montmort（1708年）和亚伯拉罕·棣莫弗（1730年）都用帕斯卡来称呼这个三角形。

历史上曾经独立绘制过这种图表的数学家：

Karaji 和 Omar Khayyám 波斯 10世纪（图文无存）
贾宪中国北宋 11世纪《释锁算术》（图文现存大英博物馆所藏《永乐大典》）
杨辉中国南宋 1261《详解九章算法》记载之功（图文现存大英博物馆所藏《永乐大典》）
朱世杰中国元代 1299《四元玉鉴》级数求和公式
阿尔·卡西阿拉伯 1427《算术的钥匙》（现存图文）
阿皮亚纳斯德国 1527
施蒂费尔德国 1544《综合算术》二项式展开式系数
薛贝尔法国 1545
B·帕斯卡法国 1654《论算术三角形》

中国数学家的研究

中国贾宪是贾宪三角的发明人，贾宪/杨辉称之为“释锁求廉本源”，朱世杰称之为“古法七乘方图”（1303年），明代数学家吴敬《九章详注比类算法大全》称之为“开方作法本源”（1450年）；明王文素《算学宝鉴》称之为“开方本源图”（1524年）；明代程大位《算法统宗》称之为“开方求廉率作法本源图”（1592年）。清代梅文鼎《少广拾遗》称之为“七乘府算法”（1692年）；清代孔广森《少广正负术》称之为“诸乘方乘率表”；焦循《加减乘除释》称之为“古开方本原图”；刘衡《筹表开诸乘方捷法》称之为“开方求廉率图”；项名达《象数一原》称之为“递加图”。伟烈亚力《数学启蒙》称之为“倍廉法表”；李善兰《垛积比类》称之为“三角垛表”。近代中算史家李俨称之为“巴斯噶三角形”，但根据《永乐大典》指出“巴斯噶三角形”最早由贾宪使用。^[6]。著名数学家华罗庚，在1956年写的一本通俗读物《从杨辉三角谈起》^[7]，将贾宪的《开方作法本源》称为“杨辉三角”，首次将“巴斯噶三角形”回归宋代数学家名下；此后的中学数学教科书和许多数学科普读物都跟随之^[8]。另一方面，专业的中国数学史著作，都用“贾宪三角”这个称呼。^[9]^[10]。

一个数在杨辉三角出现的次数

由1开始，正整数在杨辉三角形出现的次数为：∞,1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, ... （OEIS:A003016）。最小而又大于1的数在贾宪三角形至少出现n次的数为2, 3, 6, 10, 120, 120, 3003, 3003, ... （OEIS:A062527）

除了1之外，所有正整数都出现有限次。
只有2出现刚好一次。
6,20,70等出现三次。
出现两次和四次的数很多。
还未能找到出现刚好五次或七次的数。
120,210,1540等出现刚好六次。（OEIS:A098565）
- 因为丢番图方程
  ${n+1 \choose k+1}={n \choose k+2},$
  有无穷个解^[11]，所以出现至少六次的数有无穷多个。
- 其解答，是

n=F_{2i+2}F_{2i+3}-1,\,

k=F_{2i}F_{2i+3}-1,\,

- 其中 $F_{n}$ 表示第 $n$ 个斐波那契数（ $F_{1}=F_{2}=1$ ）。
3003是第一个出现八次的数。

编程语言实现

Julia (编程语言)

# Julia Language
function triangles(Lines)

  # 楊輝三角形
  coef = 1

  for i in 0:Lines
    global coef
    for space in 1:Lines-i
      print(" ")
    end

    for j in 0:i
      if (j==0 || i==0)
        coef = 1
      else
        coef = Int(coef * (i-j+1)/j)
      end
      print(" ",coef," ")     # 每個數字後面加上空個以利間隔數字
    end
    println()
  end
end

# Main Code
triangles(9)

Go

package main

import "fmt"

//行数
const LINES int = 10

//杨辉三角
func ShowYangHuiTriangle() {
	nums := []int{}
	for i := 0; i < LINES; i++ {
		//补空白
		for j := 0; j < (LINES - i); j++ {
			fmt.Print(" ")
		}

		for j := 0; j < (i + 1); j++ {
			var length = len(nums)
			var value int

			if j == 0 || j == i {
				value = 1
			} else {
				value = nums[length-i] + nums[length-i-1]
			}
			nums = append(nums, value)
			//每个数字后面加空格以间隔数字.
			fmt.Print(value, " ")
		}
		fmt.Println("")
	}
}
func main() {
	ShowYangHuiTriangle()
}

Java

public class TriangleArray
{
   public static void main(String[] args)
   {
      final int NMAX = 10; 
 
      // allocate triangular array
      int[][] odds = new int[NMAX + 1][];
      for (int n = 0; n <= NMAX; n++){
         odds[n] = new int[n + 1];  
 
      // fill triangular array
      
         for (int k = 0; k < odds[n].length; k++)
         {
            /*
             * compute binomial coefficient n*(n-1)*(n-2)*...*(n-k+1)/(1*2*3*...*k)
             */
            int lotteryOdds = 1;
            for (int i = 1; i <= k; i++)
               lotteryOdds = lotteryOdds * (n - i + 1) / i;
 
            odds[n][k] = lotteryOdds;
         }
      }
      // print triangular array
      for (int[] row : odds)
      {
         for (int odd : row)
            System.out.printf("%4d", odd);
         System.out.println();
      }
   }
}

Python

代码量较少的实现方式如下：

# -*- coding: utf-8 -*-
#!/usr/bin/env python
def triangles():
    L = [1]
    while True:
        yield L
        L = [sum(i) for i in zip([0]+L, L+[0])]

下面是另一种较易理解的方式：

def triangles():
    L = [1]
    S = []
    while True:
        yield L 
        L = [1] + S + [1]
        S = []
        for i in range(len(L)-1):
            S.append(L[i] + L[i+1])

Visual Basic

Private Sub Form_Click()
    N = InputBox("", "", 5)
    ReDim a(N + 1, N + 1), b(N + 1, N + 1)
    Cls
    k = 8
    For I = 1 To N
        Print String((N - I) * k / 2 + 1, " ");
        For J = 1 To I
            a(I, 1) = 1
            a(I, I) = 1
            a(I + 1, J + 1) = a(I, J) + a(I, J + 1)
            b(I, J) = Trim(Str(a(I, J)))
            Print b(I, J); String(k - Len(b(I, J)), " ");
        Next J
        Print
    Next I
End Sub

C++

//以下只有列出14行

#include<iostream>
using namespace std;

int P(int n){
	int a=1, i=1;
	while(i <= n){
		a *= i;
		i++;
	}
	return a;
}

int C(int a,int b){
	return P(a) / (P(b) * P(a - b));
}

int main(){
	for(int i = 1; i < 14; i++){
		for(int j = 1; j <= i; j++){
			cout << C(i - 1, j - 1) << " ";
		}
		cout << endl;
	}
}

注释

^ 亦即组合数 ${\binom {2^{a}-1}{b}}$ 恒为奇数，其中 $a$ 为非负整数， $b$ 为 $0,1,2,3,\cdots ,(2^{a}-1)$ 中的某一数。
^ 考虑二项式系数 ${\binom {p}{n}}={\frac {p!}{n!(p-n)!}}$ ，并限定n不为p或0，则由于分子有素数p，但分母不含p，故分子的p能保留，不被约分而除去，即 ${\binom {p}{n}}$ 恒为p的倍数^[1]。另见中一新生之梦。

参考文献

^ How is (x+y)^p≡x^p+y^p mod p for any prime number p. Mathematics Stack Exchange. 2018-09-27 [2021-04-26]. （原始内容存档于2022-03-25）（英语）.
^ Victor J. Katz, editor, The Mathematics of Egypt, Mesopotamia, China, India, and Islam, A Sourcebook. Page 518, Princeton University Press 2007.
^ 郭书春著《中国科学技术史·数学卷》第十五章《唐中叶至元中叶熟悉概论》第357页 （贾宪）创造《开发作法本源》即贾宪三角 科学出版社 2010
^ 《永乐大典》卷一万六千三百四十四
^ 朱世杰原著李兆华校证《四元玉鉴校证》卷首《古法七乘方图》第58页科学出版社 2007 中国数学史大系》第五卷 704页
^ 郭书春《中国科学技术史·数学卷》第十八章第二节《贾宪三角》，科学出版社 2010
^ Singmaster, David, "Repeated Binomial Coefficients and Fibonacci numbers", Fibonacci Quarterly, volume 13, number 4, pages 296—298, 1975.

外部链接

杨辉三角形

参见

[1] 亦即组合数 ${\binom {2^{a}-1}{b}}$ 恒为奇数，其中 $a$ 为非负整数， $b$ 为 $0,1,2,3,\cdots ,(2^{a}-1)$ 中的某一数。

[3] 考虑二项式系数 ${\binom {p}{n}}={\frac {p!}{n!(p-n)!}}$ ，并限定n不为p或0，则由于分子有素数p，但分母不含p，故分子的p能保留，不被约分而除去，即 ${\binom {p}{n}}$ 恒为p的倍数^[1]。另见中一新生之梦。

[2] How is (x+y)^p≡x^p+y^p mod p for any prime number p. Mathematics Stack Exchange. 2018-09-27 [2021-04-26]. （原始内容存档于2022-03-25）（英语）.

[4] Victor J. Katz, editor, The Mathematics of Egypt, Mesopotamia, China, India, and Islam, A Sourcebook. Page 518, Princeton University Press 2007.

[5] 郭书春著《中国科学技术史·数学卷》第十五章《唐中叶至元中叶熟悉概论》第357页 （贾宪）创造《开发作法本源》即贾宪三角 科学出版社 2010

[6] 《永乐大典》卷一万六千三百四十四

[7] 朱世杰原著李兆华校证《四元玉鉴校证》卷首《古法七乘方图》第58页科学出版社 2007 中国数学史大系》第五卷 704页

[12] 郭书春《中国科学技术史·数学卷》第十八章第二节《贾宪三角》，科学出版社 2010

[singmaster1975-13] Singmaster, David, "Repeated Binomial Coefficients and Fibonacci numbers", Fibonacci Quarterly, volume 13, number 4, pages 296—298, 1975.

[注 1]

[注 2]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[1]