杨辉三角(三角形矩阵)

帕斯卡三角形（三角形矩阵）一般指本词条

杨辉三角，是二项式係数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所着的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623—-1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。

杨辉三角是中国数学史上的一个伟大成就。

基本介绍

中文名：杨辉三角
外文名：Pascal’s Triangle
别称：贾宪三角形、帕斯卡三角形
表达式：几何
提出者：杨辉
提出时间：约1050年
套用学科：数学，计算机
适用领域範围：数学，计算机
使用人群：中学生、大学生，编程专家、等等
发现者：杨辉

简介

杨辉三角，是二项式係数在三角形中的一种几何排列。在欧洲，这个表叫做帕斯卡三角形。帕斯卡（1623—-1662）是在1654年发现这一规律的，比杨辉要迟393年，比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式係数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。

概述

前提：每行端点与结尾的数为1.
（与上图中的n不同，这里第一行定义为n=1）

每个数等于它上方两数之和。
每行数字左右对称，由1开始逐渐变大。
第n行的数字有n项。
第n行的m个数可表示为 C(n-1， m-1)，即为从n-1个不同元素中取m-1个元素的组合数。
第n行的第m个数和第n-m+1个数相等，为组合数性质之一。
每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。
(a+b) ⁿ的展开式中的各项係数依次对应杨辉三角的第(n+1)行中的每一项。
将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第4n+1个斐波那契数；将第2n行第2个数(n>1)，跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。
将第n行的各数值，分别乘以10的列数m-1次方，然后把这些数值相加的和等于11的n-1次方。例子：第11行数分别为1,10,45,120,210,252,210,120,45,10,1，则11^10 = 1*10^0+10*10^1+45*10^2+…+1*10^10 =25937424601

套用

性质5和性质7是杨辉三角的基本性质，是研究杨辉三角其他规律的基础。与杨辉三角联繫最紧密的是二项式乘方展开式的係数规律，即二项式定理。例如在杨辉三角中，第3行的三个数恰好对应着两数和的平方的展开式的每一项的係数（性质 8），第4行的四个数恰好依次对应两数和的立方的展开式的每一项的係数，即，以此类推。又因为性质5：第n行的m个数可表示为C(n-1,m-1)，即为从n-1个不同元素中取m-1个元素的组合数。因此可得出二项式定理的公式为：因此，二项式定理与杨辉三角形是一对天然的数形趣遇，它把数形结合带进了计算数学。求二项式展开式係数的问题，实际上是一种组合数的计算问题。用係数通项公式来计算，称为“式算”；用杨辉三角形来计算，称作“图算”。

数在杨辉三角中的出现次数

由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）因为丢番图方程有无穷个解，所以出现至少六次的数有无穷个多。解为，其中F
_n表示第n个斐波那契数（F
₁=F
₂=1）。 3003是第一个出现八次的数。

历史沿革

北宋人贾宪约1050年首先使用“贾宪三角”进行高次开方运算。杨辉，字谦光，南宋时期杭州人。在他1261年所着的《详解九章算法》一书中，辑录了如上所示的三角形数表，称之为“开方作法本源”图，并说明此表引自11世纪中叶（约公元1050年）贾宪的《释锁算术》，并绘画了“古法七乘方图”。故此，杨辉三角又被称为“贾宪三角”。元朝数学家朱世杰在《四元玉鑒》（1303年）扩充了“贾宪三角”成“古法七乘方图”。义大利人称之为“塔塔利亚三角形”（Triangolo di Tartaglia）以纪念在16世纪发现一元三次方程解的塔塔利亚。在欧洲直到1623年以后，法国数学家帕斯卡在13岁时发现了“帕斯卡三角”。布莱士·帕斯卡的着作
Traité du triangle arithmétique（1655年）介绍了这个三角形。帕斯卡蒐集了几个关于它的结果，并以此解决一些机率论上的问题，影响面广泛，Pierre Raymond de Montmort（1708年）和亚伯拉罕·棣·美弗（1730年）都用帕斯卡来称呼这个三角形。 21世纪以来国外也逐渐承认这项成果属于中国，所以有些书上称这是“中国三角形”（Chinese triangle）历史上曾经独立绘製过这种图表的数学家有：

