杨辉三角

简介

概述

前提：每行端点与结尾的数为1.

（与上图中的n不同，这里第一行定义为n=1）

1. 每个数等于它上方两数之和。

2. 每行数字左右对称，由1开始逐渐变大。

3. 第n行的数字有n项。

4. 第n行的m个数可表示为 C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数。

5. 第n行的第m个数和第n-m+1个数相等 ，为组合数性质之一。

6. 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。

7. (a+b)^{n的展开式中的各项係数依次对应杨辉三角的第(n+1)行中的每一项。}

8. 将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第4n+1个斐波那契数；将第2n行第2个数(n>1)，跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。

9. 将第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之外，所有正整数都出现有限次，只有2出现刚好一次，6,20,70等出现三次；出现两次和四次的数很多，还未能找到出现刚好五次的数。120,210,1540等出现刚好六次。（OEIS:A098565）

因为丢番图方程

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#includeusingnamespacestd;intmain(){constintn=15;constintm=2*n-1;intarr[n+1][m]={0};for(inti=0;i
Bash
#!/bin/bash#用法：./pasTrig[个数]，若不指明个数为5。#填充指定个数的空格pad(){for((k=0;k<$1;k++));doecho-n'';done;}#层数和新旧层lyrs=${1-5}prev[0]=1curr[0]=1#接下来每行第一个始终为一，无需重複赋值#执行pad$(((lyrs-1)*2))echo1for((i=2;i<=lyrs;i++));do#略过1，已处理pad$(((lyrs-i)*2))#填充空格，注意这里不会怎么顾及三位以上的数，即第14层开始会混乱curr[i]=1printf'%-4d'${curr[0]}for((j=1;j
Bash 输出杨辉三角并使用 nl 表明行号
C#
classProgram{publicintyanghui(intvalue){if(value<3)return1;int[,]arry=newint[value,value];Console.WriteLine("数组为：");for(inti=0;i
 
C
以下的代码均用标準 C 语言写成，可以被包括 MSVC（含 VC6）、GCC 的多种 C 编译器编译。
这个算法使用只行列位置和左侧的数值算出数值：
/*yh-rt1.c-时间和空间最优算法*/#include#includeintmain(){ints=1,h;//数值和高度inti,j;//循环计数scanf("%d",&h);//输入层数printf("1\n");//输出第一个1for(i=2;i<=h;s=1,i++)//行数i从2到层高{printf("1");//第一个1for(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();//暂停等待return0;}
默认求直角三角形，可通过注释的开关或使用编译器的 -D 定义开关调节等腰三角形和菱形输出。如果觉得複杂，可按照 define 使用的情况剔除因不符合 ifdef 条件从而未启用的代码之后阅读。
默认状态下不启用金字塔和菱形的输出
这个算法创建了一个二维数组，并且通过上一行的数值求当前行。在反过来再次列印时，这个程式会使用以前算好的值，从而节省了重複叠代的时间。
/*yh-2d.c-二维数组叠代*/#include#defineM10//行数//#definePYRAMID//金字塔，会额外填充空格//#defineREVERSE//反向再来一次，得到菱形intmain(void){inta[M][M],i,j;//二维数组和循环变数，a[行][列]for(i=0;i=0;i--){#ifdefPYRAMIDfor(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#include"string.h"intmain(){inta[10000];//容器，由n*(n+1)/2<=10000可知，n<=141intb,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];//杨辉三角的规律，没有值的数组默认为0for(i=1;i<=b;i++)//显示循环printf("%d",a[i]);printf("\n");//换行}return0;}
 
这个版本使用伫列的方式输出。
#include#include#defineEMPTY1#defineOFLOW2#defineINVAL3#defineMAX_Q100typedefintDataType;//数据类型选择typedefstruct{DataTypeelem[MAX_Q];intfront,rear;}LinkQ;//伫列及检查宏#defineInitQ(Q)LinkQQ;Q.front=Q.rear=-1;#define_EQ(Q,e)Q.elem[(Q.rear=(Q.rear+1)%MAX_Q)]=e#defineEnQ(Q,e)if((Q.rear+1)%MAX_Q==Q.front)Exit(OFLOW,"Overflow");_EQ(Q,e)#defineDeQ(Q,e)e=Q.elem[(Q.front=(Q.front+1)%MAX_Q)]#defineFront(Q)Q.elem[(Q.front+1)%MAX_Q]//退出intExit(interr,charmsg[]){puts(msg);exit(err);returnerr;}intmain(void){intn=1,i,j,k,t;InitQ(Q);printf("pleaseenteranumber:");scanf("%d",&n);if(n<=0){printf("ERROR!\n");exit(INVAL);}for(i=0;i
Visual Basic
PrivateSubForm_Click()N=InputBox("","",5)ReDima(N+1,N+1),b(N+1,N+1)Clsk=8ForI=1ToNPrintString((N-I)*k/2+1,"");ForJ=1ToIa(I,1)=1a(I,I)=1a(I+1,J+1)=a(I,J)+a(I,J+1)b(I,J)=Trim(Str(a(I,J)))Printb(I,J);String(k-Len(b(I,J)),"");NextJPrintNextIEndSub
单击视窗在弹出输入框后输入行数后按确认 就能在窗体上列印杨辉三角了
SQL
--使用组合的计算公式和阶乘计算杨辉三角，对大数容易溢出。createfunctionFactorial(@countint)returnsintasbegindeclare@retint,@indexintset@ret=1--初始值为1set@index=1while(@index<=@count)beginset@ret=@ret*@indexset@index=@index+1endreturn(@ret)endcreatefunctionCombination(@numint,@countint)returnsintasbegindeclare@upint,@L1int,@R1int,@retintset@up=dbo.Factorial(@count)set@L1=dbo.Factorial(@num)set@R1=dbo.Factorial(@count-@num)set@ret=@up/(@L1*@R1)return(@ret)endcreatefunctionPrintRow(@numint)returnsnvarchar(100)asbegindeclare@iintdeclare@strnvarchar(100)set@str=''set@i=1while(@i<@num)beginset@str=@str+replace(str(dbo.Combination(@i,@num)),'','')+','set@i=@i+1endreturn(@str)endcreateprocPasTrigLines(@numint)asbegin--主程式declare@iintset@i=1while(@i<=@num)beginif(@i=0)print1+','elseif(@i=1)print'1,1,'elseprint'1,'+dbo.PrintRow(@i)+'1,'set@i=@i+1endendexecPasTrigLines10--十个
 
易语言
来自易语言自带的例子。
以下为全文。
.版本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
publicclassTriangleArray{publicstaticvoidmain(String[]args){finalintNMAX=10;//allocatetriangulararrayint[][]odds=newint[NMAX+1][];for(intn=0;n<=NMAX;n++)odds[n]=newint[n+1];//filltriangulararrayfor(intn=0;n
 
PHP
num=$var;}publicfunctiondisplay(){$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;echostr_pad(" ",$n*12," ");printf("%3d",$arr[1][1]);echo"
";for($i=2;$i<=$n;$i++){$arr[$i]=array_fill(0,($i+2),0);for($j=1;$j<=$i;$j++){if($j==1)echostr_pad(" ",($n+1-$i)*12," ");printf("%3d",$arr[$i][$j]=$arr[$i-1][$j-1]+$arr[$i-1][$j]);echo"  ";}echo"
";}}}$yh=newT();//$yh=newT(数量);$yh->display();?>
只输出数组的方式如下：
Python
较为便捷，代码量较少的实现方式如下：
#-*-coding:utf-8-*-#!/usr/bin/envpythondeftriangles():L=[1]whileTrue:yieldLL=[sum(i)foriinzip([0]+L,L+[0])]
该方式用到了列表生成式，理解起来较困难，下面是另一种方式：
deftriangles():ret=[1]whileTrue:yieldretforiinrange(1,len(ret)):ret[i]=pre[i]+pre[i-1]ret.append(1)pre=ret[:]
另一个不用生成器的版本：
defYangHui(num=10):LL=[[1]]foriinrange(1,num):LL.append([(0ifj==0elseLL[i-1][j-1])+(0ifj==len(LL[i-1])elseLL[i-1][j])forjinrange(i+1)])returnLL