Phổ thông sinh thành hàm sổ

Tự liệtĐích phổ thông sinh thành hàm sổ ( ordinary generating function, OGF ) định nghĩa vi hình thức mịch cấp sổ:

F(x)=\sum_{n}a_n x^n

Kí khả dĩ thị hữu cùng tự liệt, dã khả dĩ thị vô cùng tự liệt. Thường kiến đích lệ tử ( giả thiếtDĩVi khởi điểm ):

Tự liệt $a=\langle 1,2,3\rangle$ Đích phổ thông sinh thành hàm sổ thị.
Tự liệt $a=\langle 1,1,1,\cdots\rangle$ Đích phổ thông sinh thành hàm sổ thị $\sum_{n\ge 0}x^n$ .
Tự liệt $a=\langle 1,2,4,8,16,\cdots\rangle$ Đích sinh thành hàm sổ thị $\sum_{n\ge 0}2^nx^n$ .
Tự liệt $a=\langle 1,3,5,7,9,\cdots\rangle$ Đích sinh thành hàm sổ thị $\sum_{n\ge 0}(2n+1)x^n$ .

Hoán cú thoại thuyết, như quả tự liệtHữu thông hạng công thức, na ma tha đích phổ thông sinh thành hàm sổ đích hệ sổ tựu thị thông hạng công thức.

Cơ bổn vận toán

Khảo lự lưỡng cá tự liệtĐích phổ thông sinh thành hàm sổ, phân biệt vi.Na ma hữu

F(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n

Nhân thử $F(x)\pm G(x)$ Thị tự liệt $\langle a_n\pm b_n\rangle$ Đích phổ thông sinh thành hàm sổ.

Khảo lự thừa pháp vận toán, dã tựu thị quyển tích:

F(x)G(x)=\sum_n x^n \sum_{i=0}^na_ib_{n-i}

Nhân thửThị tự liệt $\langle \sum_{i=0}^n a_ib_{n-i} \rangle$ Đích phổ thông sinh thành hàm sổ.

Phong bế hình thức

Tại vận dụng sinh thành hàm sổ đích quá trình trung, ngã môn bất hội nhất trực sử dụng hình thức mịch cấp sổ đích hình thức, nhi hội thích thời địa chuyển hóa vi phong bế hình thức dĩ canh hảo địa hóa giản.

Lệ như $\langle 1,1,1,\cdots\rangle$ Đích phổ thông sinh thành hàm sổ $F(x)=\sum_{n\ge 0}x^n$ ,Ngã môn khả dĩ phát hiện

Na ma giải giá cá phương trình đắc đáo

F(x)=\frac{1}{1-x}

Giá tựu thị $\sum_{n\ge 0}x^n$ Đích phong bế hình thức.

Khảo lự đẳng bỉ sổ liệt $\langle 1,p,p^2,p^3,p^4,\cdots\rangle$ Đích sinh thành hàm sổ $F(x)=\sum_{n\ge 0}p^nx^n$ ,Hữu

\begin{aligned}F(x)px+1 &=F(x)\\F(x) &=\frac{1}{1-px}\end{aligned}

Đẳng bỉ sổ liệt đích phong bế hình thức dữ triển khai hình thức thị thường dụng đích biến hoán thủ đoạn.

Tiểu luyện tập

Thỉnh cầu xuất hạ liệt sổ liệt đích phổ thông sinh thành hàm sổ ( hình thức mịch cấp sổ hình thức hòa phong bế hình thức ). Nan độ thị tuần tự tiệm tiến đích.

$a=\langle 0,1,1,1,1,\cdots\rangle$ .
$a=\langle 1,0,1,0,1,\cdots \rangle$ .
$a=\langle 1,2,3,4,\cdots \rangle$ .
$a_n=\binom{m}{n}$ (Thị thường sổ, $n\ge 0$ ).
$a_n=\binom{m+n}{n}$ (Thị thường sổ, $n\ge 0$ ).

Đáp án

Đệ nhất cá:

F(x)=\sum_{n\ge 1}x^n=\dfrac{x}{1-x}

Đệ nhị cá:

\begin{aligned} F(x)&=\sum_{n\ge 0}x^{2n}\\ &=\sum_{n\ge 0}(x^2)^{n}\\ &=\frac{1}{1-x^2} \end{aligned}

Đệ tam cá ( cầu đạo ):

\begin{aligned}F(x)&=\sum_{n\ge 0}(n+1)x^n\\&=\sum_{n\ge 1}nx^{n-1}\\&=\sum_{n\ge 0}(x^n)'\\&=\left(\frac{1}{1-x}\right)'\\&=\frac{1}{(1-x)^2}\end{aligned}

Đệ tứ cá ( nhị hạng thức định lý ):

F(x)=\sum_{n\ge 0}\binom{m}{n}x^n=(1+x)^m

Đệ ngũ cá:

F(x)=\sum_{n\ge 0}\binom{m+n}{n}x^n=\frac{1}{(1-x)^{m+1}}

Khả dĩ sử dụng quy nạp pháp chứng minh.

Thủ tiên đươngThời, hữu $F(x)=\dfrac{1}{1-x}$ .

Nhi đươngThời, hữu

\begin{aligned} \frac{1}{(1-x)^{m+1}} &=\frac{1}{(1-x)^m}\frac{1}{1-x}\\ &=\left(\sum_{n\ge 0}\binom{m+n-1}{n}x^n \right)\left(\sum_{n\ge 0}x^n \right)\\ &=\sum_{n\ge 0} x^n\sum_{i=0}^n \binom{m+i-1}{i}\\ &=\sum_{n\ge 0}\binom{m+n}{n}x^n \end{aligned}

Phỉ ba na khế sổ liệt đích sinh thành hàm sổ

Tiếp hạ lai ngã môn lai thôi đạo phỉ ba na khế sổ liệt đích sinh thành hàm sổ.

Phỉ ba na khế sổ liệt định nghĩa vi $a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}\;(n>1)$ .Thiết tha đích phổ thông sinh thành hàm sổ thị,Na ma căn cư tha đích đệ thôi thức, ngã môn khả dĩ loại tự địa liệt xuất quan vuĐích phương trình:

Na ma giải đắc

F(x)=\frac{x}{1-x-x^2}

Na ma tiếp hạ lai đích vấn đề thị, như hà cầu xuất tha đích triển khai hình thức?

Triển khai phương thức nhất

Bất phương tươngĐương tác nhất cá chỉnh thể, na ma khả dĩ đắc đáo

\begin{aligned} F(x)&=\frac{x}{1-(x+x^2)}\\ &=\sum_{n\ge 0}(x+x^2)^n\\ &=\sum_{n\ge 0}\sum_{i=0}^n\binom{n}{i}x^{2i}x^{n-i}\\ &=\sum_{n\ge 0}\sum_{i=0}^n\binom{n}{i}x^{n+i}\\ &=\sum_{n\ge 0}x^n\sum_{i=0}^n\binom{n-i}{i} \end{aligned}

Ngã môn đắc đáo liễuĐích thông hạng công thức, đãn na tịnh bất thị ngã môn thục tri đích hữu quan hoàng kim phân cát bỉ đích hình thức.

Triển khai phương thức nhị

Khảo lự cầu giải nhất cá đãi định hệ sổ đích phương trình:

\frac{A}{1-ax}+\frac{B}{1-bx}= \frac{x}{1-x-x^2}

Thông phân đắc đáo

\frac{A-Abx+B-aBx}{(1-ax)(1-bx)} = \frac{x}{1-x-x^2}

Đãi định hạng hệ sổ tương đẳng, ngã môn đắc đáo

\begin{cases} A+B=0\\ -Ab-aB=1\\ a+b=1\\ ab=-1 \end{cases}

Giải đắc

\begin{cases} A=\frac{1}{\sqrt{5}}\\ B=-\frac{1}{\sqrt{5}}\\ a=\frac{1+\sqrt{5}}{2}\\ b=\frac{1-\sqrt{5}}{2} \end{cases}

Na ma ngã môn căn cư đẳng bỉ sổ liệt đích triển khai thức, tựu khả dĩ đắc đáo phỉ ba na khế sổ liệt đích thông hạng công thức:

\frac{x}{1-x-x^2}=\sum_{n\ge 0}x^n \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \right)

Giá dã bị xưng vi phỉ ba na khế sổ liệt đích lánh nhất cá phong bế hình thức ( $\frac{x}{1-x-x^2}$ Thị nhất cá phong bế hình thức ).