贾宪中国北宋 11世纪《释锁算术》
杨辉中国南宋1261《详解九章算法》记载之功
朱世杰中国元代 1299《四元玉鑒》级数求和公式
阿尔·卡西阿拉伯 1427《算术的钥匙》
阿皮亚纳斯德国 1527
米歇尔.斯蒂费尔德国 1544《综合算术》二项式展开式係数
薛贝尔法国 1545
B·帕斯卡法国 1654《论算术三角形》

其实，中国古代数学家在数学的许多重要领域中处于遥遥领先的地位。中国古代数学史曾经有自己光辉灿烂的篇章，而杨辉三角的发现就是十分精彩的一页。

在编程中实现

杨辉三角在编程实现中较为容易。最常见的算法便是用上一行递推计算；也有运用和组合的对应关係而使用阶乘计算的，然而后者速度较慢且阶乘容易溢出。编程的输出大多相类，此处并不过多添加截图。 C、C++、C#、Java 语言之间的语法也大多相类，因此这里也不会将每一种算法都在这些语言中各实现一遍。要在这些语言的版本间修改，实际上只需注意一些简单的语法和函式名称的改变，如 C 的 int yh[M][M] 应改写为 Java 的 int[][] yh = new int[M][M]、C# 的 int[,] yh=new int[M,M]；C printf 应使用 Java 的 System.out.print、C# 的 Console.Write 、C++ 中更智慧型的 cout 来替换。

C++

#include<iostream>#include<iomanip>using namespace std;int main(){    const int n = 15;    const int m = 2 * n-1;    int arr[n + 1][m] = { 0 };    for (int i = 0; i < n; i++)    {        arr[i][n - i- 1] = 1;        arr[i][n + i -1] = 1;    }    for (int i = 2; i < n; i++)    {        for (int j = n - i + 1; j < n-2+i; j = j + 2)            arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j + 1];    }    int p;    for (int i = 0; i < n; i++)    {        for (int j = 0; j < n - i - 1; j++)            cout << "    ";        p = 1;        for (int j = n - i - 1; p < i + 2; j = j + 2)        {            cout << setw(4) << arr[i][j] << "    ";            p = p + 1;        }        cout << endl;    }    return 0;}

Bash

#! /bin/bash# 用法：./pasTrig [个数]，若不指明个数为 5。# 填充指定个数的空格pad(){ for ((k=0;k<$1;k++)); do echo -n ' '; done; }# 层数和新旧层lyrs=${1-5}prev[0]=1curr[0]=1 # 接下来每行第一个始终为一，无需重複赋值# 执行pad $(((lyrs-1)*2))echo 1for ((i=2; i<=lyrs; i++)); do # 略过 1，已处理  pad $(((lyrs-i)*2)) # 填充空格，注意这里不会怎幺顾及三位以上的数，即第 14 层开始会混乱  curr[i]=1  printf '%-4d' ${curr[0]}  for ((j=1; j<i-1; j++)); do # 首尾极值已处理，略过    ((curr[j]=prev[j-1]+prev[j]))    printf '%-4d' ${curr[j]}  done  printf '%-4d\n' ${curr[i]} # 最后一个和换行  # 搬家    prev=(${curr[*]})    done

Bash 输出杨辉三角并使用 nl 表明行号

C#

class Program{  public int yanghui(int value)  {  if(value<3) return 1;  int[,]arry=new int[value,value];  Console.WriteLine("数组为：");  for(int i=0;i<value;i++)  {    string str="";    str=str.PadLeft(value-i);    Console.Write(str);    for(int j=0;j<=i;j++)    {      if(i==j||j==0)        arry[i,j]=1;      else        arry[i,j]=arry[i-1,j-1]+arry[i-1,j];      Console.Write(arry[i,j]+"");    }    Console.WriteLine();  }} static void Main(string[]args){  Program p=new Program();  Console.WriteLine("请输入数组值：");  if (p.yanghui(Convert.ToInt16(Console.ReadLine())))    Console.WriteLine("输入数值必须大于3");  Console.Readkey();} }

