楊輝三角

楊輝三角，是二項式係數在三角形中的一種幾何排列，中國南宋數學家楊輝1261年所著的《詳解九章算法》一書中出現。在歐洲，帕斯卡（1623----1662）在1654年發現這一規律，所以這個表又叫做帕斯卡三角形。帕斯卡的發現比楊輝要遲393年，比賈憲遲600年。

楊輝三角是中國數學史上的一個偉大成就。

基本介紹

• 中文名：楊輝三角
• 外文名：Pascal's Triangle
• 別稱：賈憲三角形、帕斯卡三角形
• 表達式：幾何
• 提出者：楊輝
• 提出時間：約1050年
• 套用學科：數學，計算機
• 適用領域範圍：數學，計算機
• 使用人群：中學生、大學生，編程專家、等等
• 發現者：楊輝

簡介

楊輝三角，是二項式係數在三角形中的一種幾何排列。在歐洲，這個表叫做帕斯卡三角形。帕斯卡（1623----1662）是在1654年發現這一規律的，比楊輝要遲393年，比賈憲遲600年。楊輝三角是中國古代數學的傑出研究成果之一，它把二項式係數圖形化，把組合數內在的一些代數性質直觀地從圖形中體現出來，是一種離散型的數與形的結合。

概述

前提：每行端點與結尾的數為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+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開始，正整數在楊輝三角形出現的次數為∞,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