TRƯỜNG ĐẠI HỌC SƯ PHẠM
THÀNH PHỐ HỒ CHÍ MINH
∗
∗∗
∗∗
∗∗
∗∗
∗∗
∗∗
∗∗

)
n
a b+
NHƯ SAU 6
3.1. Thuật toán 6
3.2. Ví dụ áp dụng bài toán bất đẳng thức từ nhị thức Newton 7
IV. MỞ RỘNG THUẬT TOÁN KHAI TRIỂN NHỊ THỨC NEWTON, KHAI
TRIỂN TAM THỨC NEWTON 8
4.1. Thuật toán khai triển tam thức Newton
( )
n
a b c+ +
như sau 9
4.2. Mã Giả 10
4.3. Chương trình khai triển tam thức Newton 11
2
THUẬT TOÁN KHAI TRIỂN NHỊ THỨC NEWTON
VÀ TAM THỨC NEWTON
I.ĐẶT VẤN ĐỀ
Các hằng đẳng thức
Khi học chương trình Đại số lớp 8 các bạn gặp một số các hằng đẳng thức sau đây:
( )
( )
( )
( )
( )
( )
0
1
2

2.1 Nhị thức Newton( Niu-tơn)
Các hằng đẳng thức trên chỉ là trường hợp riêng của hằng đẳng thức tổng quát sau
đây:
( )
0 1 1 1 1
0

n
n
n n n n n n k n k k
n n n n n
k
a b C a C a b C ab C b C a b
− − − −
=
+ = + + + + =
∑
(1)
( ) ( ) ( ) ( )
0 0
1
k
n n
n
n k
k n k k n k k
n n
k k
a b a b C a b C a b
− −

)
Như vậy nếu có đẳng thức
(a b c)
n
+ +
ta khai triển như thế nào? Khai triển này
là mở rộng của nhị thức Newton hay còn gọi là tam thức Newton.
3
2.2 Chứng minh công thức tổ hợp.
Bây giờ chúng ta chứng minh bằng quy nạp biến số n công thức sau đây:
(
)
!
! !
k
n
n
n
C
k
k n k
æö
ç ÷
= =
ç ÷
-
è ø
Với n=0 thì
0
0

+ +
æ ö æ ö
+
+
ç ÷ ç ÷
= = = = =
ç ÷ ç ÷
+
+
è ø è ø
+

Với trường hợp
1 k N£ £
chúng ta có
1
1
k k k
N N N
C C C
-
+
= +
Theo giả thiết quy nạp thì công thức đúng với trường hợp n=N, cho nên
(
)
(
)
(
)

= =
ç ÷
-
è ø
-
Từ đó suy ra:
(
)
(
)
(
)
1
1
! !
1 ! 1 ! k! !
k k k
N N N
N N
C C C
k N k N k
-
+
= + = +
- - + -

(
)
(
)

ç ÷
= = =
ç
- +
è
+
÷
- +
ø
Như vậy chúng ta đã chứng minh đúng với n=N+1. Tóm lại, theo nguyên lý quy
nạp thì ta chứng minh được công thức cho các hệ số trong tam giác Pascal là
(
)
!
! !
k
n
n
n
C
k
k n k
æö
ç ÷
= =
ç ÷
-
è ø

4

3
C
2
3
C
3
3
C
4
0
4
C
1
4
C
2
4
C
3
4
C
4
4
C
… … … … … …
n
0
n
C
1

n
x
- - - -
æö æö æ ö æ ö
ç ÷ ç ÷ ç ÷ ç ÷
+ = + + + + + +
ç ÷ ç ÷ ç ÷ ç ÷
è ø è ø è ø
- -
è ø
Chúng ta dùng quy nạp để chứng minh định lý khai triển nhị thức Newton
(
)
1 2 2 2 2 1

1 2 2 1
n
n n n n n n
n
n n n n
x y x x y x y y xy y
n
x
- - - -
æö æö æ ö æ ö
ç ÷ ç ÷ ç ÷ ç ÷
+ = + + + + + +
ç ÷ ç ÷ ç ÷ ç ÷
è ø è ø è ø
- -

1
1 2 1
1
1
1
1