C

以下的代码均用标準 C 语言写成，可以被包括 MSVC（含 VC6）、GCC 的多种 C 编译器编译。这个算法使用只行列位置和左侧的数值算出数值：

/* yh-rt1.c - 时间和空间最优算法 */#include <stdio.h>#include <stdlib.h>int main(){    int s = 1, h;                    // 数值和高度    int i, j;                        // 循环计数    scanf("%d", &h);                 // 输入层数    printf("1\n");                   // 输出第一个 1    for (i = 2; i <= h; s = 1, i++)         // 行数 i 从 2 到层高    {        printf("1 ");                // 第一个 1        for (j = 1; j <= i - 2; j++) // 列位置 j 绕过第一个直接开始循环            //printf("%d ", (s = (i - j) / j * s));            printf("%d ", (s = (i - j) * s / j));        printf("1\n");               // 最后一个 1，换行    }    getchar();                       // 暂停等待    return 0;}

默认求直角三角形，可通过注释的开关或使用编译器的 -D 定义开关调节等腰三角形和菱形输出。如果觉得複杂，可按照 define 使用的情况剔除因不符合 ifdef 条件从而未启用的代码之后阅读。
默认状态下不启用金字塔和菱形的输出 这个算法创建了一个二维数组，并且通过上一行的数值求当前行。在反过来再次列印时，这个程式会使用以前算好的值，从而节省了重複叠代的时间。

/* yh-2d.c - 二维数组叠代 */#include<stdio.h>#define M 10       // 行数// #define PYRAMID // 金字塔，会额外填充空格// #define REVERSE // 反向再来一次，得到菱形int main(void){  int a [M][M], i, j;   // 二维数组和循环变数，a[行][列]  for (i = 0; i<M; i++) // 每一行  {#ifdef PYRAMID    for (j = 0;j <= M-i; j++) printf ("  ");#endif // 填充结束    for (j = 0; j <= i; j++) // 赋值列印      printf("%4d", (a[i][j] = (i == j || j == 0) ? 1 : // 首尾置 1        a[i - 1][j] + a[i - 1][j - 1] )); // 使用上一行计算    printf("\n");  }#ifdef REVERSE  for(i = M-2; i >= 0; i--)  {#ifdef PYRAMID    for (j = 0;j <= M - i; j++) printf("  ");#endif // 填充结束    for (j = 0;j <= i; j++) printf("%4d",a[i][j]); // 直接使用以前求得的值    printf("\n");  }#endif // 菱形结束  getchar(); // 暂停等待}

这一个使用大数组写成，风格更接近教科书上的 VC6 代码。

/* yh-rt3.c - 较为暴力的大数组 */#include <stdio.h>#include "string.h"int main(){    int a[10000];        //容器，由n*(n+1)/2<=10000可知，n<=141    int b,CR,i;        //b为当前行数，CR为要求显示的行数，i为循环数    printf("请输入要显示的行数（3~141）：");    scanf("%d",&CR);    YHSJ(CR);    a[1]=a[2]=1;        //前两行数值少且全为1，故直接输出    printf("%d\n",a[1]);    printf("%d %d\n",a[1],a[2]);    for(b=3;b<=CR;b++)        //从第三行开始判断    {        for(i=b;i>=2;i--)        //从倒数第一个数开始加          a[i]=a[i]+a[i-1];        //杨辉三角的规律，没有值的数组默认为0        for(i=1;i<=b;i++)        //显示循环          printf("%d ",a[i]);        printf("\n");        // 换行    }    return 0;}

这个版本使用伫列的方式输出。

