BÀI TẬP LỚN HÀM SINH VÀ ỨNG DỤNG
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (3.34 MB, 20 trang )
Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ thông tin và truyền thông
Môn Toán rời rạc
BÁO CÁO
BÀI TẬP LỚN
HÀM SINH và ứng dụng
Nhóm nghiên cứu:
Kim Đình Sơn
20102089
Nguyễn Hữu Trung
20102767
Hoàng Lê Chung
20101172
Giảng viên hướng dẫn:
TS Đỗ Phan Thuận
HÀ NỘI, 4/17/2012
GENERATING FUNCTION
Mục lục
Chương 1 Tổng quan về hàm sinh...................................................................................................... 2
1.1.
Giới thiệu ........................................................................................................................... 2
1.2.
Các phép biến đổi trên hàm sinh ......................................................................................... 2
1.3.
Xây dựng hàm sinh ............................................................................................................ 3
Chương 2 Các khái niệm mở rộng ..................................................................................................... 6
2.1.
Hàm sinh mũ ...................................................................................................................... 6
2.2.
Hàm sinh đa biến ............................................................................................................... 7
2.3.
Hàm sinh xác suất ............................................................................................................ 11
2.3.1.
Khái niệm................................................................................................................. 11
2.3.2.
Hàm sinh của tổng các biến ngẫu nhiên .................................................................... 12
Chương 3 Ứng dụng ........................................................................................................................ 13
3.1, Bài toán tính đếm .................................................................................................................. 13
3.2. Bài toán tính tổng.................................................................................................................. 14
3.3. Tính số phép toán trung bình của thuật toán .......................................................................... 15
3.4. Các ứng dụng khác ............................................................................................................... 16
3.4.1. Bài toán đếm số cây khung ............................................................................................. 16
3.4.2. Hàm sinh chuỗi Dirichlet ................................................................................................ 16
3.4.3. Tính số các bảng dự phòng bởi các số nguyên không âm (
) ............. 17
Kết luận .......................................................................................................................................... 18
Tài liệu tham khảo ........................................................................................................................... 19
1
GENERATING FUNCTION
∑
∑
∑
⏟
∑
∑
∑
{
{ }
}
{
}
∑
∑
∑
∑
∑
2
∑
∑
GENERATING FUNCTION
(
)
∑
∑
∑
∑
√
∑(
√
∑
(
)
) (
∑
)
(
)
∑
∑
3
(
)
GENERATING FUNCTION
{
}
)
∏(
∑
{
∑
}
|
{
∑
| |
}
∑
∑
∑
∑
{ }
(
{
{
}
)
∏(
∏(
)
∏(
(∏(
∑
4
)
))
)
}
GENERATING FUNCTION
∑∑
∑[
]
∑
∑
∑(
)∑
(
(
((
)
∑
∑
(
)
)∑
))
)
∑
{
∑
∑∑
∑∑(
∑∑∑
|
∑∑
∑
∑∑
|
∑
|
∑
∑
|
[(
)
5
]
GENERATING FUNCTION
{
} {
|
∑
}
|
∑
(
∑
)
(
)
6
∑
GENERATING FUNCTION
(
)
∏
∑
∑
[
]
|
{
∑
|
{
[ ]
∑
{
7
}
GENERATING FUNCTION
[
∑
]
|
{
}
{
}
(
)
(
)
∑
|
∑
[
]
[(
|
∑
∑
∑
∑
∑
∑
8
)
]
GENERATING FUNCTION
∑
∑
∑
∑
∑
|
∑
∏
∑
∏(
)
9
GENERATING FUNCTION
∑
|
∑
|
(Multivariate Fuss-Catalan numbers)(một dạng tổng quát cho số
Catalan). Xác định bởi công thức:
(
)
[ ]
∑
o
o
(
o
)(
)
[ ]
10
GENERATING FUNCTION
∑
( )
∑
∑
∑
∑
[ ]
11
GENERATING FUNCTION
| |
∑
[
[
]
(
]
[
]
[ ]
[ ]
)
∑
∏
12
[ ]
GENERATING FUNCTION
(
(
(
( )
( )( )
∑
)
(
)
)
)
( )( )
{
{
}
13
}
GENERATING FUNCTION
(
)
∑
∑
(
)
∑( )
(
∑( )(
)
-
(⌊
∑
( )
⌋
)
⌋
⌊
)
(⌊
(
)
(
⌋
)
14
)
GENERATING FUNCTION
∑( )
(
)
∑( )
(
(
)
⌋
⌊
)
(
)
Begin:
j:=1;m=:X[1];
for i:=2 to n do
if x[i]>m then
m:=x[i];
j:=i;
end if
end for
End
[]
[]
15
{ [ ]
}
GENERATING FUNCTION
∑
[]
[]
[]
[]
[]
[]
∑
∑
(
)(
)(
∑
)
(
∑
)
(
)
∑
∑
[
]
{
}
∑
↔ {
↔ {
}
}
↔ {∑
16
}
GENERATING FUNCTION
(∑
)
∑
{
∑
∑
∑
[
]
∑
∏∏
17
}
GENERATING FUNCTION
18
GENERATING FUNCTION
19