1
N N
N N N
N N N
N N N
N N
N N
C C
C C C
C C C
C C
+
+
- - -
+
-
+
+ =
+ =
+ =
+ =
Do đó
(

n n n n n n
n n n n
x x y x y x y x
n n
y y
- - - -
æö æö æ ö æ ö
ç ÷ ç ÷ ç ÷ ç ÷
= + + + + + +
ç ÷ ç ÷ ç ÷ ç ÷
è ø è ø è ø è
-
ø
-
Một cách khác, ta có thể dựa vào tam giác Pascal:
Thay
y y=-
chúng ta có hằng đẳng thức:
(
)
(
)
(
)
(
)
2 1
1 2 2 2 2 1
1 1 1
2 11 2

−
=
= + = = + + +
∑
•
( ) ( ) ( )
0 1
0
0 1 1 1 1
n
n k n
k n
n n n n
k
C C C C
=
= − = − = − + + −
∑
•
( )
0 1 1 0
0
1
n
n
k n k n n n
n n n n
k
x C x C x C x C x
− −

− = − = − + + −
∑
6
III. Thuật toán khai triển nhị thức Newton
(
)
n
a b+
như sau:
3.1 Thuật toán
Input : n bậc của nhị thức
Output:
0 1 1
0
( )
n
n n n k n k k n n k n k k
n n n n n
k
a b C a C a b C a b C b C a b
- - -
=
+ = + + + + + =
å
Bước 1: Viết tam giác Pascal đến dòng thứ n, của nhị thức Newton
( )
n
a b+

Cột(k)

2
3
C
3
3
C
4
0
4
C
1
4
C
2
4
C
3
4
C
4
4
C
… … … … … …
n
0
n
C
1
n
C

=
;
: ""S
=
; (
S
là xâu chứa hằng đẳng thức
( )
n
a b+
)
Bước 3: Nếu
k n>
qua Bước 5
Lập tam giác Pascal,
ta có:
k
n
C

b
n kk
a
-
Bước 4: Ghép các chuỗi ở bước 3
:
k n k k
n
s s C a b
−

không âm do đó có thể bỏ đi bất kì một số các số hạng nào đó ở vế phải ta được vế
trái không nhỏ hơn vế phải, chẳng hạn:
2
1
(1 ) 1
( 1)
(1 ) 1
2
(1 ) 1 ,
n
n
n n n
b nb
n n
b nb b
b nb b
-
+ ³ +
-
+ ³ + +
+ ³ + +

Từ (2), nếu
1
,( 1)b
n
n= >
thì
0 1 2
2

Nên:
1 1 1 1
1 1
1! 2! !
n
n n
æ ö
ç + ÷ + + +< +
ç ÷
è ø

Ví dụ 2:
Viết nhị thức Newton theo hai cách sau:
0 1 1 1 1
( )
n n n n n n n
n n n n
a b C a C a b C ab C b
- - -
+ = + + + +

1 1 1 1 0
( )
n n n n n n n
n n n n
b a C b C b a C ba C a
- - -
+ = + + + +
Cộng theo từng vế của hai đẳng thức trên ta có:
(


Do đó với
0, b 0a ³ ³
thì:
(
)
(
)
(
)
(
)
0 1 1
2( )
n n n n n n n n n n n
n n n n
a b C a b C a b C a b C a b
-
+ £ + + + + + + + +
8
(
)
2( ) 2
n n n n
a b a b + Ê +
hay
2 2
n
n n
a b a b

2 1 1 1 1
n n n
n n
n n n
C x C x x C x
-
= - + - + + + +
Vỡ
1x Ê
nờn
(1 ),(1 )x x- +
u khụng õm do ú:
( ) ( )
0
2 1 1 (1 ) (1 )
n n
n n n n
n n
C x C x x x - + + = - + +
IV. THUT TON KHAI TRIN TRONG TAM THC NEWTON
T trc n nay, ta ó quen bit vi tam giỏc Pascal l bng cỏc h s cho
khai trin nh thc Newton, cựng vi cỏc kớ hiu
k
n
C
. Bõy gi, ta s m rng cỏc
thut toỏn ú cho trng hp khai trin biu thc
( )
,
n

3 2
3 3 0 2 1 1 0 3
( ( )) 1. .( ) 3. .( ) 3. 1. .( )a b c a b c a b c a b c a b c a b c+ + = + + = + + + + + + +

3 2 2 2 2 3 2 2 3
3 3 3 6 3 3 3a a b a c ab abc ac b b c bc c= + + + + + + + + +

Ta cú th rỳt ra thut toỏn tỡm khai trin ca (a+b+c)
3
nh sau:
Bc 1: Vit bng cỏc h s v bin bờn trong ngoc
+ Cỏc h s ca dũng th i (i = 0, 1, 2, 3) ca bng l dũng th i ca tam giỏc
s Pascal.
9
+ Các biến của dòng thứ i (i = 0, 1, 2, 3) của bảng tương ứng với các hệ số
trên là dãy các biến của khai triển
( )
i
a b+
.
+ Đặt dấu cộng giữa các đơn thức trên.
Bước 2: Viết các nhân tử bên ngoài ngoặc:
+ Các hệ số ở dòng thứ i (i =0, 1, 2, 3) là dãy hệ số của dòng thứ n = 3 của
tam giác Pascal nghĩa là dòng cuối cùng của bảng số ở bước 1.
+ Các biến ở dòng thứ i (i = 0, 1, 2, 3) là dãy biến
3

i n i
a a
- -

= = =
+ + =
æ ö
ç ÷
= + = =
ç ÷
è
+ +
ø
å å å0
p q n p p q q
n p
q p n
C C a b c
- -
£ £ £
=
å

Như vậy ta có
4.1. Thuật toán khai triển tam thức Newton
( )
n
a b c+ +
như sau:
Input : n bậc của tam thức
Output:

Bước 2: Ở đầu các dòng, ta viết các đơn thức khai triển nhị thức Newton
( )
1
n
a +
,
tức là của
1 0
, , ,
n n
a a a
-
¼

Bước 3: Nhân lần lượt các đơn thức ở đầu dòng mỗi cột với các đơn thức còn lại
trên mỗi dòng đó, rồi cộng các kết quả lại.
10
Kết qủa cuối cùng là:
( )
4
4
3 3
2 2 2 2 2
3 2 2 3
4 3 2 2 3 4
4 4
6 12 6
4 12 12 4
4 6 4
a b c a

+ + = =
ç ÷
è ø
å å
Thuật toán:
Bước 1: nhập n vào
Bước 2: i:=0; s:=’ ‘;
11
Bước 3: nếu i > n thì dừng và in kết quả triển khai
Bước 4: tính
•
!
:
!( )!
i
n
n
C
i n i
=
−
(* hàm tohop(n,k) *)
• chèn

i n i
n
c a
−
vào chuổi S (* hàm chen(s1,s2) chen s1 vào s2 *)
• chèn “ ( “ vào S

var i:byte;
t:longint;
begin
t:=1;
for i:=1 to n do t:=t*i; gt:=t;
end;
function tohop(n,k:byte):longint;
begin
tohop:=gt(n)div(gt(k)*gt(n-k));
end;
function IntToStr(i:longint):string;
var
s:string;
12
begin
str(i,s);
IntToStr:=s;
end;
procedure chen(s2:string;Var s1:string);
var l:byte;
begin
l:=length(s1);
insert(s2,s1,l);
end;
procedure nhithuc(a,b:char;n:byte);
var i,j,k:byte;
s1,s2:string;
begin
for i:=0 to n do
begin

clrscr;
s:=' ';
writeLN('CHUONG TRINH TRIEN KHAI TAM THUC');
WRITEln('DANG: (a+b+c)^n ');
writeln;
ch:='r';
while ord(ch)<>27 do
begin
write('Nhap bac cua tam thuc vao : ');
readln(n);
write('(a+b+c)^',n,'=');
tamthuc('a','b','c',n) ;
write(s);
writeln;
writeln;
write('NHAN PHIM ESC DE THOAT');
CH:=readkey;
clrscr;
writeLN('CHUONG TRINH TRIEN KHAI TAM THUC');
WRITEln('DANG: (a+b+c)^n ');
writeln;
S:=' ';
end;
readln;
end.
14