-
楊輝三角
鎖定
- 中文名
- 楊輝三角
- 外文名
- Pascal's Triangle
- 別 名
-
賈憲三角形
帕斯卡三角形 - 表達式
- 幾何
- 提出者
- 楊輝
- 提出時間
- 約1050年
- 適用領域
- 數學，計算機
- 應用學科
- 數學，計算機
- 使用人羣
- 中學生、大學生，編程專家、等等
- 發現者
- 楊輝
楊輝三角簡介
楊輝三角，是二項式係數在三角形中的一種幾何排列。在歐洲，這個表叫做帕斯卡三角形。帕斯卡（1623----1662）是在1654年發現這一規律的，比楊輝要遲393年，比賈憲遲600年。楊輝三角是中國古代數學的傑出研究成果之一，它把二項式係數圖形化，把組合數內在的一些代數性質直觀地從圖形中體現出來，是一種離散型的數與形的結合
[2]
。
楊輝三角
楊輝三角補充説明
前提：每行端點與結尾的數為1.
（與上圖中的n不同，這裏第一行定義為n=1）
- 每個數等於它上方兩數之和。
- 每行數字左右對稱，由1開始逐漸變大。
- 第n行的數字有n項。
- 前n行共[(1+n)n]/2 個數。
- 第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的展開式中的各項係數依次對應楊輝三角的第(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），其中m為該數所在的列，再將各項相加的和為11^（n-1）。11^0=1，11^1=1x10^0+1×10^1=11，11^2=1×10^0+2x10^1+1x10^2=121，11^3=1x10^0+3×10^1+3x10^2+1x10^3=1331，11^4=1x10^0+4x10^1+6x10^2+4x10^3+1x10^4=14641，11^5=1x10^0+5x10^1+10x10^2+10x10^3+5x10^4+1×10^5=161051。
- 第n行數字的和為2^（n-1）。1=2^（1-1），1+1=2^（2-1），1+2+1=2^（3-1），1+3+3+1=2^（4-1），1+4+6+4+1=2^（5-1），1+5+10+10+5+1=2^（6-1）。
- 斜線上數字的和等於其向左（從左上方到右下方的斜線）或向右拐彎（從右上方到左下方的斜線），拐角上的數字。1+1=2，1+1+1=3，1+1+1+1=4，1+2=3，1+2+3=6，1+2+3+4=10，1+3=4，1+3+6=10，1+4=5。
- 將各行數字左對齊，其右上到左下對角線數字的和等於斐波那契數列的數字。1，1，1+1=2，2+1=3，1+3+1=5，3+4+1=8，1+6+5+1=13，4+10+6+1=21，1+10+15+7+1=34，5+20+21+8+1=55。
應用
性質5和性質7是楊輝三角的基本性質，是研究楊輝三角其他規律的基礎。
與楊輝三角聯繫最緊密的是二項式乘方展開式的係數規律，即二項式定理。例如在楊輝三角中，第3行的三個數恰好對應着兩數和的平方的展開式的每一項的係數（性質 8），第4行的四個數恰好依次對應兩數和的立方的展開式的每一項的係數，即
，以此類推。
又因為性質5：第n行的m個數可表示為C(n-1,m-1)，即為從n-1個不同元素中取m-1個元素的組合數。因此可得出二項式定理的公式為：
因此，二項式定理與楊輝三角形是一對天然的數形趣遇，它把數形結合帶進了計算數學。求二項式展開式係數的問題，實際上是一種組合數的計算問題。用係數通項公式來計算，稱為“式算”；用楊輝三角形來計算，稱作“圖算”
[3]
。
數在楊輝三角中的出現次數
由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）
因為丟番圖方程
有無窮個解，所以出現至少六次的數有無窮個多。解為
，其中Fn表示第n個斐波那契數（F1=F2=1）。
3003是第一個出現八次的數。
楊輝三角歷史沿革
北宋人賈憲約1050年首先使用“賈憲三角”進行高次開方運算。
楊輝，字謙光，南宋時期杭州人。在他1261年所著的《詳解九章算法》一書中，輯錄瞭如上所示的三角形數表，稱之為“開方作法本源”圖，並説明此表引自11世紀中葉（約公元1050年）賈憲的《釋鎖算術》，並繪畫了“古法七乘方圖”。故此，楊輝三角又被稱為“賈憲三角”。
在歐洲直到1623年以後，法國數學家帕斯卡在31歲時發現了“帕斯卡三角”。
布萊士·帕斯卡的著作Traité du triangle arithmétique（1655年）介紹了這個三角形。帕斯卡蒐集了幾個關於它的結果，並以此解決一些概率論上的問題，影響面廣泛，Pierre Raymond de Montmort（1708年）和亞伯拉罕·棣·美弗（1730年）都用帕斯卡來稱呼這個三角形。
21世紀以來國外也逐漸承認這項成果屬於中國，所以有些書上稱這是“中國三角形”（Chinese triangle）
歷史上曾經獨立繪製過這種圖表的數學家有：
- 賈憲 中國北宋 11世紀 《釋鎖算術》
- 楊輝 中國南宋1261《詳解九章算法》記載之功
- 阿爾·卡西 阿拉伯 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]=1
curr[0]=1 # 接下來每行第一個始終為一，無需重複賦值
# 執行
pad $(((lyrs-1)*2))
echo 1
for ((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;
}
默認狀態下不啓用金字塔和菱形的輸出
這個算法創建了一個二維數組，並且通過上一行的數值求當前行。在反過來再次打印時，這個程序會使用以前算好的值，從而節省了重複迭代的時間。
/* 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 100
typedef 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 I
End 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) end create 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) end create 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) end create 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 end end exec 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(" ",$n*12," ");
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(" ",($n+1-$i)*12," ");
printf("%3d",$arr[$i][$j]=$arr[$i-1][$j-1]+$arr[$i-1][$j]);
echo " ";
}
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 python def 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
- 參考資料
-
- 1. 教材編委會．數學 選修2-3：人民教育出版社，2009：33
- 2. 趙金成,陳中峯.“有趣的楊輝三角”教學實錄與評析[J].中國數學教育（高中版）,2013,(1):25-28. ．萬方數據庫．2013-05-03[引用日期2017-08-28]
- 3. 楊明順.楊輝三角的若干性質研究[J].渭南師範學院學報,2016,(4):9-12. ．萬方數據庫．2016-04-07[引用日期2017-08-28]