Đối vu nhậm ý đa hạng thức,Sinh thành hàm sổ $\dfrac{P(x)}{Q(x)}$ Đích triển khai thức đô khả dĩ sử dụng thượng thuật phương pháp cầu xuất. Tại thật tế vận dụng đích quá trình trung, ngã môn vãng vãng tiên cầu xuấtĐích căn, bả phân mẫu biểu kỳ vi $\prod (1-p_ix)^{d_i}$ Đích hình thức, nhiên hậu tái cầu phân tử.

Đương đối phân mẫu tiến hành nhân thức phân giải đãn hữu trọng căn thời, mỗi hữu nhất cá trọng căn tựu yếu đa nhất cá phân thức, như khảo lự sinh thành hàm sổ

G(x)=\frac{1}{(1-x)(1-2x)^2}

Đích hệ sổ đích thông hạng công thức, na ma hữu

G(x)=\frac{c_0}{1-x}+\frac{c_1}{1-2x}+\frac{c_2}{(1-2x)^2}

Giải đắc

\begin{cases} c_0&=1\\ c_1&=-2\\ c_2&=2 \end{cases}

Na ma

[x^n]G(x)=1-2^{n+1}+(n+1)\cdot 2^{n+1}

Ngưu đốn nhị hạng thức định lý

Ngã môn trọng tân định nghĩa tổ hợp sổ đích vận toán:

\binom{r}{k}=\frac{r^{\underline{k}}}{k!}\quad(r\in\mathbf{C},k\in\mathbf{N})

Chú ýĐích phạm vi thị phục sổ vực. Tại giá chủng tình huống hạ. Đối vu $\alpha\in\mathbf{C}$ ,Hữu

(1+x)^{\alpha}=\sum_{n\ge 0}\binom{\alpha}{n}x^n

Nhị hạng thức định lý kỳ thật thị ngưu đốn nhị hạng thức định lý đích nhất cá đặc thù tình huống.

Tạp đặc lan sổ đích sinh thành hàm sổ

Tham khảoCatalan sổ đích phong bế hình thức

Ứng dụng

Tiếp hạ lai cấp xuất nhất ta lệ đề, lai giới thiệu sinh thành hàm sổ tại OI trung đích cụ thể ứng dụng.

Thực vật

Tại hứa đa bất đồng chủng loại đích thực vật trung tuyển xuấtCá, mỗi chủng thực vật đích hạn chế như hạ:

Thừa đức hán bảo: Ngẫu sổ cá
Khả nhạc: 0 cá hoặc 1 cá
Kê thối: 0 cá, 1 cá hoặc 2 cá
Mật đào đa: Kỳ sổ cá
Kê khối: 4 đích bội sổ cá
Bao tử: 0 cá, 1 cá, 2 cá hoặc 3 cá
Thổ đậu phiến sao nhục: Bất siêu quá nhất cá.
Diện bao: 3 đích bội sổ cá

Mỗi chủng thực vật đô thị dĩ “Cá” vi đan vị, chỉ yếu tổng sổ gia khởi lai thịTựu toán nhất chủng phương án. Đối vu cấp xuất đíchNhĩ nhu yếu kế toán xuất phương án sổ, đốiThủ mô.

Giá thị nhất đạo kinh điển đích sinh thành hàm sổ đề. Đối vu nhất chủng thực vật, ngã môn khả dĩ thiếtBiểu kỳ giá chủng thực vật tuyểnCá đích phương án sổ, tịnh cầu xuất tha đích sinh thành hàm sổ. Nhi lưỡng chủng thực vật nhất cộng tuyểnCá đích phương án sổ đích sinh thành hàm sổ, tựu thị tha môn sinh thành hàm sổ đích quyển tích. Đa chủng thực vật tuyểnCá đích phương án sổ đích sinh thành hàm sổ dã thị tha môn sinh thành hàm sổ đích quyển tích.

Tại lý giải liễu phương án sổ khả dĩ dụng quyển tích biểu kỳ dĩ hậu, ngã môn tựu khả dĩ cấu tạo sinh thành hàm sổ ( tiêu hào đối ứng đề mục trung thực vật đích tiêu hào ):

$\displaystyle\sum_{n\ge 0}x^{2n}=\dfrac{1}{1-x^2}$ .
.
$1+x+x^2=\dfrac{1-x^3}{1-x}$ .
$\dfrac{x}{1-x^2}$ .
$\displaystyle \sum_{n\ge 0}x^{4n}=\dfrac{1}{1-x^4}$ .
$1+x+x^2+x^3=\dfrac{1-x^4}{1-x}$ .
.
$\dfrac{1}{1-x^3}$ .