#include <stdio.h>#include <stdlib.h>#define EMPTY 1#define OFLOW 2#define INVAL 3#define MAX_Q 100typedef int DataType; // 数据类型选择typedef struct{ DataType elem[MAX_Q]; int front, rear; } LinkQ;// 伫列及检查宏#define InitQ(Q) LinkQ Q; Q.front=Q.rear=-1;#define _EQ(Q,e) Q.elem[(Q.rear=(Q.rear+1)%MAX_Q)]=e#define EnQ(Q,e) if((Q.rear+1)%MAX_Q==Q.front) Exit(OFLOW,"Overflow"); _EQ(Q,e)#define DeQ(Q,e) e=Q.elem[(Q.front=(Q.front+1)%MAX_Q)]#define Front(Q) Q.elem[(Q.front+1)%MAX_Q]// 退出int Exit(int err, char msg[]) { puts(msg); exit(err); return err; }int main(void){    int n=1,i,j,k,t;    InitQ(Q);    printf("please enter a number:");    scanf("%d",&n);    if (n<=0) {        printf("ERROR!\n");        exit(INVAL);    }    for(i=0;i<n;i++) printf(" ");    puts("1"); EnQ(Q,1); EnQ(Q,1);    for(i=1;i<n;i++) {        for(k=0;k<n-i;k++) printf(" ");        EnQ(Q,1);        for(j=0;j<i;j++){            DeQ(Q,t);            printf("%3d ",t);            EnQ(Q,t+Front(Q));        }        EnQ(Q,1);        DeQ(Q,t);        printf("%d\n",t);    }    return 0;}

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 IEnd Sub

单击视窗在弹出输入框后输入行数后按确认就能在窗体上列印杨辉三角了

SQL

-- 使用组合的计算公式和阶乘计算杨辉三角，对大数容易溢出。create function Factorial (@count int) returns int as begin  declare @ret int,@index int  set @ret = 1 --初始值为 1  set @index = 1  while(@index <= @count) begin    set @ret = @ret * @index    set @index = @index + 1  end  return (@ret)endcreate function Combination (@num int,@count int) returns int as begin  declare @up int,@L1 int,@R1 int,@ret int  set @up = dbo.Factorial(@count)  set @L1 = dbo.Factorial(@num)  set @R1 = dbo.Factorial(@count - @num)  set @ret = @up/(@L1 * @R1)  return (@ret)endcreate function PrintRow (@num int) returns nvarchar(100) as begin  declare @i int  declare @str nvarchar(100)  set @str = ''  set @i = 1  while (@i < @num) begin    set @str = @str + replace(str(dbo.Combination(@i,@num)),' ','') + ' ,'    set @i = @i + 1  end  return (@str)endcreate proc PasTrigLines(@num int) as begin -- 主程式  declare @i int  set @i = 1  while(@i <= @num ) begin    if (@i = 0 ) print 1 + ','    else if (@i = 1) print '1,1,'    else print '1,' + dbo.PrintRow(@i) + '1,'    set @i = @i + 1  endendexec PasTrigLines 10 -- 十个

易语言

来自易语言自带的例子。以下为全文。