Na ma toàn bộ thừa khởi lai, đắc đáo đáp án đích sinh thành hàm sổ:

F(x)=\frac{(1+x)(1-x^3)x(1-x^4)(1+x)}{(1-x^2)(1-x)(1-x^2)(1-x^4)(1-x)(1-x^3)} =\frac{x}{(1-x)^4}

Nhiên hậu tương tha chuyển hóa vi triển khai hình thức ( sử dụng phong bế hình thức luyện tập trung đệ ngũ cá luyện tập ):

F(x)=\sum_{n\ge 1}\binom{n+2}{n-1}x^n

Nhân thử đáp án tựu thị $\dbinom{n+2}{n-1}=\dbinom{n+2}{3}$ .

Sweet

“CEOI2004” Sweet

HữuĐôi đường quả. Bất đồng đích đôi lí đường quả đích chủng loại bất đồng ( tức đồng nhất cá đôi lí đích đường quả chủng loại thị tương đồng đích, bất đồng đích đôi lí đích đường quả đích chủng loại thị bất đồng đích ). ĐệCá đôi lí hữuCá đường quả. Hiện tại yếu cật điệu chí thiếuCá đường quả, đãn bất siêu quáCá. Cầu hữu đa thiếu chủng phương án.

Lưỡng chủng phương án bất đồng đương thả cận đương cật đích cá sổ bất đồng, hoặc giả cật đích đường quả trung, mỗ nhất chủng đường quả đích cá sổ tại lưỡng cá phương án trung bất đồng.

$n\le 10,0\le a\le b\le 10^7,m_i\le 10^6$ .

Tại đệĐôi cậtCá đường quả đích phương án sổ ( hiển nhiên vi 1 ) đích sinh thành hàm sổ vi

F_i(x)=\sum_{j=0}^{m_i}x^j=\frac{1-x^{m_i+1}}{1-x}

Nhân thử tổng cộng cậtCá đường quả đích phương án sổ đích sinh thành hàm sổ tựu thị

G(x)=\prod_{i=1}^n F_i(x)=(1-x)^{-n}\prod_{i=1}^n(1-x^{m_i+1})

Hiện tại ngã môn yếu cầu đích thị $\sum_{i=a}^b[x^i]G(x)$ .

Do vu $n\le 10$ ,Nhân thử ngã môn khả dĩ bạo lực triển khai $\prod_{i=1}^n(1-x^{m_i+1})$ ( tối đa chỉ hữuHạng ).

Nhiên hậu đối $(1-x)^{-n}$ Sử dụng ngưu đốn nhị hạng thức định lý:

\begin{aligned} (1-x)^{-n} &=\sum_{i\ge 0}\binom{-n}{i}(-x)^i\\ &=\sum_{i\ge 0}\binom{n-1+i}{i}x^i \end{aligned}

Ngã môn mai cử $\prod_{i=1}^n(1-x^{m_i+1})$ TrungHạng đích hệ sổ, giả thiết vi.Na ma tha hòa $(1-x)^{-n}$ Tương thừa hậu, đối đáp án đích cống hiến tựu thị

c_k\sum_{i=a-k}^{b-k}\binom{n-1+i}{i}=c_k\left( \binom{n+b-k}{b-k}- \binom{n+a-k-1}{a-k-1} \right)

Giá dạng tựu khả dĩĐịa cầu xuất đáp án liễu.

Thời gian phục tạp độ.

Bổn hiệt diện tối cận canh tân:2023/3/22 15:46:23,Canh tân lịch sử
Phát hiện thác ngộ? Tưởng nhất khởi hoàn thiện?Tại GitHub thượng biên tập thử hiệt!
Bổn hiệt diện cống hiến giả:sshwy,CCXXXI,countercurrent-time,Enter-tainer,Great-designer,hly1204,NachtgeistW,purple-vine,schtonn,shuzhouliu,skylee03,SukkaW
Bổn hiệt diện đích toàn bộ nội dung tạiCC BY-SA 4.0HòaSATAHiệp nghị chi điều khoản hạ đề cung, phụ gia điều khoản diệc khả năng ứng dụng