.版本 2.程式集 启动视窗程式集　.程式集变数 帕斯卡三角阶数, 整数型, , , 帕斯卡三角行数　.程式集变数 帕斯卡三角, 文本型, , , 形成的帕斯卡三角.子程式 __启动视窗_创建完毕' 使用算法：递归调用　' 问题：求帕斯卡（杨辉）三角　' 问题描述：取N阶的帕斯卡（杨辉）三角并显示　' 问题分析：　' 　运用递归的方法取N层帕斯卡三角，并显示。三角形边界上的数都是1，内部的每个数是位于它上面的两个数之和。　' 　假设f(row, col)表示杨辉三角的第row行的第col个元素，那幺：f(row, col) = 1 (col = 1 或者 row = col)，也就是递归的停止条件。f(row, col) = f(row - 1, col - 1) + f(row - 1, col)，也就是上一行的两个相邻元素的和。递归调用求解。　' 备注：.子程式 _计算图形按钮_被单击　.局部变数 行数, 整数型, , , 帕斯卡三角行数　.局部变数 列数, 整数型, , , 帕斯卡三角列数　.局部变数 询问返回, 整数型, , , 信息框返回的结果编辑框2.内容 = “”　帕斯卡三角 = “”　' 判断输入的值　.判断开始 (编辑框1.内容 = “”)　信息框 (“输入错误!”, 0, )　' 当数值过大时，给出提示　.判断 (到数值 (编辑框1.内容) > 20)　询问返回 = 信息框 (“您输入的数值过大，处理数据时程式将会有一段时间无回响，是否继续？”, #是否钮 + #询问图示, “请问：”)　.如果真 (询问返回 = #是钮)　' 如果确定，调用求帕斯卡三角　求帕斯卡三角 ()　.如果真结束　' 数据较小时调用求帕斯卡三角　.判断 (编辑框1.内容 ≠ “” 且 到数值 (编辑框1.内容) ≤ 20)　求帕斯卡三角 ()　.默认.判断结束　.子程式 求帕斯卡三角　.局部变数 行数, 整数型, , , 帕斯卡三角行数　.局部变数 列数, 整数型, , , 帕斯卡三角列数' 要求的帕斯卡三角的总行数　帕斯卡三角阶数 = 到数值 (编辑框1.内容) － 1　.变数循环首 (0, 帕斯卡三角阶数, 1, 行数)　.变数循环首 (0, 行数, 1, 列数)　' 取帕斯卡三角元素放到当前行里　帕斯卡三角 = 帕斯卡三角 + 到文本 (取帕斯卡三角元素 (行数 + 1, 列数 + 1)) + “,”　.变数循环尾 ()　帕斯卡三角 = 取文本左边 (帕斯卡三角, 取文本长度 (帕斯卡三角) － 1) + #换行符　' 没层需去尾都好加换行符　.变数循环尾 ()　' 显示结果　编辑框2.内容 = 帕斯卡三角　.子程式 取帕斯卡三角元素, 整数型, , 取帕斯卡三角中元素的子程式　.参数 行数, 整数型, , 帕斯卡三角行数　.参数 列数, 整数型, , 帕斯卡三角列数.如果 (列数 = 1 或 行数 = 列数)　' 每行的外围两个元素为1　返回 (1)　.否则　' 其余的部分为上一行的(行数 - 1)和(行数)元素之和　返回 (取帕斯卡三角元素 (行数 － 1, 列数 － 1) + 取帕斯卡三角元素 (行数 － 1, 列数))　.如果结束

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 n = 0; n < odds.length; n++)         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();      }   }}

PHP

<?php/* 默认输出十行，用T(值)的形式可改变输出行数 */class T{  private $num;  public function __construct($var=10) {    if ($var<3) die("值太小啦！");    $this->num=$var;  }  public function display(){    $n=$this->num;    $arr=array();  //$arr=array_fill(0,$n+1,array_fill(0,$n+1,0));    $arr[1]=array_fill(0,3,0);    $arr[1][1]=1;    echo str_pad("&nbsp;",$n*12,"&nbsp;");    printf("%3d",$arr[1][1]);    echo "<br/>";    for($i=2;$i<=$n;$i++){      $arr[$i]=array_fill(0,($i+2),0);      for($j=1;$j<=$i;$j++){        if($j==1)          echo str_pad("&nbsp;",($n+1-$i)*12,"&nbsp;");        printf("%3d",$arr[$i][$j]=$arr[$i-1][$j-1]+$arr[$i-1][$j]);        echo "&nbsp;&nbsp;";      }      echo"<br/>";    }  }}$yh=new T(); //$yh=new T(数量);$yh->display();?>

只输出数组的方式如下：

<?php$max = 10;$L = [1];var_dump($L);$L = [1,1];var_dump($L);$n = 2;while ($n <= $max - 1){    $oldL = $L;    $L[$n] = 1;    $n++;    for ($i = 1;$i <count($oldL);$i++){        $L[$i] = $oldL[$i-1] + $oldL[$i];    }    var_dump($L);}?>

Python

较为便捷，代码量较少的实现方式如下：

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

该方式用到了列表生成式，理解起来较困难，下面是另一种方式：

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

另一个不用生成器的版本：

def YangHui (num = 10):    LL = [[1]]    for i in range(1,num):        LL.append([(0 if j== 0 else LL[i-1][j-1])+ (0 if j ==len(LL[i-1]) else LL[i-1][j]) for j in range(i+1)])    return LL

杨辉三角(三角形矩阵)