数学建模 / 英语

生成函数

CSU Mathematics · YouTube · 8:58

YouTube · CSU Mathematics原视频

选中时刻 · 7:35 · 章节点是时间参考，不表示实时播放进度。

视频中的要点

01生成函数作为一根晾衣绳
02斐波那契数列示例
03x是一个形式变量

来自学习笔记

0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots

斐波那契数列示例

选中时刻

适用于所有 n 的无穷生成函数

建议预备知识

无穷序列
基本幂次记号 $x^n$
求和记号 $\sum_{n=0}^{\infty}$
数列与带索引的列表
多项式记号与 x 的幂
二项式系数 $\binom{n}{k}$
基础硬币面值：便士 = 1美分，镍币 = 5美分
基础多项式乘法
理解指数与同类项
组合的基本计数
多项式乘法
指数与形式幂级数
无序组合的基本组合计数
基本数列与求和记号
初等组合数学：乘法原理
生成函数的非正式概念：作为编码一个序列的幂级数

阅读与收藏

把讲解展开来看。

被收藏 0

已审核学习内容 · 视频分析 · 中文

阅读完整概览

这是一节时长为 120 秒的导论课，将生成函数定义为序列的形式编码。课程从赫伯特·威尔夫（Herbert Wilf）的晾衣绳比喻出发，展示了斐波那契序列 0,1,1,2,3,5,8,13, $\ldots$ ，并将其重写为 $0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots$ ，同时强调 x 仅是一个形式符号，而非用于收敛计算的具体数值输入。第二张幻灯片给出一般定义 $A(x) = a_0 + a_1x + a_2x^2 + \cdots = \sum_{n=0}^{\infty} a_n x^n$ ，并将其应用于序列 1,1,1,1,1, $\ldots$ 和 1,2,3,4, $\ldots$ 。本段时长120秒的讲座，将生成函数引入为序列系数的编码方式，再特化到终归为零序列的多项式型生成函数；给出显式示例1,2,1,0,0,… ↦ $1+2x+x^2$ ，以及帕斯卡三角形恒等式 $\binom{n}{0}+\binom{n}{1}x$ +⋯+ $\binom{n}{n}x^n=(1+x)^n$ ，并以此激发生成函数的因式分解思想；最后将该思路应用于一个含7枚便士与2枚镍币的硬币找零问题：先列出凑出6美分的两种方式，再将问题分解为按美分索引的仅便士序列与仅镍币序列。这段时长120秒的讲座片段，通过硬币找零实例引出生成函数概念。它首先将用7枚便士与2枚镍币凑零钱的方式分别编码为两个多项式，再解释其相乘之所以能统计组合选择数，是因为指数相加。讲师展开该乘积，说明每一幂次项的系数即对应凑出该分值的方式数，并以6分、10分、12分、13分和18分为例加以演示。片段最后提出一个更大规模的问题：用便士、镍币、角币和二角五分币凑出32分。这段时长为120秒的讲座片段通过硬币换零钱问题引出生成函数的概念。它首先解决一个具体问题：用便士、镍币、角币和四分之一美元硬币凑出32分共有多少种方式？方法是写出四个有限多项式，在 Sage 中将它们相乘，并提取 $x^{32}$ 的系数，从而得到17。接着，它通过定义 $c_n$ 为凑出 n 分的方式数，并给出 $C(x)=P(x)N(x)D(x)Q(x)$ （其中每个因子现在均为无穷级数），来引出无穷生成函数的一般思想。关键的概念跃迁在于：从单次截断计算转向一个能同时编码所有答案的形式幂级数。这个时长为 58 秒的片段讲解了用于硬币找零计数的一种基础生成函数方法。第一张幻灯片将 $c_n$ 定义为用便士、镍币、角币和二十五分硬币凑出 n 美分的方法数，接着展示了单枚硬币对应的级数 $P(x)$ 、 $N(x)$ 、 $D(x)$ 、 $Q(x)$ ，并指出 $C(x) = P(x)N(x)D(x)Q(x)$ 。讲师解释道，将这些相互独立的选择相乘，是对乘法原理的推广，且能一次性编码所有可能的金额。第二张幻灯片提出了一个关于 Splinktonk 星球的练习题：splink 值 2 美分，tonk 值 7 美分，且最多使用五个 splink 和两个 tonk，要求观众将两个多项式相乘；该片段在任何解法演示前即结束。

在学习检查器中查看要点和时刻，或切换阅读标签查看完整笔记。

章节

0:00标题与导言 0:11晾衣绳比喻与斐波那契示例 0:46x 作为形式变量 1:09一般定义与简单示例 2:00生成函数的定义 2:04多项式作为生成函数 2:38帕斯卡三角形与(

1+x

)^n 2:59找零问题：7枚便士和2枚镍币 3:17仅用便士的序列 3:44仅用镍币的序列 4:00硬币找零序列与6分示例 4:02写出便士与镍币的生成函数 4:27为何多项式相乘可统计组合选择数 4:56展开乘积并读取系数 5:48生成函数的力量 5:5532美分四硬币问题的设定 6:00用有限多项式进行换零钱 6:51Sage 计算与系数提取 7:35适用于所有 n 的无穷生成函数 8:00硬币找零生成函数的构建 8:16为何对级数进行相乘是可行的 8:33Splinktonk 练习题

学习解说文稿

依据视频画面与讲解整理，并非逐字语音转写。

视频以一张紫色标题卡开场，上面写着“生成函数”，课程标识为“数石头！：科罗拉多州立大学组合数学导论”。主讲人走入画面，将生成函数作为组合数学的一个主题进行介绍。

第一张内容幻灯片引用赫伯特·威尔夫的话：“生成函数是一根晾衣绳，用来悬挂一列数字以便展示。”其下方，幻灯片将序列0,1,1,2,3,5,8,13, $\ldots$ 与级数 $0+x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots$ 并列呈现。视觉对齐方式揭示了规则：所列第n个数字成为 $x^n$ 的系数。

主讲人随后澄清符号x的地位。她指出，屏幕上显示的对象未必是关于x的收敛函数；相反，x是一个形式变量。它的指数标记序列中的位置，而系数则承载序列的实际数值。这将该级数重新界定为一种记号工具，而非解析函数。

一张题为“定义与示例”的新幻灯片对该概念加以形式化。在加框陈述中，序列 $a_0$ , $a_1$ , $a_2$ , $\ldots$ 的生成函数被定义为 $A(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a$ _nx^n。主讲人指出惯例：用大写字母A表示与小写序列a相对应的函数。

紧接着给出两个直接示例。对于常数序列1,1,1,1,1, $\ldots$ ，每个系数均为1，因此其生成函数为 $1+x+x^2+x^3+\cdots$ 。主讲人补充说明，形式变量的字母是任意的：也可写作 $A(y)$ 或使用其他任意符号。

最后，对于计数数列1,2,3,4, $\ldots$ ，系数依次变为1,2,3,4, $\ldots$ ，从而得到 $1+2x+3x^2+4x^3+\cdots$ 。视频在此处结束，此时主讲人仍在重申：x的幂次被用来记录序列中的位置。

该片段首先将序列 $a_0,a_1,a_2,\ldots$ 的生成函数定义为 $A(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a_nx^n$ 。主讲人用类比说明： $x$ 的各次幂就像衣架，序列的各项就挂在这些衣架上。

接着转向多项式——一种特殊的生成函数。若一个序列最终全为零（例如 $1,2,1,0,0,\ldots$ ），则其对应的级数为 $1+2x+x^2+0+0+\cdots$ ，而零系数可被省略，从而得到有限多项式 $1+2x+x^2$ 。

第二个多项式例子是有限序列 $\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}$ ，音频中指出这是帕斯卡三角形的 $n$ 行。其生成函数写作 $\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n$ ，幻灯片指出该式等于 $(1+x)^n$ 。

紧接此例之后，讲师指出：对生成函数进行因式分解，将成为以组合方式理解或求解系数的有力工具。本片段并未在此处证明这一论断，而是通过刚刚展示的因式分解来激发这一思路。

最后一节引入了一个具体的找零问题：用7枚便士和2枚五分镍币，共有多少种方法凑出6美分？幻灯片上明确列出了两种答案：1枚便士和1枚镍币，或者6枚便士。

接着，主讲人将问题从单一目标金额6美分推广至所有美分金额，并将对应方案数记录为一个序列。仅使用便士时，从0美分到7美分的每个金额都恰好有一种表示方式，而更大的金额则无法表示，由此得到序列 $1,1,1,1,1,1,1,0,0,0,\ldots$ 。

仅使用五美分硬币时，使用0，1或2个五美分硬币只能得到0，5，或者10 美分。因此，以美分为索引的序列为 $1,0,0,0,0,1,0,0,0,0,1,0,0,\ldots$ ，在0、5, 且 10 且 zeros elsewhere.

该片段以一张标题为‘找零’的幻灯片开场，问题为：你有7枚便士和2枚镍币，共有多少种方法凑出6美分？幻灯片明确列出两种组合：1枚便士与1枚镍币，以及6枚便士与0枚镍币。其下方，幻灯片展示了两个计数序列，分别对应便士与镍币。

幻灯片下半部分由序列转为生成函数：便士对应的多项式为 $1+x+x^2+x^3+x^4+x^5+x^6+x^7$ ；镍币对应的多项式为 $1+x^5+x^{10}$ 。讲师解释道，最终指数记录了该类硬币最多可使用的枚数。

对于镍币，允许的总金额为0、5或10美分，因此其生成函数恰好包含三项。这使编码规则变得具体：指数 = 金额（美分），系数 = 仅用该类硬币实现该金额的方式数。

接着，讲师将幻灯片上展示的两种6美分组合，与两个多项式中各项的乘积关联起来：从便士多项式中选取 $x$ ，从镍币多项式中选取 $x^5$ ，得到 $x\cdot x^5=x^6$ ；选取 $x^6$ 和 $1$ 则得到 $x^6\cdot 1=x^6$ 。由于乘法使指数相加，这些恰好对应凑出总计6美分的所有方式。

由此引出通用方法：为统计组合后的硬币选择方式数，需将生成函数相乘，并查看目标幂次项的系数。在此例中，乘积中 $x^6$ 次幂项的系数即等于凑出6美分的方法数。

幻灯片切换为“重新表述”，并提问：在乘积中，有多少种方法凑出 $x^6$ in the product $(1+x+\cdots+x^7)(1+x^5+x^{10})$ 。完整展开式显示为： $1 + x + x^2 + x^3 + x^4 + 2x^5 + 2x^6 + 2x^7 + x^8 + x^9 + 2x^{10} + 2x^{11} + 2x^{12} + x^{13} + x^{14} + x^{15} + x^{16} + x^{17}$ 。

从该展开式中可直观看出， $x^6$ 次幂项的系数为2，从而验证了先前的直接枚举结果。讲师强调：现在这个已展开的多项式能一次性回答所有金额的问题，而不仅限于6美分。

讲师朗读若干系数作为示例：10美分有2种方法，12美分有2种方法，13美分有1种方法。由于该多项式在 $x^{17}$ 处截止，故不存在 $x^{18}$ 项，因此无法用这些硬币凑出18美分。

教学要点被明确指出：生成函数让代数能够同时执行大量计数运算，以一个多项式乘积取代繁琐的分类讨论。

一张新幻灯片将该方法推广至更大规模的问题：使用便士、角币、镍币与四分之一美元硬币，共有多少种方法凑出32美分？四种生成函数分别列为 $1+x+x^2+\cdots+x^{32}$ 、 $1+x^5+x^{10}+\cdots+x^{30}$ 、 $1+x^{10}+x^{20}+x^{30}$ 和 $1+x^{25}$ 。该片段在此处结束，尚未展开乘积，也未计算 $x^{32}$ 的系数。

该片段以一个具体的计数问题开场：用便士、镍币、角币和四分之一美元硬币凑出32分，有多少种无序方式？由于目标金额固定，每种硬币都有其自然的上限。

讲师明确解释了这些上限：最多32 枚便士、6 枚镍币，3 枚十分硬币，以及 1 枚二十五分硬币可以以任意有效的组合出现，用于凑成 32 美分。这将原本开放的选择转化为一个有限的多项式模型。

接着，每种硬币类型被编码为一个多项式，其各项指数表示该硬币类型所贡献的分值。便士对应 $1+x+x^2+\cdots+x^{32}$ ；镍币对应 $1+x^5+x^{10}+\cdots+x^{30}$ ；角币对应 $1+x^{10}+x^{20}+x^{30}$ ；四分之一美元硬币对应 $1+x^{25}$ 。

下一步是计算环节：在 Sage 中，四个多项式分别定义为 P、N、D 和 Q，使用范围求和实现，与幻灯片上显示的截断指数模式一致。

将乘积 $P*N*D*Q$ 展开，并提取其中 $x^{32}$ 项的系数。从概念上讲，该乘积中的每一项都从每种硬币类型中各选取一个贡献，而指数则记录所选硬币对应的总美分数。

屏幕上显示的结果是 17，因此共有 17 种方式凑出 32 美分。讲师强调，这种系数提取方法比手工枚举所有组合要简便得多。

课程随后从单个具体实例转向一般性理论：不再只关注凑出 32 美分的方式数，而是定义 $c_n$ 为使用同四种硬币凑出 n 美分的方法总数。

为了将所有数 $c_0$ , $c_1$ , $c_2$ , $\ldots$ 整合进一个数学对象中，引入生成函数 $C(x)$ 。幻灯片分别写出每种硬币对应的无穷级数： $P(x)=1+x+x^2+x^3+\cdots$ ， $N(x)=1+x^5+x^{10}+x^{15}+\cdots$ ， $D(x)=1+x^{10}+x^{20}+x^{30}+\cdots$ ，以及 $Q(x)=1+x^{25}+x^{50}+x^{75}+\cdots$ 。

核心结论是 $C(x)=P(x)N(x)D(x)Q(x)$ 。这消除了对每个目标金额单独截断的需要；同一个无穷乘积一次性编码了所有 n 对应的答案。

视频片段以一张标题为“生成函数”的幻灯片开始。一个带框的问题陈述定义 $c_n$ as the number of ways to make $n$ 美分的方法数，并要求该序列 $C(x)$ 的生成函数 $(c_n)$ 。

其下方并列显示四个独立的级数： $P(x)=1+x+x^2+x^3+\cdots$ 、 $N(x)=1+x^5+x^{10}+x^{15}+\cdots$ 、 $D(x)=1+x^{10}+x^{20}+x^{30}+\cdots$ 和 $Q(x)=1+x^{25}+x^{50}+x^{75}+\cdots$ 。每个级数分别记录单一币种可能带来的贡献：对应面值为1美分、5美分、10美分和25美分的硬币。

讲师解释道：若分别考虑仅使用某一种硬币来凑零钱的所有方式，再将这些生成函数相乘，即可得到完整序列 $c_n$ 的生成函数。幻灯片通过公式 $C(x)=P(x)\cdot N(x)\cdot D(x)\cdot Q(x)$ 明确表达了这一过程。

她强调该方法的广泛适用性：一个乘积即可编码所有可能美分数额（“直至无穷”）所对应的答案，而无需对每个数额单独求解。

随后，讲解将该方法与组合数学更广泛地联系起来：选择若干枚便士、若干枚镍币、若干枚角币以及若干枚四分之一美元硬币，可视为乘法原理的一种推广；生成函数的乘法能同时完成多个相互独立的计数选择。

幻灯片切换至一道练习题，标题为“现在你来试试……”。它引入了名为 Splinktonk 的星球，其中 splink 币值为2美分，tonk 币值为7美分。任务是将两个多项式相乘，以统计在恰好拥有五枚 splink 和两枚 tonk 的前提下，凑出各种金额的方式数。

她在朗读题目时补充了一个具体观察：在 Splinktonk 星球上，你无法恰好凑出1美分，因为没有任何一种硬币的面值是1，且任意数量的2与7组合也无法得到1。

视频片段以如下指令结束：分别构造 splink 和 tonk 对应的有界生成多项式，并将它们相乘。本片段中未展示展开过程或最终的系数表。

知识卡片

生成函数作为一根晾衣绳

讲座以赫伯特·威尔夫的比喻引入生成函数：生成函数是一根晾衣绳，一列数字被悬挂其上以便展示。这表明此处的主要目的，是代数地编码一个序列，而非立即求某个数值函数的值。

斐波那契数列示例

从斐波那契数列0,1,1,2,3,5,8,13, $\ldots$ 出发，视频将各项依次写作x的各次幂的系数。结果为 $0+x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots$ ，直观展示了基本构造规则。

0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots

x是一个形式变量

主讲人明确指出，该级数对于x的各个取值而言，未必表示一个收敛函数。相反，x只是一个形式符号，其指数仅用于指示序列中的位置，而系数则直接给出该序列本身。

一般定义

对于无穷序列 $a_0$ , $a_1$ , $a_2$ , $\ldots$ ，其生成函数定义为 $A(x)=a_0+a_1x+a_2x^2+\cdots$ ，等价于 $\sum_{n=0}^{\infty}a$ _nx^n。用大写字母A表示小写字母a所对应的序列，是一种约定俗成的做法。

A(x) = a_0 + a_1x + a_2x^2 + \cdots = \sum_{n=0}^{\infty} a_n x^n

全一数列

若序列为1,1,1,1,1, $\ldots$ ，则每个系数都等于1，因此生成函数为 $1+x+x^2+x^3+\cdots$ 。这是对定义最直接、最简单的应用。

1 + x + x^2 + x^3 + \cdots

变量名称的选择

形式变量所用的字母并非本质性的。主讲人指出，可以写作 $A(y)$ 而非 $A(x)$ ，甚至可选用其他符号，因为该变量仅作为幂次的形式占位符。

自然数序列

对于序列1,2,3,4, $\ldots$ ，各项依次成为对应项的系数，得到 $1+2x+3x^2+4x^3+\cdots$ 。这再次印证了在斐波那契示例中所采用的相同系数放置规则。

1 + 2x + 3x^2 + 4x^3 + \cdots

生成函数的定义

该片段通过将序列第n项作为 $x^n$ 的系数来定义该序列的生成函数。这是本片段后续全部内容所采用的基本编码方式。

A(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a_nx^n

最终为零的序列对应多项式

如果一个序列在有限项之后全部变为零，那么它的生成函数可以写成一个多项式，因为末尾的零系数无需写出。示例序列1,2,1,0,0,... 变为 $1+2x+x^2$ 。

1+2x+x^2+0+0+\cdots=1+2x+x^2

帕斯卡三角形的一行作为生成函数

帕斯卡三角形第n行的二项式系数构成的有限序列，其生成函数为( $1+x$ )^n。视频片段将此作为可因式分解的多项式生成函数的关键示例。

\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n=(1+x)^n

为何要对生成函数进行因式分解

在帕斯卡三角形示例之后，讲师立即指出：对生成函数进行因式分解有助于从组合意义上理解其系数。这被用作后续操作技巧的动机说明。

硬币找零问题：凑出6美分

当有7枚便士和2枚镍币时，幻灯片直接列出了凑出6美分的两种方式：一枚便士加一枚镍币，或六枚便士。

仅用便士的找零序列

When only seven pennies are available, the number of ways to make c cents is 1，其中 $c =0$ ，1，…，7，且0（当c更大时）。因此，以美分为索引的序列为1，1，1，1，1，1，1，0，0，0，……

1,1,1,1,1,1,1,0,0,0,\ldots

仅用镍币的找零序列

当仅有两枚镍币可用时，可凑出的金额为0美分、5美分和10美分。以美分为索引，这些位置上的值为1，其余位置为0：1、0、0、0、0、1、0、0、0、0、1、0、0、……

1,0,0,0,0,1,0,0,0,0,1,0,0,\ldots

计数序列的生成函数

生成函数将一个计数序列打包为一个多项式或幂级数。在本节硬币找零课程中， $x^n$ 的系数记录了用允许的硬币凑出 $n$ 美分的方法数。

\sum_{n\ge 0} a_n x^n

含7枚便士的便士生成函数

若最多可使用7枚便士，则仅用便士即可恰好以唯一方式凑出从0美分到7美分之间的每一种金额。因此该生成函数是幂次连续递增、最高幂次为 $x^7$ 的各项之和。

1+x+x^2+x^3+x^4+x^5+x^6+x^7

含2枚镍币的镍币生成函数

若最多可使用2枚镍币，则仅用镍币所能凑出的金额为0美分、5美分和10美分。这些金额成为生成函数中各项的指数。

1+x^5+x^{10}

为何生成函数相乘是可行的

从每种硬币类型的生成函数中各选一项，对应于从每组硬币中选取一个贡献值。各项相乘时指数相加，因此乘积的每一项统计的是组合后的总金额。

x^a\cdot x^b=x^{a+b}

例题：凑出6美分

凑出6美分的两种方式是：1枚便士加1枚镍币，以及6枚便士加0枚镍币。用生成函数的语言描述，这两种方式分别对应 $x\cdot x^5$ 和 $x^6\cdot 1$ ，二者均对 $x^6$ 项作出贡献。

x\cdot x^5 + x^6\cdot 1 = 2x^6

含7枚便士与2枚镍币的展开乘积

将便士生成函数与镍币生成函数相乘，得到一个多项式；其各项系数回答了该套硬币下所有找零问题。

(1+x+x^2+x^3+x^4+x^5+x^6+x^7)(1+x^5+x^{10})=1 + x + x^2 + x^3 + x^4 + 2x^5 + 2x^6 + 2x^7 + x^8 + x^9 + 2x^{10} + 2x^{11} + 2x^{12} + x^{13} + x^{14} + x^{15} + x^{16} + x^{17}

从系数读取答案

乘积展开后，每一项幂次的系数即表示凑出对应美分数目的方法数。讲师依次读出示例：2种方法凑出10 美分，2 种方式表示 12 美分，1 种方式表示 13 美分，且 0 种方式表示 18 美分，因为没有 $x^{18}$ 项出现。

[x^n]\bigl(P(x)Q(x)\bigr)

生成函数的主要优势

无需分别求解多个独立的计数问题，仅需一次代数运算即可同时算出所有系数。这被视作该方法的核心力量。

32美分四枚硬币问题的设定

相同方法可推广至更多种类的硬币。若用便士、镍币、角币和二角五分币凑出32美分，则所求答案即为所列四个生成函数乘积中 $x^{32}$ 项的系数。

[x^{32}]\bigl((1+x+\cdots+x^{32})(1+x^5+\cdots+x^{30})(1+x^{10}+x^{20}+x^{30})(1+x^{25})\bigr)

用于凑出 32 美分找零的有限多项式编码

对于固定的 32 美分目标金额，每种硬币类型由一个有限多项式表示，其各项指数即为该类硬币所能贡献的美分数值。幻灯片中分别用一个因式表示便士、镍币、角币和四分币，并将每个因式截断于不超过 32 美分的最大倍数处。

(1+x+x^2+\cdots+x^{32})(1+x^5+x^{10}+\cdots+x^{30})(1+x^{10}+x^{20}+x^{30})(1+x^{25})

详细学习笔记

按知识点查看条件、步骤和证据。补充解释与视频直接内容分别标明。

符号定义 · 40

x

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片展示了生成函数 $0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7$ + ⋯，随后给出 $A(x) = a_0 + a_1x + a_2x^2$ + ⋯。
声音
观察依据
主讲人指出，x 是一个形式变量，仅作为带指数的符号，用于标示序列中的位置。

符号

含义

在生成函数中用作幂的底数的形式变量；其指数记录序列中的索引或位置。

适用范围

形式符号；本片段中不将其视为用于收敛性分析的数值输入。

$A(x)$

依据清楚

视频直接表达

来源依据

公式
观察依据
定义框中写有： $A(x) = a_0 + a_1x + a_2x^2$ + ⋯ = $\sum _{n=0}^{\infty } a_n x^n$ 。
声音
观察依据
主讲人说：‘我们通常将序列 a 对应的生成函数记作 $A(x)$ ，即用大写字母 A 表示小写字母 a 的序列，这仅是一种惯例。’

符号

$A(x)$

含义

与序列 $a_0$ , $a_1$ , $a_2$ , … 相关联的生成函数。

适用范围

关于变量 x 的形式幂级数。

$a_0$ , $a_1$ , $a_2$ , $\ldots$

依据清楚

视频直接表达

来源依据

公式
观察依据
定义框中写道：‘序列 $a_0$ , $a_1$ , $a_2$ , … 的生成函数是’，随后给出 $A(x) = \sum _{n=0}^{\infty } a_n x^n$ 。
声音
观察依据
主讲人在朗读定义时，点出无限序列 $a_0$ , $a_1$ , $a_2$ , …。

符号

$a_0$ , $a_1$ , $a_2$ , $\ldots$

含义

一项无限序列，其各项成为生成函数的系数。

适用范围

带索引的序列；本片段未指明各项所属的数系。

$a_n$

依据清楚

视频直接表达

来源依据

公式
观察依据
求和形式在 $\sum_{n=0}^{\infty} a_n x^n$ 中使用 $a_n x^n$ 。
声音
观察依据
说话人将该求和读作：‘n 从零到无穷大时，a 下标 n 乘以 x 的 n 次方的和’。

符号

$a_n$

含义

序列的第 n 项，作为生成函数中 $x^n$ 的系数出现。

适用范围

所展示的求和式中， $n \ge 0$ 。

n

依据清楚

视频直接表达

来源依据

公式
观察依据
定义框中显示 $\sum_{n=0}^{\infty} a_n x^n$ 。
声音
观察依据
说话人称 n 从零取到无穷大。

符号

含义

求和指标同时标记序列项 $a_n$ 和幂次 $x^n$ 。

适用范围

非负整数，起始于 0。

y

依据清楚

视频直接表达

来源依据

声音
观察依据
说话人说：‘顺便提一下，我们也可以使用不同的变量。例如可写成 y 的函数 $A(y)$ ，然后把所有 x 替换为 y。’

待核验内容

屏幕上未显示含 y 的任何公式；替代变量仅通过口头说明。

符号

含义

生成函数中可用来替代 x 的另一种形式变量示例。

适用范围

形式符号；仅口头提及。

$a_0$ , $a_1$ , $a_2$ , $\ldots$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片展示了数列 $a_0$ , $a_1$ , $a_2$ , … 的生成函数，记为 $A(x) = a_0 + a_1x + a_2x^2$ + ⋯ = $\sum _{n=0}^{\infty } a_n x^n$ 。

符号

$a_0$ , $a_1$ , $a_2$ , $\ldots$

含义

其各项被编码为生成函数的系数的数列。

适用范围

一个无穷数列；本片段中的示例使用整数与二项式系数。

$A(x)$

依据清楚

视频直接表达

来源依据

公式
观察依据
所展示的定义将该生成函数命名为 $A(x)$ 。

符号

$A(x)$

含义

与数列 $a_0$ , $a_1$ , $a_2$ , … 相关联的形式幂级数或多项式。

适用范围

关于不定元 x 的函数；片段中未说明任何收敛条件。

x

依据清楚

视频直接表达

来源依据

公式
观察依据
在所有已展示的生成函数示例中，x 均作为乘以各次幂的变量出现。

待核验内容

片段未明确说明 x 是被纯粹当作形式符号处理，还是被当作数值变量处理。

符号

含义

用作将数列位置记录为指数的不定元。

适用范围

示例中出现了幂次 $x^0$ , $x^1$ , $x^2$ , …。

1,1,1,1,1,1,1,0,0,0, $\ldots$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片列出了便士换算序列为 1，1，1，1，1，1，1，0，0，0， $\ldots$ ，在“组成 0 的方式数”下1，2，3，……用便士表示的美分。

符号

1,1,1,1,1,1,1,0,0,0, $\ldots$

含义

仅用七枚便士凑出每个非负美分数额的方式数。

适用范围

按美分索引：0、1、2、3、……

1,0,0,0,0,1,0,0,0,0,1,0,0, $\ldots$

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片将五美分换算序列列为 1，0，0，0，0，1，0，0，0，0，1，0，0，……在‘组成……的方式数’下方0，1，2，3，……使用镍币。

符号

1,0,0,0,0,1,0,0,0,0,1,0,0, $\ldots$

含义

仅使用两枚五美分硬币，凑出每个非负美分数额的方案数。

适用范围

按美分索引：0、1、2、3、……

x

依据清楚

视频直接表达

来源依据

公式
观察依据
变量 x 在屏幕上显示的所有生成函数表达式中均用作幂的底数。

符号

含义

用于通过指数编码美分数量的形式变量。

适用范围

形式幂级数／多项式变量

知识点 · 25

生成函数作为一列数字的晾衣绳

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片标题“生成函数”包含引语：“生成函数是一根晾衣绳，用于悬挂一列数字以供展示。——赫伯特·威尔夫”
声音
观察依据
主讲人复述了赫伯特·威尔夫的这句引语，并补充说明：这正是代数被用于分析组合数学的起点。

定义

解释

视频通过赫伯特·威尔夫的比喻引入生成函数：它是一根晾衣绳，一列数字被悬挂其上以供展示。主讲人将此表述为运用代数分析组合数学的开端。

公式

适用条件

适用于一列数字。
本片段强调的是展示／编码功能，而非数值计算。

斐波那契数列编码为生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片列出：序列：0, 1, 1, 2, 3, 5, 8, 13, $\ldots$ ；生成函数： $0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots$ 。
声音
观察依据
主讲人说：“假设我们有斐波那契数列0, 1, 1, 2, 3, 5, 8, 13。你只需把这些数作为幂级数的系数即可。”随后朗读屏幕上显示的级数。

方法

解释

该例取斐波那契数列0,1,1,2,3,5,8,13, $\ldots$ ，并将其各项依次作为x的各次幂的系数。所得显示的级数起始为 $0+x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots$ 。

公式

0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots

适用条件

数列各项按顺序作为 $x^0$ , $x^1$ , $x^2$ , $\ldots$ 的系数。

先修条目

生成函数作为一列数字的晾衣绳

将 x 视为一个形式变量，而非收敛意义上的输入值

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出，这一工具未必在x的各类取值下构成收敛函数；它仅是一根晾衣绳，而x只是一个形式变量／符号。
声音
观察依据
她解释道：指数表示序列中的第三项或第四项等位置，而系数则记录序列本身的各项数值。

定义

解释

主讲人明确提醒：屏幕上展示的这种类似幂级数的对象，不必被视作关于 x 的收敛函数。在本入门性讲解中，x 是一个形式符号，其各次幂仅用于标记序列中的位置，而系数则承载序列的各项取值。

公式

适用条件

当把生成函数视为序列的形式编码时使用。
本片段中不假设收敛性。

先修条目

斐波那契数列编码为生成函数

生成函数的正式定义

依据清楚

视频直接表达

来源依据

公式
观察依据
定义框：“序列 $a_0$ , $a_1$ , $a_2$ , $\ldots$ 的生成函数为 $A(x) = a_0 + a_1x + a_2x^2 + \cdots = \sum_{n=0}^{\infty} a_n x^n$ 。”
声音
观察依据
主讲人朗读该定义，并指出一种惯例：用大写字母 $A(x)$ 表示对应小写字母 a 的序列。

定义

解释

对于无穷数列 $a_0$ , $a_1$ , $a_2$ ,…，其生成函数定义为形式幂级数 $A(x) = a_0 + a_1x + a_2x^2$ + ⋯，等价地可用求和符号写作 $\sum _{n=0}^{\infty } a_n x^n$ 。主讲人指出，大写字母 A 与小写字母 a 搭配是一种命名惯例。

公式

A(x) = a_0 + a_1x + a_2x^2 + \cdots = \sum_{n=0}^{\infty} a_n x^n

适用条件

输入是一个从 $n=0$ 开始索引的无限序列。
该表达式被呈现为一个形式级数。

先修条目

生成函数作为一列数字的晾衣绳
将 x 视为一个形式变量，而非收敛意义上的输入值

常数数列1、1、1、……的生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片显示：“1, 1, 1, 1, 1, $\ldots$ 的生成函数：”后接 $1 + x + x^2 + x^3 + \cdots$ 。
声音
观察依据
The speaker says, 'For instance, the generating function of the all ones sequence is 1 加 x 加 x 的平方加 x 的立方，等等。”

公式

解释

当数列每一项都等于1时，生成函数中每个系数均为1，从而得到形式级数 $1+x+x^2+x^3$ +⋯。

公式

1 + x + x^2 + x^3 + \cdots

适用条件

该数列为 $a_n=1$ （对所有 $n\ge 0$ 成立）。

先修条目

生成函数的正式定义

计数数列1、2、3、4、……的生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片显示：“1、2、3、4、……的生成函数：”后接 $1+2x+3x^2+4x^3$ +⋯。
声音
观察依据
主讲人说：“计数数列1、2、3、4、……的生成函数是1加2x加3x的平方加4x的立方，等等。”

待核验内容

视频片段在讲解x的幂如何被使用的中途结束。

公式

解释

对于数列1、2、3、4、……，各项依次作为x的各次幂的系数出现，得到 $1+2x+3x^2+4x^3$ +⋯。这体现了与斐波那契示例相同的系数放置规则。

公式

1 + 2x + 3x^2 + 4x^3 + \cdots

适用条件

该数列从1开始，每步递增1；首项乘以 $x^0$ 。

先修条目

生成函数的正式定义

生成函数的定义

依据清楚

视频直接表达

来源依据

公式
观察依据
定义框中写道：序列 $a_0$ 、 $a_1$ 、 $a_2$ 、…… 的生成函数为 $A(x) = a_0 + a_1x + a_2x^2$ + ⋯ = $\sum _{n=0}^{\infty } a_n x^n$ 。
声音
观察依据
主讲人将其描述为‘挂起你的数字序列以供展示的衣架绳’。

定义

解释

生成函数通过将序列各项依次作为某个不定元各次幂的系数来记录该序列。本片段将生成函数呈现为一种序列的展示工具，而非具有明确定义域的解析函数。

公式

A(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a_nx^n

适用条件

输入是一个序列 $a_0$ 、 $a_1$ 、 $a_2$ 、……
$x^n$ 的系数是 $a_n$ 。

最终为零的序列给出多项式型生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片显示：‘序列1、2、1、0、0、……的生成函数：’后接 $1 + 2x + x^2 + 0 + 0$ + ⋯ = $1 + 2x + x^2$ 。
声音
观察依据
主讲人指出，若一个无穷序列最终全为零，则可将其视作一个有限多项式，因为零项无需写出。

方法

解释

当一个序列在有限项之后全部变为零时，它的生成函数是一个多项式：非零的初始项保留下来，而末尾的零系数可以省略。

公式

1+2x+x^2+0+0+\cdots=1+2x+x^2

适用条件

该序列仅有有限个非零项。
从某个下标开始，之后的所有项均为0。

先修条目

生成函数的定义

帕斯卡三角形某一行的生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片指出，序列 $\binom{n}{0}$ , $\binom{n}{1}$ , $\ldots$ , $\binom{n}{n}$ 的生成函数为 $\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n=(1+x)^n$ 。
声音
观察依据
主讲人将该序列称为‘帕斯卡三角形的第 n 行’，并指出其生成函数可因式分解为 ( $1+x$ )^n。

公式

解释

帕斯卡三角形第 n 行的二项式系数构成的有限序列，其生成函数为 ( $1+x$ )^n。本片段以此作为多项式型生成函数因式分解的核心例证。

公式

\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n=(1+x)^n

适用条件

n 是一个非负整数。
该序列为 $\binom{n}{0}$ , $\binom{n}{1}$ , $\ldots$ , $\binom{n}{n}$ 。

先修条目

生成函数的定义
最终为零的序列给出多项式型生成函数

硬币找零计数问题的设定

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片标题为‘换零钱’，问题框中提问：‘你有7枚便士和2枚镍币。凑出6美分共有多少种方法？’
声音
观察依据
主讲人口述了同一问题，并列出了两种直接解法。

定义

解释

该片段引入了一个具体的枚举问题：计算用至多6美分硬币和至多7枚便士组成2镍币。它首先直接求解特定目标，再将问题分解为所有分值金额的序列。

公式

适用条件

可用硬币：7枚便士和2枚镍币。
题目中指定的目标金额：6美分。

仅使用便士的换零钱序列

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片将序列1,1,1,1,1,1,1,0,0,0,…标记为用便士凑出0、1、2、3……美分的方案数。
声音
观察依据
主讲人解释道：若有七枚便士，则恰好有一种方式凑出从0到7美分之间的每一种金额，而超过7美分则无法凑出。

方法

解释

对于以分为索引的金额，仅使用便士的组合数为 1 对每个金额 0，1, $\ldots$ ,7 以及 0 此后，因为从 7 分起至 1 分的每个金额都恰好能用一枚价值

公式

1,1,1,1,1,1,1,0,0,0,\ldots

适用条件

仅使用便士。
最多可使用7枚便士。

先修条目

硬币找零计数问题的设定

仅使用五美分硬币的找零序列

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片将序列1,0,0,0,0,1,0,0,0,0,1,0,0,…标记为用镍币凑出0、1、2、3……美分的方案数。
声音
观察依据
主讲人解释道：用两枚五美分硬币，可以凑出0美分、5美分或10美分，无法凑出其他金额。

方法

解释

对于以分为索引的金额，仅使用镍币的组合数为 1 在 5 的倍数处（直至 10 美分和 0 其他位置，因为使用 0、1 或 2 个镍币恰好得到 0、5 或 10 美分。

公式

1,0,0,0,0,1,0,0,0,0,1,0,0,\ldots

适用条件

仅使用五美分硬币。
最多可使用2枚五美分硬币。

先修条目

硬币找零计数问题的设定

定理与条件 · 9

此处生成函数无需被视为收敛函数

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人说：“现在，这个工具并不一定对各种x值构成收敛函数。它实际上只是一根晾衣绳。”

待核验内容

该视频片段未给出明确的收敛判据或收敛半径。

命题

所展示的这种幂级数形式的对象，对于各种 x 的取值而言，未必是收敛函数；在本介绍中，它主要被当作一种形式化的编码工具来处理。

前提

该对象正被用作某个序列的生成函数。
x 被解释为一个形式变量，而非数值输入。

量词

本片段中的示例不假设对任意 x 都收敛。

形式变量的名称是任意的

依据清楚

视频直接表达

来源依据

声音
观察依据
说话人指出，可以使用 $A(y)$ ，将其中的 x 替换为 y，也可使用星号或笑脸等任意符号，因为它仅是一个形式符号。

待核验内容

仅给出口头陈述；未展示使用其他符号的公式。

命题

形式变量所用的字母是约定俗成的；x 可替换为 y 或其他符号，而不改变生成函数的作用。

前提

该变量被形式化地用于标记级数中的幂次／位置。

量词

适用于本片段所讨论的生成函数记号中的占位符符号。

因式分解生成函数有助于理解系数

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人说：“因式分解生成函数将成为求解系数或以更组合化的方式理解系数的非常有力的工具。”

待核验内容

这是关于未来用途的方法论主张，并未在本片段中加以证明。

命题

因式分解生成函数在以组合方式求解或理解系数时很有用。

前提

被操作的对象是生成函数。

量词

这是一般性方法论陈述；片段中未给出形式化的量词。

$x^6$ 的系数等于2

依据清楚

视频直接表达

来源依据

公式
观察依据
展开后的乘积包含项 $2x^6$ 。
声音
观察依据
我们确实看到x的六次方项的系数为二

命题

在乘积 $(1+x+x^2+x^3+x^4+x^5+x^6+x^7)(1+x^5+x^{10})$ 中， $x^6$ 的系数是2。

前提

共有7枚便士和2枚五美分硬币。
生成函数编码了按美分金额找零的各种方式。

量词

针对特定的指数6。

该乘积即为硬币找零问题的完整生成函数。

依据清楚

视频直接表达

来源依据

声音
观察依据
这是一个生成函数，用于计算用七枚便士和两枚五美分硬币凑出任意美分数额的方法数。
公式
观察依据
完全展开的多项式显示在幻灯片上。

命题

展开后的乘积给出了用7枚便士和2枚五美分硬币凑出每一种可能美分数额的方法数。

前提

请使用幻灯片中给出的便士生成函数和五美分硬币生成函数。
将它们相乘，并读取各项系数。

量词

针对乘积中指数所表示的所有美分金额。

共有 17 种方式凑出 32 美分

依据清楚

视频直接表达

来源依据

图示
观察依据
屏幕上显示的代码输出为：'Answer: 17'。
声音
观察依据
说话人说：'答案立刻就出来了，是17。'

命题

用便士、一角硬币、五分硬币和二角五分硬币凑出32美分的方法数为17。

前提

可用的硬币有便士、五分硬币、一角硬币和二角五分硬币。
硬币的顺序无关紧要。
幻灯片上使用的是有限多项式模型。

量词

针对特定目标32美分的存在性计算结果。

整体生成函数是四种硬币生成函数的乘积。

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片明确写出： $C(x) = P(x) \cdot N(x) \cdot D(x) \cdot Q(x)$ 。
声音
观察依据
主讲人将 $C(x)$ 介绍为序列 $c_n$ 的生成函数，并在幻灯片上展示了该乘积公式。

命题

若 $c_n$ 表示用便士、镍币、角币和二角五分币凑出 n 美分的方法数，则 $C(x) = P(x)N(x)D(x)Q(x)$ 。

前提

$P(x)$ 、 $N(x)$ 、 $D(x)$ 、 $Q(x)$ 分别是便士、镍币、角币和二角五分币对应的无穷生成函数。
$C(x)$ 是序列 $c_n$ 的生成函数。

量词

对所有非负整数 n， $C(x)$ 中 $x^n$ 的系数等于 $c_n$ 。

$C(x)$ 的系数解释

依据清楚

依据视频推导

来源依据

公式
观察依据
幻灯片将 $c_n$ 定义为凑出 n 美分的方法数，并给出 $C(x) = P(x)N(x)D(x)Q(x)$ 。
声音
观察依据
讲师指出，将单枚硬币的生成函数相乘，即可得到序列 $c_n$ 的生成函数。

待核验内容

视频虽未明确陈述系数提取这一说法，但通过称 $C(x)$ 为 $c_n$ 的生成函数，已直接蕴含该含义。

命题

$C(x) = P(x)N(x)D(x)Q(x)$ 中 $x^n$ 的系数等于 $c_n$ ，即用便士、镍币、角币和四分之一美元硬币凑出 n 美分的方法数。

前提

P、N、D、Q 分别是选择0枚或更多便士、镍币、角币和四分之一美元硬币的生成函数。
$C(x)$ 定义为这四个函数的乘积。

量词

对每个非负整数 n。

一个乘积同时处理所有金额

依据清楚

视频直接表达

来源依据

声音
观察依据
讲师：“因此，它一次性解决了使用这四种硬币所能产生的所有可能问题，且延伸至无穷。”

命题

单个乘积 $C(x) = P(x)N(x)D(x)Q(x)$ 同时编码了所有金额 n 对应的答案，并无限延展。

前提

这四个因子即幻灯片上所展示的无穷级数。

量词

对所有由 x 的幂所表示的目标金额 n。

推导与证明 · 10

从斐波那契数列构造其生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片展示了序列行，其正下方直接对应显示了生成函数行。
声音
观察依据
主讲人解释道：将数列各项作为幂级数的系数，然后读出屏幕上显示的级数。

视觉说明

步骤

公式
$0, 1, 1, 2, 3, 5, 8, 13, \ldots$
解释
从屏幕上显示的斐波那契数列开始。
步骤依据
该数列在幻灯片上给出，并由主讲人口头念出。
视频直接表达
公式
$0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots$
解释
将第一项放在 $x^0$ 处，第二项放在 $x^1$ 处，第三项放在 $x^2$ 处，并依序继续下去。
步骤依据
这正是幻灯片上所展示、并被主讲人口头描述为‘将数列各项作为幂级数系数’的系数模式。
视频直接表达

结论

斐波那契数列被编码为一个形式级数，其系数依次为斐波那契数。

从一个数列过渡到一般的生成函数记号

依据清楚

视频直接表达

来源依据

公式
观察依据
定义框中同时给出了 $A(x)$ 的展开式与求和式两种形式。
声音
观察依据
主讲人在给出具体例子之后，朗读了一般性定义。

视觉说明

步骤

公式
$a_0, a_1, a_2, \ldots$
解释
从一个从 0 开始编号的任意无穷数列出发。
步骤依据
该陈述出现在定义框的标题中。
视频直接表达
公式
$A(x) = a_0 + a_1x + a_2x^2 + \cdots$
解释
将序列的每一项写为下一个 x 的幂次的系数。
步骤依据
这是幻灯片上展示的展开定义。
视频直接表达
公式
$A(x) = \sum_{n=0}^{\infty} a_n x^n$
解释
用求和符号简洁地重写同一模式。
步骤依据
该等式直接显示在定义框中。
视频直接表达

结论

一个序列的一般生成函数，是将每个 $n\ge 0$ 对应的 $a_n$ 作为 $x^n$ 的系数所得到的形式幂级数。

从帕斯卡三角形的行到（ $1+x$ ）^n

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片写出该行的生成函数，然后写出其等于( $1+x$ )^n的等式。
声音
观察依据
主讲人指出帕斯卡三角形的第n行给出一个有限多项式，且该生成函数可因式分解为( $1+x$ )^n。

待核验内容

该片段陈述了这一恒等式，但并未逐步证明它。

直观解释

步骤

公式
$\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}$
解释
从音频中指出的帕斯卡三角形第n行这一有限数列出发。
步骤依据
依据幻灯片上显示的文字及语音中的识别说明。
视频直接表达
公式
$\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n$
解释
将该行的第k个元素作为 $x^k$ 的系数，从而构造其生成函数。
步骤依据
依据该片段早先展示的生成函数定义。
视频直接表达
公式
$(1+x)^n$
解释
认出所得多项式即为（ $1+x$ ）^n的二项式展开式。
步骤依据
幻灯片上显示的等式；该片段未提供其背后的证明。
视频直接表达

结论

帕斯卡三角形第n行的生成函数是（ $1+x$ ）^n。

推导仅使用便士的找零数列

依据清楚

视频直接表达

来源依据

声音
观察依据
说话人从可用的便士数量出发，推导出每个美分金额对应的组合数。
公式
观察依据
幻灯片展示了所得数列：1,1,1,1,1,1,1,0,0,0, $\ldots$ 。

直观解释

步骤

公式
$\text{amount}=c,\quad 0\le c\le 7$
解释
考虑仅用便士凑出 c 分钱，且最多只有7枚便士可用。
步骤依据
幻灯片与音频中给出的问题设定。
视频直接表达
公式
$1\text{ way}$
解释
对每个这样的 c，恰好只有一种选择：使用 c 枚便士。
步骤依据
每枚便士价值1分，因此便士的数量由目标金额唯一确定。
依据视频推导
公式
$\text{amount}=c,\quad c>7$
解释
现在考虑大于7分的金额。
步骤依据
继续按分进行相同编号。
视频直接表达
公式
$0\text{ ways}$
解释
任何超过7分的金额都无法仅用七枚便士凑出。
步骤依据
七枚便士所能达到的最大金额是7分。
依据视频推导
公式
$1,1,1,1,1,1,1,0,0,0,\ldots$
解释
读取 $c = 0$ 、1、2、… 对应的计数，即可得到所展示的序列。
步骤依据
合并前述两种情况。
视频直接表达

结论

仅用便士的找零序列是 1 对应于 0 到 7 美分，并 0此后。

推导仅使用镍币的找零序列

依据清楚

视频直接表达

来源依据

声音
观察依据
说话人列举了使用0枚、1枚或2枚镍币所能得到的所有可能总额。
公式
观察依据
幻灯片展示了所得序列1,0,0,0,0,1,0,0,0,0,1,0,0, $\ldots$ 。

直观解释

步骤

公式
$\text{use }j\text{ nickels},\quad j\in\{0,1,2\}$
解释
由于仅有两枚镍币可用，所用镍币数量只能是0、1或2。
步骤依据
问题设定来自幻灯片与音频。
视频直接表达
公式
$5j\text{ cents}$
解释
使用 j 枚镍币恰好产生5j 分。
步骤依据
每枚镍币价值5分。
依据视频推导
公式
$0,5,10$
解释
因此，唯一可实现的金额为0分、5分和10分。
步骤依据
将 $j = 0$ 、1、2代入。
依据视频推导
公式
$1,0,0,0,0,1,0,0,0,0,1,0,0,\ldots$
解释
按美分索引得到1在0，5，以及10和0其余位置。
步骤依据
与幻灯片上显示的序列一致。
视频直接表达

结论

仅使用五美分硬币的找零序列为1在美分处0，5，以及10和0 否则。

从项的乘积中推导出凑出6美分的两种方式

依据清楚

视频直接表达

来源依据

声音
观察依据
凑出六美分的两种方法分别是：一枚便士加一枚五美分硬币（对应x与x的五次方），或六枚便士加零枚五美分硬币。
公式
观察依据
幻灯片要点显示：1枚便士和1枚五美分硬币—— $x \cdot x^5$ ；6枚便士和0枚五美分硬币—— $x^6 \cdot 1$ 。

直观解释

步骤

公式
$x \cdot x^5 = x^6$
解释
选取1枚便士和1枚五美分硬币，分别贡献指数1和5，其乘积的指数为6。
步骤依据
幂的乘法运算使指数相加。
视频直接表达
公式
$x^6 \cdot 1 = x^6$
解释
选取6枚便士和0枚五美分硬币，分别贡献指数6和0，其乘积的指数同样为6。
步骤依据
乘以1不改变该项。
视频直接表达
公式
$2x^6$
解释
这些是唯一展示出的、能得到指数6的方式，因此 $x^6$ 的系数为2。
步骤依据
展开后合并同类项。
依据视频推导

结论

恰好有 2组成6美分的方法数，使用7 pennies 且 2 nickels.

展开组合生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片展示了该乘积多项式的完整展开式。
声音
观察依据
“好，我们来把它展开，得到这个展开式”

视觉说明

步骤

公式
$(1+x+x^2+x^3+x^4+x^5+x^6+x^7)(1+x^5+x^{10})$
解释
从便士和镍币的生成函数的乘积开始。
步骤依据
独立硬币组的组合生成函数的定义。
视频直接表达
公式
$=1 + x + x^2 + x^3 + x^4 + 2x^5 + 2x^6 + 2x^7 + x^8 + x^9 + 2x^{10} + 2x^{11} + 2x^{12} + x^{13} + x^{14} + x^{15} + x^{16} + x^{17}$
解释
分配并合并同类幂次的 x，得到屏幕上显示的多项式。
步骤依据
多项式乘法及同类项合并。
视频直接表达
公式
$[x^6]=2,\;[x^{10}]=2,\;[x^{12}]=2,\;[x^{13}]=1$
解释
从展开式中读取指定系数，以回答特定的美分金额问题。
步骤依据
生成函数的系数表示所求组合的数量。
视频直接表达

结论

展开后的多项式编码了用0到17美分中每种金额的组成方法数，所用硬币为7 pennies 且 2 nickels.

从有限多项式推导出凑出 32 美分的方法数。

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人先对每种硬币的数量加以限制，再写出四个有限多项式，然后指出：将它们相乘，并提取 $x^{32}$ 的系数。
图示
观察依据
幻灯片展示了四个有限多项式，随后是 Sage 代码：expand( $P*N*D*Q$ ).coefficient( $x^(32)$ )，输出结果为 17。

数值验证

步骤

公式
$1+x+x^2+\cdots+x^{32}$
解释
将便士的选择编码为从 0 枚到 32 枚。
步骤依据
每枚便士贡献 1 美分，因此 k 枚便士共贡献 k 美分。
视频直接表达
公式
$1+x^5+x^{10}+\cdots+x^{30}$
解释
将五美分硬币的选择编码至不超过 5 的最大 32 的倍数。
步骤依据
每枚镍币贡献5美分。
视频直接表达
公式
$1+x^{10}+x^{20}+x^{30}$
解释
编码一角硬币的选择，直至30美分。
步骤依据
每枚一角硬币贡献10美分。
视频直接表达
公式
$1+x^{25}$
解释
编码二十五美分硬币的选择：0枚或1枚。
步骤依据
两枚二十五美分硬币将超过32美分。
视频直接表达
公式
$(1+x+x^2+\cdots+x^{32})(1+x^5+x^{10}+\cdots+x^{30})(1+x^{10}+x^{20}+x^{30})(1+x^{25})$
解释
将四个因子相乘，以组合彼此独立的硬币选择。
步骤依据
乘积中的一项从每个因子中各选一个指数，所得总美分数等于所选各指数之和。
视频直接表达
公式
$\operatorname{coeff}_{x^{32}}\bigl((1+x+x^2+\cdots+x^{32})(1+x^5+x^{10}+\cdots+x^{30})(1+x^{10}+x^{20}+x^{30})(1+x^{25})\bigr)=17$
解释
读取 $x^{32}$ 项的系数；幻灯片中 Sage 的计算结果为17。
步骤依据
该系数表示有多少种指数选取方式使其和为32，即有多少种硬币组合可凑出32美分。
视频直接表达

结论

有限多项式法得出 17 种方式凑出 32 美分。

从单一目标金额到完整的生成函数

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人提问为何不直接使用多项式，并回答：无限生成函数能一次性涵盖全部算术结构。
图示
观察依据
该幻灯片用无穷级数 $P(x)$ 、 $N(x)$ 、 $D(x)$ 、 $Q(x)$ 替代截断的有限多项式，并定义 $C(x) = P(x)N(x)D(x)Q(x)$ 。

直观解释

步骤

公式
$c_n = \text{number of ways to make } n \text{ cents}$
解释
引入一个以目标金额 n 为下标的完整序列，而非仅考虑 $n = 32$ 。
步骤依据
这是新幻灯片上展示的定义。
视频直接表达
公式
$P(x)=1+x+x^2+x^3+\cdots,\; N(x)=1+x^5+x^{10}+x^{15}+\cdots,\; D(x)=1+x^{10}+x^{20}+x^{30}+\cdots,\; Q(x)=1+x^{25}+x^{50}+x^{75}+\cdots$
解释
将每种硬币对应的有限多项式替换为其无穷版本。
步骤依据
取消截断后，同一构造对所有 n 都适用，而不仅限于 32。
视频直接表达
公式
$C(x)=P(x)N(x)D(x)Q(x)$
解释
通过将四个级数相乘，将整个序列打包成一个生成函数。
步骤依据
乘积中 $x^n$ 的系数，表示从四个级数中各选一个指数、其和恰好为 n 的选择方式数。
视频直接表达

结论

无穷生成函数推广了有限多项式的技巧，使得所有值 $c_n$ 同时被编码。

从单种硬币的因子出发推导完整生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片依次展示 $P(x)$ 、 $N(x)$ 、 $D(x)$ 、 $Q(x)$ ，然后显示“于是 $C(x) = P(x)\cdot N(x)\cdot D(x)\cdot Q(x)$ ”。
声音
观察依据
讲师描述了先分别考虑仅使用一种硬币的情形，再将它们全部相乘，从而得到 $c_n$ 的生成函数。

直观解释

步骤

公式
$P(x)=1+x+x^2+x^3+\cdots$
解释
从仅使用便士的生成函数开始：选择0、1、2……枚便士，分别对应0、1、2、3……美分的价值。
步骤依据
幻灯片上直接展示。
视频直接表达
公式
$N(x)=1+x^5+x^{10}+x^{15}+\cdots$
解释
类似地，仅使用镍币时，所贡献的价值是5美分的倍数。
步骤依据
幻灯片上直接展示。
视频直接表达
公式
$D(x)=1+x^{10}+x^{20}+x^{30}+\cdots$
解释
仅使用角币时，所贡献的价值是10美分的倍数。
步骤依据
幻灯片上直接展示。
视频直接表达
公式
$Q(x)=1+x^{25}+x^{50}+x^{75}+\cdots$
解释
仅使用二角五分币时，所贡献的价值是25美分的倍数。
步骤依据
幻灯片上直接展示。
视频直接表达
公式
$C(x)=P(x)\cdot N(x)\cdot D(x)\cdot Q(x)$
解释
将四种独立的单币种生成函数相乘，即可得到涵盖全部四种硬币组合的生成函数。
步骤依据
幻灯片上已陈述，并由讲师口头解释。
视频直接表达

结论

序列 $c_n$ 所需的生成函数，即为这四个单币种级数的乘积。

例题详解 · 13

斐波那契生成函数示例

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片列出：序列：0, 1, 1, 2, 3, 5, 8, 13, $\ldots$ ；生成函数： $0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots$ 。
声音
观察依据
主讲人指出该序列为斐波那契数列，并说明各项成为幂级数的系数。

题目

将斐波那契数列编码为一个生成函数。

已知条件

序列：0, 1, 1, 2, 3, 5, 8, 13, $\ldots$
将各项依次用作 x 的各次幂的系数。

目标

写出对应的生成函数。

步骤

公式
$0, 1, 1, 2, 3, 5, 8, 13, \ldots$
解释
按顺序列出给定的数列各项。
步骤依据
直接在幻灯片上显示并由讲解者口头读出。
视频直接表达
公式
$0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots$
解释
将第 k 项与 $x^k$ 的系数对应起来，起始项为 $x^0$ 。
步骤依据
这是讲解者陈述并同时在所展示公式中可见的构造规则。
视频直接表达

结果

$0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots$

检验

所展示级数的各项系数依次恰好为0、1、1、2、3、5、8、13，与上方数列行一一对应。

全为一的数列示例

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片上写着‘1, 1, 1, 1, 1, $\ldots$ 的生成函数：’后接 $1 + x + x^2 + x^3 + \cdots$ 。
声音
观察依据
主讲人将此例朗读为“全一序列”的生成函数。

题目

求常数数列1,1,1,1,1, $\ldots$ 的生成函数。

已知条件

数列：1, 1, 1, 1, 1, $\ldots$

目标

写出它的生成函数。

步骤

公式
$1, 1, 1, 1, 1, \ldots$
解释
该数列的每一项都是1。
步骤依据
如幻灯片所示。
视频直接表达
公式
$1 + x + x^2 + x^3 + \cdots$
解释
由于每个系数都是1，因此每个 x 的幂次都以系数1出现。
步骤依据
直接应用定义 $A(x)=\sum_{n=0}^{\infty}a$ _nx^n，其中 $a_n=1$ 。
视频直接表达

结果

$1 + x + x^2 + x^3 + \cdots$

检验

每个显示的系数都等于 1, matching the all-ones sequence.

计数数列示例

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片上写着‘数列1, 2, 3, 4, $\ldots$ 的生成函数：’后接 $1 + 2x + 3x^2 + 4x^3 + \cdots$ 。
声音
观察依据
主讲人称其为计数数列的生成函数，并朗读了该级数。

待核验内容

视频片段在主讲人说完最后一句解释性句子前就中断了。

题目

求该数列1,2,3,4, $\ldots$ 的生成函数。

已知条件

数列：1, 2, 3, 4, $\ldots$

目标

写出它的生成函数。

步骤

公式
$1, 2, 3, 4, \ldots$
解释
按顺序列出计数数。
步骤依据
在幻灯片上给出并口头念出。
视频直接表达
公式
$1 + 2x + 3x^2 + 4x^3 + \cdots$
解释
若从 1 开始索引，则将第n项附于 $x^{n-1}$ 上，等价地附于 $a_0=1$ , $a_1=2$ , $a_2=3$ ，…到 $x^0$ , $x^1$ , $x^2$ , $\ldots$ .
步骤依据
这是幻灯片上显示的系数模式，且与序列从0重新索引后的通用定义相匹配。
视频直接表达

结果

$1 + 2x + 3x^2 + 4x^3 + \cdots$

检验

从该级数中逐项读出的系数依次为1、2、3、4、 $\ldots$ 。

序列1,2,1,0,0,…的多项式生成函数。

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片给出：‘序列1,2,1,0,0, $\ldots$ 的生成函数为：’以及等式 $1+2x+x^2+0+0+\cdots=1+2x+x^2$ 。
声音
观察依据
主讲人以序列1,2,1,0,0,0,…为例，说明什么是最终为零的无穷序列。

题目

求无穷序列1,2,1,0,0,…的生成函数。

已知条件

序列：1,2,1,0,0,…
开场幻灯片中给出的生成函数定义。

目标

将生成函数化为最简多项式形式。

步骤

公式
$1+2x+x^2+0x^3+0x^4+\cdots$
解释
将序列的第n项与 $x^n$ 相乘。
步骤依据
根据定义， $A(x)=\sum_{n=0}^{\infty}a$ _nx^n。
依据视频推导
公式
$1+2x+x^2+0+0+\cdots=1+2x+x^2$
解释
省略所有系数为零的项，得到一个有限多项式。
步骤依据
音频中明确指出，并在幻灯片上同时显示。
视频直接表达

结果

1加2乘以x加x的2次方

检验

$x^0$ 的系数是1， $x^1$ 的系数是2， $x^2$ 的系数是1，所有更高次幂的系数均为0，与给定序列一致。

帕斯卡三角形第 n 行的生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片给出了组合数序列 $\binom{n}{0}$ , $\binom{n}{1}$ , $\ldots$ , $\binom{n}{n}$ 的生成函数： $\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n=(1+x)^n$ 。
声音
观察依据
主讲人称其为‘另一个著名的有限序列’，并指出它就是帕斯卡三角形的第 n 行。

题目

求有限序列 $\binom{n}{0}$ , $\binom{n}{1}$ , $\ldots$ , $\binom{n}{n}$ 的生成函数。

已知条件

有限序列： $\binom{n}{0}$ , $\binom{n}{1}$ , $\ldots$ , $\binom{n}{n}$ 。
生成函数的定义。

目标

写出生成函数并将其因式分解。

步骤

公式
$\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n$
解释
将二项式系数依次作为各项的系数。
步骤依据
直接应用生成函数的定义。
视频直接表达
公式
$(1+x)^n$
解释
识别该多项式为 ( $1+x$ )^n 的二项式展开。
步骤依据
幻灯片上显示的等式；本片段并未在此处证明二项式定理。
视频直接表达

结果

（1加 x）的 n 次方

检验

展开 ( $1+x$ )^n 得到的系数为 $\binom{n}{0}$ , $\binom{n}{1}$ , $\ldots$ , $\binom{n}{n}$ ，与输入序列一致。

直接枚举凑出 6 美分的所有方式。

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片题目框询问：用 6 分钱硬币、7 枚便士和 2 枚镍币，共有多少种组合方式？并以项目符号列出“1 枚便士和 1 枚镍币”以及“6 枚便士”。
声音
观察依据
说话人指出，这是凑出六美分的两种方法。

题目

你有 7 枚便士和 2 枚镍币。问：能有多少种方法凑出恰好 6 美分？

已知条件

可供使用的便士数量为 7 枚。
可供使用的镍币数量为 2 枚。
一枚便士价值 1 美分。
一枚镍币价值 5 美分。

目标

统计凑出恰好 6 美分的所有方法数。

步骤

公式
$1\text{ penny}+1\text{ nickel}=1+5=6\text{ cents}$
解释
一种可行的组合是使用一枚便士和一枚镍币。
步骤依据
利用硬币面值进行数值验证。
视频直接表达
公式
$6\text{ pennies}=6\text{ cents}$
解释
另一种有效的组合使用六枚便士。
步骤依据
至少有六枚便士可用。
视频直接表达
公式
$2\text{ ways}$
解释
幻灯片上仅列出了这些可能性。
步骤依据
幻灯片明确列出了且仅列出了这两条要点。
视频直接表达

结果

2种方式

检验

没有其他至多 7 枚便士和至多 2 枚镍币的组合被列在该 6 分目标的幻灯片上。

仅用便士凑出所有美分金额的方式数序列

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片展示了便士序列1,1,1,1,1,1,1,0,0,0, $\ldots$ 。
声音
观察依据
主讲人解释了为何从0美分到7美分的每个金额都恰好有一种表示方式，而更大的金额则无法表示。

题目

以美分为索引，将仅用七枚便士凑出0,1,2,3, $\ldots$ 美分的方式数记录为一个序列。

已知条件

只能使用便士。
最多可使用7枚便士。

目标

生成所有非负分值金额的完整找零序列。

步骤

公式
$c=0,1,\ldots,7$
解释
对于从0至7美分的每一金额，恰好使用c枚一美分硬币。
步骤依据
这是可行且唯一的，因为一美分硬币的面值为1。
依据视频推导
公式
$c>7$
解释
对于超过7美分的金额，任取至多七枚一美分硬币均无法达到该目标。
步骤依据
七枚便士所能得到的最大金额是7美分。
依据视频推导
公式
$1,1,1,1,1,1,1,0,0,0,\ldots$
解释
依次读出 $c=0$ 、1、2、……时的计数值。
步骤依据
合并上述两种情况，并与屏幕上显示的序列一致。
视频直接表达

结果

1，1，1，1，1，1，1，0，0，0，……

检验

前七项对应金额0至7分，后续的零则对应那些无法实现的更大金额。

仅用镍币凑出所有美分金额的方式序列

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片展示了镍币序列：1、0、0、0、0、1、0、0、0、0、1、0、0、……
声音
观察依据
主讲人解释道：使用0枚、1枚或2枚镍币，分别可得到0美分、5美分或10美分，且无法得到其他金额。

题目

以分为索引，记录使用仅有的两枚镍币凑出0、1、2、3、……分的方案数。

已知条件

只能使用镍币。
最多可使用2枚镍币。
一枚镍币价值5分。

目标

生成所有非负分值金额对应的完整找零序列。

步骤

公式
$j=0,1,2$
解释
所用镍币的数量只能是0、1或2。
步骤依据
仅有两枚镍币可用。
视频直接表达
公式
$5j=0,5,10$
解释
这些选择恰好产生0、5和10分。
步骤依据
每枚镍币贡献5分。
依据视频推导
公式
$1,0,0,0,0,1,0,0,0,0,1,0,0,\ldots$
解释
按美分索引得到 1 在 0，5，以及 10 和 0 其余位置。
步骤依据
与屏幕上显示的序列一致。
视频直接表达

结果

1，0，0，0，0，1，0，0，0，0，1，0，0，……

检验

仅用至多两枚镍币时，只能凑出5的倍数且不超过10美分的金额，因此所有其他美分位置的值必须为0。

用6美分，使用7 pennies 且 2五美分硬币

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片标题：凑零钱；提示：你有7枚便士和2枚镍币。凑出6美分有多少种方法？
声音
观察依据
讲师讲解两个对应的乘积 $x*x^5$ 和 $x^6*1$ 。

题目

已知有7枚便士和2枚镍币，求凑出6美分的方法数。

已知条件

可使用的便士数量为7枚
可使用的镍币数量为2枚
目标金额为6美分

目标

计算总金额为6美分的有效硬币组合数。

步骤

公式
$1\text{ penny }+1\text{ nickel}$
解释
一种有效组合是使用1枚便士和1枚镍币。
步骤依据
$1+5=6$ ，且两种硬币的数量均未超过可用数量。
视频直接表达
公式
$6\text{ pennies }+0\text{ nickels}$
解释
另一种有效组合是使用6枚便士且不使用镍币。
步骤依据
$6+0=6$ ，且 $6\le 7$ 。
视频直接表达
公式
$x\cdot x^5 + x^6\cdot 1 = 2x^6$
解释
在生成函数形式中，这两种选择各自贡献一个 $x^6$ 因子。
步骤依据
生成函数的乘法法则及同类项合并。
依据视频推导

结果

2种方式

检验

下一页展开的乘积显示系数 2 在 $x^6$ 。

从展开后的生成函数中读取多个答案

依据清楚

视频直接表达

来源依据

公式
观察依据
展开后的多项式包含 $2x^{10}$ 、 $2x^{12}$ 、 $x^{13}$ ，并以 $x^{17}$ 结尾。
声音
观察依据
“凑出十美分有两法，凑出十二美分也有两法，凑出十三美分仅有一法。凑出十八美分则无法实现，因为金额过大。”

题目

利用7枚便士和2枚镍币对应的展开乘积，确定凑出10、12、13和18美分的方式数。

已知条件

由( $1+x$ +⋯+ $x^7$ )( $1+x^5+x^{10}$ )展开所得的多项式。
图中显示的最大指数为17。

目标

提取指定美分数额对应的系数。

步骤

公式
$[x^{10}]=2$
解释
在所展示的展开式中， $x^{10}$ 的系数是2。
步骤依据
直接从多项式中读取。
视频直接表达
公式
$[x^{12}]=2$
解释
在所展示的展开式中， $x^{12}$ 的系数是2。
步骤依据
直接从多项式中读取。
视频直接表达
公式
$[x^{13}]=1$
解释
在所展示的展开式中， $x^{13}$ 的系数是1。
步骤依据
直接从多项式中读取。
视频直接表达
公式
$[x^{18}]=0$
解释
不存在 $x^{18}$ 项，因为最大指数为17。
步骤依据
缺失的项其系数为0。
依据视频推导

结果

10美分：2种方法；12美分：2种方法；13美分：1种方法；18美分：0种方法

检验

与讲师口述的示例及屏幕上展示的展开式一致。

建立32美分找零问题的生成函数。

依据清楚

视频直接表达

来源依据

公式
观察依据
新幻灯片：使用便士、一角硬币、五分硬币和二角五分硬币，凑出32美分共有多少种方法？并列出四个生成函数。
声音
观察依据
“我们稍微拓展一下找零问题……凑出三十二美分共有多少种方法？”

待核验内容

该片段在解法计算完成前结束。

题目

为使用便士、五分硬币、一角硬币和二角五分硬币凑出32美分的方法数，建立一个生成函数解法。

已知条件

便士： $1 + x + x^2$ + ⋯ + $x^{32}$
五分硬币： $1 + x^5 + x^{10}$ + ⋯ + $x^{30}$
一角硬币： $1 + x^{10} + x^{20} + x^{30}$
二角五分硬币： $1 + x^{25}$
目标金额：32美分

目标

将问题表示为从生成函数乘积中提取特定系数。

步骤

公式
$P(x)=1+x+x^2+\cdots+x^{32}$
解释
对不超过32美分的金额，使用便士的生成函数。
步骤依据
每枚便士贡献1美分，且所示多项式允许最多使用32枚便士。
视频直接表达
公式
$N(x)=1+x^5+x^{10}+\cdots+x^{30}$
解释
使用五美分硬币的生成函数表示 5 的倍数，最高到 30 美分。
步骤依据
每枚镍币贡献5美分。
视频直接表达
公式
$D(x)=1+x^{10}+x^{20}+x^{30}$
解释
使用十美分硬币的生成函数表示 10 的倍数，最高到 30 美分。
步骤依据
每枚角币贡献10美分。
视频直接表达
公式
$Q(x)=1+x^{25}$
解释
使用允许含0枚或1枚四分之一美元硬币的二十五美分硬币生成函数。
步骤依据
每枚四分之一美元硬币贡献25美分。
视频直接表达
公式
$[x^{32}]\bigl(P(x)N(x)D(x)Q(x)\bigr)$
解释
所求的计数值即为四个生成函数乘积中 $x^{32}$ 项的系数。
步骤依据
组合相互独立的硬币选择时使用的乘法法则。
依据视频推导

结果

仅设置： $x^{32}$ 在 $(1+x+\cdots+x^{32})(1+x^5+\cdots+x^{30})(1+x^{10}+x^{20}+x^{30})(1+x^{25})$ 中的系数

检验

本片段未完成；视频在展开或计算前就中断了。

例题：凑出 32 美分

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片提问：‘使用便士、一角硬币、五分硬币和二角五分硬币，凑出 32 美分有多少种方法？’随后给出有限多项式及 Sage 代码。
声音
观察依据
主讲人逐步讲解每种硬币的数量限制、多项式建模过程以及系数提取方法。

题目

用便士、一角硬币、五分硬币和二角五分硬币凑出 32 分钱有多少种方法？

已知条件

面额分别为：1美分、5美分、10美分和25美分。
目标总金额为：32美分。
组合不考虑顺序。

目标

求凑出32美分的不同硬币组合数。

步骤

公式
$1+x+x^2+\cdots+x^{32}$
解释
使用此因子表示便士。
步骤依据
最多可使用32枚便士，而不会超过目标金额。
视频直接表达
公式
$1+x^5+x^{10}+\cdots+x^{30}$
解释
使用此因子表示镍币。
步骤依据
最多可使用六枚镍币，共计30美分。
视频直接表达
公式
$1+x^{10}+x^{20}+x^{30}$
解释
使用此因子表示角币。
步骤依据
最多可使用三枚角币，共计30美分。
视频直接表达
公式
$1+x^{25}$
解释
使用此因子表示四分之一美元硬币。
步骤依据
最多只能使用一枚二十五美分硬币。
视频直接表达
公式
$P=sum([x^i for i in range(33)])$
解释
在 Sage 中定义便士多项式。
步骤依据
range(33) 生成 $i = 0$ ,1,…,32。
视频直接表达
公式
$N=sum([x^(5*i) for i in range(7)])$
解释
在 Sage 中定义五美分硬币多项式。
步骤依据
range(7) 生成 $i = 0$ ,1,…,6，因此指数为 0,5,…,30。
视频直接表达
公式
$D=sum([x^(10*i) for i in range(3)])$
解释
在 Sage 中定义十美分硬币多项式。
步骤依据
range(3) 生成 $i = 0$ ,1,2，因此指数为 0,10,20,30。
视频直接表达
公式
$Q=sum([x^(25*i) for i in range(2)])$
解释
在 Sage 中定义二十五美分硬币多项式。
步骤依据
range(2) 生成 $i = 0$ ,1，因此指数为 0 和 25。
视频直接表达
公式
$expand(P*N*D*Q).coefficient(x^(32))$
解释
将这四个多项式相乘，并提取 $x^{32}$ 的系数。
步骤依据
该系数表示所有面值之和为 32 美分的组合数。
视频直接表达
公式
$17$
解释
屏幕上显示的答案是 17。
步骤依据
这是幻灯片上显示并口头陈述的输出内容。
视频直接表达

结果

对应的式子为：17

检验

幻灯片显示 Sage 的输出结果：“答案：17”，该结果是在计算 $x^{32}$ 的系数后得到的。

图示与动画 · 14

标题幻灯片与主讲人入场

依据清楚

视频直接表达

来源依据

图示
观察依据
紫色标题幻灯片上写着“生成函数”、“一部开放教育资源视频”以及“数石头！：科罗拉多州立大学组合数学导论”。
动画
观察依据
约在2秒时，主讲人从画面右侧入镜。

图中对象

紫色背景
白色标题文字
主讲人从右侧入镜

变化过程

静态标题卡淡出，主讲人走入画面。

不变量

课程品牌标识与主题标题持续显示，直至首张内容幻灯片出现。

数学含义

本开场环节确立本次讲座的主题为组合数学课程中的生成函数。

斐波那契数列示例幻灯片

依据清楚

视频直接表达

来源依据

图示
观察依据
标题为‘生成函数’的幻灯片上展示威尔夫名言、一行序列及一行生成函数。
动画
观察依据
主讲人在讲解时先指向序列，再指向级数。

图中对象

赫伯特·威尔夫名言
序列：0, 1, 1, 2, 3, 5, 8, 13, $\ldots$
生成函数： $0 + x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7 + \cdots$
主讲人

变化过程

注意力依次从名言转向序列，再转向所展示的级数。

不变量

数列的项与级数的系数保持相同的顺序对应。

数学含义

上方数列行与下方级数行的视觉配对表明：生成函数是通过将数列各项作为系数来构造的。

定义与示例幻灯片

依据清楚

视频直接表达

来源依据

图示
观察依据
标题为‘定义与示例’的幻灯片包含一个加框的定义，其下方有两行示例。
动画
观察依据
主讲人一边讲解变量选取，一边先指向加框公式，再指向示例。

图中对象

加框定义 $A(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a$ _nx^n
对应于 1,1,1,1,1, $\ldots$ 的示例
对应于 1,2,3,4, $\ldots$ 的示例
主讲人

变化过程

讲座从一个具体的实例出发，过渡到一般性定义，再延伸至两个更简单的实例。

不变量

所有示例均遵循定义中所示的‘系数—幂次’对应规则。

数学含义

该幻灯片将先前示例中的模式形式化为一般记号，然后在两个基础数列上检验该记号。

开场定义幻灯片

依据清楚

视频直接表达

来源依据

图示
观察依据
紫色幻灯片标题为“定义与示例”，其中包含一个框出的生成函数定义，以及其下方的两个示例行。

图中对象

标题“定义与示例”
框出的定义公式
两个生成函数示例行
主讲人位于右侧

变化过程

主讲人手势指向定义框。

不变量

所显示的定义在整个该时间段内持续可见。

数学含义

该视觉呈现先于任何示例讲解，确立了系数编码的一般规则。

多项式幻灯片

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片切换为“多项式”，并展示两个示例：一个终归为零的序列，以及帕斯卡三角形的第 n 行。

图中对象

标题：多项式
公式 $1+2x+x^2+0+0$ +⋯= $1+2x+x^2$
公式 $\binom{n}{0}+\binom{n}{1}x$ +⋯+ $\binom{n}{n}x^n=(1+x)^n$
主讲人边指边做手势

变化过程

主讲人先指向上方的多项式示例，再指向下方的二项式系数示例。

不变量

两个多项式示例在此期间始终保留在屏幕上。

数学含义

幻灯片直观对比了两类序列：一类是通项最终为零的一般序列，另一类是具有简洁生成函数因式分解形式的命名组合序列。

找零问题幻灯片

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片切换至‘找零问题’，包含一个问题框、两条要点式解法，以及分别表示便士和镍币的两个序列。

图中对象

标题：找零问题
问题框涉及7枚便士和2枚镍币
要点：‘1枚便士和1枚镍币’以及‘6枚便士’
便士序列线
镍币序列线
主讲人沿两条序列指向示意

变化过程

主讲人先指向问题框，再指向便士序列，最后沿镍币序列描画示意。

不变量

两个显式解的要点条目及两条序列始终保留在画面中，直至本片段结束。

数学含义

画面从单个目标金额（6美分）过渡到完整序列，该序列编码了每一美分金额对应的组合数，并将便士与镍币的贡献分别呈现。

第一张幻灯片从数列过渡到生成函数

依据清楚

视频直接表达

来源依据

图示
观察依据
紫色幻灯片标题为“凑硬币”，显示6美分的提示框、两个项目符号示例、两个数列，然后是两个生成函数。
动画
观察依据
约在2秒处，下方文字从“数列”变为“生成函数”，而上方的项目符号保持不变。

图中对象

标题：“凑硬币”
提示框内容关于7枚便士和2枚镍币
关于6美分的项目符号示例
展示的两个数列
展示的两个生成函数
主讲人位于右侧

变化过程

初始状态显示便士与镍币对应的数列。
后续状态将这些行替换为对应的生成函数。
主讲人先指向便士多项式，再指向镍币多项式。

不变量

顶部提示语及下方两个带项目符号的示例在整个时段内持续可见。
整体主题仍是用 6 美分硬币凑出 7便士和2镍币。

数学含义

视觉过渡演示了计数序列如何被编码为一个多项式，其中各项的指数对应所表示的美分数额。

第二张幻灯片展示重新理解后的乘积及其展开式。

依据清楚

视频直接表达

来源依据

图示
观察依据
新幻灯片标题为“重新理解”，展示乘积问题及完全展开后的多项式。
动画
观察依据
主讲人横向示意展开式，并指向诸如 $2x^6$ 、 $2x^{10}$ 、 $2x^{12}$ 以及 $x^{13}$ 等项附近。

图中对象

标题：“重新理解”
提问：在该乘积中，有多少种方式得到 $x^{6}$ 项？
乘积表达式
展开后的多项式
底部注释提及11美分和13美分
右侧主讲人

变化过程

幻灯片内容从分别讨论生成函数转变为单一乘积问题。
完整展开后的多项式成为画面主要视觉焦点。
主讲人用手势示意从展开式中读取各项系数。

不变量

继续使用含7枚便士和2枚镍币的相同硬币找零情境。
当前讨论的数学对象仍是两个生成函数的乘积。

数学含义

幻灯片以可视化方式将组合问题转化为从一个多项式乘积中提取指定系数的问题。

第三张幻灯片引入更大的32美分找零问题

依据清楚

视频直接表达

来源依据

图示
观察依据
第三张幻灯片标题为“找零”，提问：用便士、一角硬币、五分硬币和二角五分硬币凑出32美分，同时列出四个生成函数。

待核验内容

仅展示问题设定；视频片段结束前未出现展开式。

图中对象

标题：“找零”
关于凑出32美分的提问
四种硬币（便士、镍币、一角硬币、二角五分硬币）的生成函数
主讲人位于画面右侧

变化过程

幻灯片切换为一道新题目，硬币种类由两种增至四种。
目标金额从6美分变为32美分。

不变量

所用方法仍是通过x的幂次编码的生成函数。
主讲人继续站在幻灯片旁讲解。

数学含义

这一视觉变化标志着：从一个小型的例题演示，推广至同一方法在更广泛情形下的应用。

初始的“找零问题”幻灯片

依据清楚

视频直接表达

来源依据

图示
观察依据
紫色教学幻灯片，标题为“找零问题”，框出的问题是凑出32美分，下方用四个黄色项目符号列出分别对应于便士、镍币、角币和四分之一美元硬币的有限多项式。
动画
观察依据
主讲人在讲解时，手势指向所列的多项式。

图中对象

标题：“找零问题”
框出的问题陈述
四行带项目符号的有限多项式
主讲人

变化过程

主讲人在解释每种硬币数量限制时，依次指向不同的多项式行。

不变量

此时间段内幻灯片内容保持不变。
目标金额固定为32美分。

数学含义

视觉布局将每种硬币面额分别表示为一个独立因子，帮助观众理解总组合数是若干独立选择的乘积。

Sage 计算叠加层

依据清楚

视频直接表达

来源依据

图示
观察依据
多项式列表下方出现一个白色代码框，内含五行 Sage 代码，输出结果为“Answer: 17”。
动画
观察依据
主讲人一边指向各行代码，一边讲解 range() 函数和系数提取操作。

图中对象

原始多项式列表
白色代码框
输出行“Answer: 17”
主讲人

变化过程

在数学表达式下方添加了一个代码块。
主讲人指出定义 P、N、D、Q 的各行代码，以及最后提取系数的命令。

不变量

四种硬币对应的多项式仍显示在代码上方。
题目陈述保持不变。

数学含义

叠加层将符号化的多项式模型转化为明确的计算机代数过程，并显示数值结果。

过渡到无穷生成函数

依据清楚

视频直接表达

来源依据

图示
观察依据
幻灯片切换至标题“生成函数”，其中包含一个带方框的定义：〔 $c_n$ 〕和〔 $C(x)$ 〕，四个无穷级数〔 $P(x)$ 〕、〔 $N(x)$ 〕、〔 $D(x)$ 〕、〔 $Q(x)$ 〕，以及公式〔 $C(x)=P(x)\cdot N(x)\cdot D(x)\cdot Q(x)$ 〕。
动画
观察依据
主讲人示意指向新定义及乘积公式。

图中对象

标题“生成函数”
带方框的〔 $c_n$ 〕和〔 $C(x)$ 〕定义
四个无穷级数
〔 $C(x)$ 〕的乘积公式
主讲人

变化过程

有限截断多项式被无穷级数取代。
引入〔 $c_n$ 〕和〔 $C(x)$ 〕的新定义。
乘积公式被呈现为核心结论。

不变量

仍使用相同的四种硬币面额进行建模。
变量 x 仍在指数中记录以分为单位的数值。

数学含义

视觉上的变化标志着从求解单个实例（32分）转向对所有 n 对应的答案序列进行编码。

易错点 · 10

将生成函数误当作普通的收敛函数

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人明确指出，该工具对于x的各个取值而言，未必是一个收敛函数。

误区

人们可能认为，以幂级数形式写出的生成函数，必然自动地为所考虑的x值定义出一个收敛的数值函数。

说明

本片段中，主讲人强调该对象被用作序列的“形式衣架”；收敛性并非首要关注点，也未被预先假定。

将x视作必需的数值变量

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人称x仅是一个形式变量，本质上只是一个符号，并随后指出任何符号都可使用。

误区

人们可能以为字母x在生成函数中天然具有作为数字的数学含义。

说明

视频将x呈现为一个占位符号，通过指数标记位置；该符号的名称仅为惯例，可以更换。

零系数无需写出

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人指出，形如 $0x^3$ 和 $0x^4$ 这样的项可被理解为‘根本未出现’，且‘零项无需写出’。

误区

有人可能认为，一个末尾带无穷多个零的无限序列，其生成函数仍需写出所有零项。

说明

本片段解释道：一旦序列最终恒为零，则对应的生成函数可通过省略零系数而写成有限多项式。

生成函数包含多项式

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人称，若以恰当方式理解，多项式便是生成函数的例子。

误区

人们或许会认为生成函数仅指无穷幂级数。

说明

本片段明确将多项式视为有限序列或最终为零序列的生成函数。

请勿将x视为待求解的未知数

时间近似

补充解释

来源依据

声音
观察依据
讲座中将x视作通过指数加法与系数读取来处理的对象，而非代入具体数值。
公式
观察依据
所有展示出的表达式均以x作为占位符，其指数编码金额。

待核验内容

视频并未明确提醒观众：切勿将x当作方程中的未知变量来理解。

误区

学生可能误以为这些多项式中的x是普通变量，其值必须被求出。

说明

这里的 x 是一个形式标记：其指数记录美分数，系数记录达成该金额的方式数。

缺失的幂次意味着其系数为0

依据清楚

视频直接表达

来源依据

声音
观察依据
“无法凑出十八美分，这个数额太大了”
公式
观察依据
所展示的展开式在 $x^{17}$ 处截止。

误区

学习者可能误以为只要某个金额未被明确讨论，就一定存在某种表示方式。

说明

若某幂次未出现在展开后的生成函数中，则其系数为0，表示该金额无法用给定的硬币凑出。

认为有限多项式已足以解决一般性问题

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人提问：‘那么无穷生成函数有什么用？我们为什么不能只用多项式？’并回答道：无穷生成函数能将全部这类算术信息一次性地加以概括。
图示
观察依据
幻灯片将此前的有限多项式与后续的无穷级数 $P(x)$ 、 $N(x)$ 、 $D(x)$ 、 $Q(x)$ 进行了对比。

误区

人们或许会认为，用于计算32分的截断多项式，就是硬币兑换问题中自然的最终工具。

说明

有限多项式仅能求解单一目标金额，而无穷生成函数则能一次性编码所有 $c_n$ ，因此同一乘积形式适用于所有 n，无需为每个新目标金额重新截断。

混淆组合与有序序列

时间近似

依据视频推导

来源依据

图示
观察依据
该设定为每种硬币类型设置一个因子，并将它们相乘，从而统计出每种硬币各使用多少枚的组合方式。
声音
观察依据
主讲人将问题表述为‘有多少种方法凑出32分’，其计算过程对应的是组合而非硬币抽取的序列。

待核验内容

该片段并未明确说明‘顺序无关’；这一点是从标准的生成函数模型及所展示的计算中推断得出的。

误区

学习者可能将‘凑零钱的方式数’理解为计算硬币交付顺序的不同种数。

说明

该多项式乘积所计数的是由所用便士、镍币、角币和四分之一美元硬币的数量所决定的无序组合，而非硬币序列的排列。

硬币供应无限与之对比硬币供应有限

依据清楚

依据视频推导

来源依据

字幕依据
观察依据
练习题明确说明“如果你有五个 splink 和两个 tonk”，这与之前针对无限量便士、镍币、角币和二角五分币所用的无穷级数不同。
声音
观察依据
主讲人将此前的无穷生成函数与本次新的受限练习进行对比。

误区

人们可能在每种硬币仅有固定数量可用时，仍沿用此前的无穷级数模式。

说明

当供应受限时，对应的因子必须是有限多项式，而非无穷级数；此处 splink 仅贡献至 $x^{10}$ ，tonk 仅贡献至 $x^{14}$ 。

并非所有金额都可实现

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人说：“不，你在 Splinktonk 星球上无法只给某人一分钱。”

误区

人们可能误以为只要使用了生成函数，就一定能凑出任意整数分值。

说明

当硬币面值为2和7时，某些金额（例如1美分）无法凑出；生成函数中对应这些金额的项系数直接为零。

概念关系 · 24

生成函数作为一列数字的晾衣绳 → 生成函数的正式定义

依据清楚

视频直接表达

来源依据

图示
观察依据
第一张幻灯片给出‘衣架’这一比喻性说法及一个具体的斐波那契数列示例；下一张幻灯片给出形式化定义。
声音
观察依据
主讲人从比喻与示例过渡到‘正式定义’。

特例

解释

非正式的‘衣架’描述，由后续公式 $A(x)=\sum_{n=0}^{\infty}a$ _nx^n予以精确化。

生成函数的正式定义 → 斐波那契数列编码为生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
斐波那契数列在一般性定义之前已展示出来，随后的定义框则以符号方式重述了相同的系数模式。

应用

解释

将一般定义应用于斐波那契数列，得到屏幕上显示的级数。

将 x 视为一个形式变量，而非收敛意义上的输入值 → 生成函数的正式定义

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人首先说明 x 是一个形式变量，随后又指出该符号可替换为 y 或其他占位符。

包含

解释

该定义以 x 作为形式变量，而此前的说明则解释了该符号在定义内部所起的作用。

生成函数的正式定义 → 常数数列1、1、1、……的生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
方框中的定义后紧跟着示例：‘1、1、1、1、1、 $\ldots$ 的生成函数： $1 + x + x^2 + x^3 + \cdots$ 。’

应用

解释

令 $a_n = 1$ in the general definition yields the displayed all-ones generating function.

生成函数的正式定义 → 计数数列1、2、3、4、……的生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
方框中的定义后紧跟着示例：‘1、2、3、4、 $\ldots$ 的生成函数： $1 + 2x + 3x^2 + 4x^3 + \cdots$ 。’

应用

解释

将计数数列作为系数序列代入一般定义，便得到屏幕上显示的级数。

生成函数的定义 → 最终为零的序列给出多项式型生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
定义幻灯片之后，给出多项式示例： $1+2x+x^2+0+0+\cdots=1+2x+x^2$ 。

应用

解释

最终为零序列的示例先应用生成函数的一般定义，再通过省略零系数进行化简。

最终为零的序列给出多项式型生成函数 → 帕斯卡三角形某一行的生成函数

依据清楚

视频直接表达

来源依据

公式
观察依据
两个示例均出现在标题‘多项式’之下，其中第二个是有限多项式生成函数。

特例

解释

帕斯卡三角形某一行的示例，是更普遍思想的一个特例：即最终为零序列或有限序列所对应的生成函数均为多项式。

帕斯卡三角形某一行的生成函数 → 因式分解生成函数有助于理解系数

依据清楚

视频直接表达

来源依据

声音
观察依据
在陈述因式分解（ $1+x$ )^n 后，讲者立即指出，对生成函数进行因式分解将成为一种强有力的工具。

证明依赖

解释

二项式行的因式分解，作为讲者所提出的‘对生成函数因式分解有助于理解其系数’这一论断的动机示例。

硬币找零计数问题的设定 → 仅使用便士的换零钱序列

依据清楚

视频直接表达

来源依据

公式
观察依据
‘凑硬币’幻灯片首先提出6分问题，然后分别列出只用便士和只用镍币的序列。

包含

解释

整个凑硬币问题被分解为子问题：对每一分数额，单独计算仅用便士的组合方式数目。

硬币找零计数问题的设定 → 仅使用五美分硬币的找零序列

依据清楚

视频直接表达

来源依据

公式
观察依据
同一张幻灯片还在便士序列下方列出了仅用镍币的序列。

包含

解释

整个凑硬币问题也被分解为另一子问题：对每一分数额，单独计算仅用镍币的组合方式数目。

生成函数作为一种从序列到多项式的编码方式 → 最多使用7枚便士的生成函数

依据清楚

视频直接表达

来源依据

声音
观察依据
讲师首先为两个序列引入生成函数，然后写出并解释便士多项式。
公式
观察依据
序列行被便士生成函数所替代。

应用

解释

将生成函数的一般定义应用于便士计数序列。

生成函数作为一种从序列到多项式的编码方式 → 最多使用2枚镍币的生成函数

依据清楚

视频直接表达

来源依据

声音
观察依据
讲师以类似方式，从允许的镍币总金额出发构造镍币生成函数。
公式
观察依据
镍币序列被替换为 $1+x^5+x^{10}$ 。

应用

解释

相同的编码思想被应用于镍币计数序列。

问题定位 · 30

根据本讲，什么是生成函数？

依据清楚

视频直接表达

来源依据

公式
观察依据
威尔夫引文幻灯片与定义方框均阐述了生成函数的含义。

涉及知识点

生成函数作为一列数字的晾衣绳
生成函数的正式定义

斐波那契数列是如何转化为生成函数的？

依据清楚

视频直接表达

来源依据

公式
观察依据
斐波那契数列及其对应的级数一同呈现在幻灯片上。

涉及知识点

斐波那契数列编码为生成函数
从斐波那契数列构造其生成函数
斐波那契生成函数示例

为什么将 x 视为一个形式变量，而不是一个具体的数？

依据清楚

视频直接表达

来源依据

声音
观察依据
主讲人解释道，x 是一个形式变量，可被替换为其他符号。

涉及知识点

将 x 视为一个形式变量，而非收敛意义上的输入值
此处生成函数无需被视为收敛函数
形式变量的名称是任意的

序列的生成函数的标准公式是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
定义框中显示 $A(x) = a_0 + a_1x + a_2x^2 + \cdots = \sum_{n=0}^{\infty} a_n x^n$ 。

涉及知识点

生成函数的正式定义
从一个数列过渡到一般的生成函数记号

序列 1,1,1, $\ldots$ 和 1,2,3,4, $\ldots$ 的生成函数分别是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
定义下方的幻灯片上出现了两个示例行。

涉及知识点

常数数列1、1、1、……的生成函数
计数数列1、2、3、4、……的生成函数
全为一的数列示例
计数数列示例

数列的生成函数的定义是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
定义框开启显示。

涉及知识点

生成函数的定义

为什么一个最终为零的无穷数列可以具有多项式形式的生成函数？

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者说明省略零项的原因。

涉及知识点

最终为零的序列给出多项式型生成函数
零系数无需写出

帕斯卡三角形第n行的生成函数是什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片展示二项式系数的生成函数等于（ $1+x$ ）^n。

涉及知识点

帕斯卡三角形某一行的生成函数

为什么讲师说因式分解生成函数是有用的？

依据清楚

视频直接表达

来源依据

声音
观察依据
讲解者指出因式分解生成函数的实用性。

涉及知识点

因式分解生成函数有助于理解系数

有多少种方法可以用6美分由7 pennies 且 2这个例子中有多少个五美分硬币？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片列出关于6美分的两个要点式解法。

涉及知识点

硬币找零计数问题的设定

在硬币示例中，数列1,1,1,1,1,1,1,0,0,0,... 表示什么？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片按美分对便士数列进行标注。

涉及知识点

仅使用便士的换零钱序列

为什么仅使用五美分硬币的序列1美分处0，5，以及10和0其他位置？

依据清楚

视频直接表达

来源依据

公式
观察依据
幻灯片按美分标注镍币序列。

涉及知识点

仅使用五美分硬币的找零序列

覆盖情况与待核验内容

已覆盖 · 标题页与主讲人登场确立了本次讲座的主题；此时尚未出现任何数学公式。

已覆盖 · 威尔夫（Wilf）引言、斐波那契示例，以及对 x 作为形式变量的解释。

已覆盖 · 带框的一般定义，外加两个示例；最后一句话虽被截断，但此时间段内所展示的数学内容已完整。

已覆盖 · 生成函数的开篇定义及其符号形式。

已覆盖 · 来自终归为零序列的一个多项式示例，并说明零项可以省略。

已覆盖 · 帕斯卡三角形某一行的示例、其因式分解形式( $1+x$ )^n，以及关于生成函数可因式分解的口头陈述。

已覆盖 · 一个具体的硬币找零问题，直接枚举出凑出6美分的两种方式。

已覆盖 · 推导并列出仅使用便士时对所有美分金额的找零序列。

已覆盖 · 推导并列出仅使用镍币时对所有美分金额的找零序列。

已覆盖 · 起始幻灯片展示了6分问题、两个示例组合以及两个计数序列。

已覆盖 · 幻灯片切换至两个生成函数，讲师解释各项乘积如何给出凑出6分的方式数。

已覆盖 · 重构幻灯片展示了该乘积及其完全展开式；讲师朗读各项系数，并指出该方法的一般幂次形式。

已覆盖 · 新幻灯片引入32分四币问题，并列出了四个生成函数；本片段在此问题求解前结束。

已覆盖 · 幻灯片提出了32分换零钱问题，主讲人解释了每种硬币对应的有限多项式因子。

已覆盖 · Sage 代码将四个多项式相乘，并提取 $x^{32}$ 的系数，得到结果17。

已覆盖 · 幻灯片之间的简短过渡，除从有限例子转向一般设定外，未引入任何新的数学陈述。

已覆盖 · 新幻灯片定义了 $c_n$ 和 $C(x)$ ，列出了无限硬币级数，并指出 $C(x)=P(x)N(x)D(x)Q(x)$ 。

已覆盖 · 主讲部分：定义硬币找零序列，展示四种单枚硬币的生成函数，并指出它们的乘积即为 $C(x)$ 。

已覆盖 · 练习部分：引入 Splinktonk 上的有限硬币问题，并指出 1 美分是无法凑出的；未给出具体求解过程。

探索视频中的知识

打开视频知识图谱 →

生成函数讲解定位 0:11
查看关联依据
已审核中文素材 v1：card「生成函数作为一根晾衣绳」出现在 0:11——讲座以赫伯特·威尔夫的比喻引入生成函数：生成函数是一根晾衣绳，一列数字被悬挂其上以便展示。这表明此处的主要目的，是代数地编码一个序列，而非立即求某个数值函数的值。

生成函数

把讲解展开来看。

章节

学习解说文稿

知识卡片

生成函数作为一根晾衣绳

斐波那契数列示例

x是一个形式变量

一般定义

全一数列

变量名称的选择

自然数序列

生成函数的定义

最终为零的序列对应多项式

帕斯卡三角形的一行作为生成函数

为何要对生成函数进行因式分解

硬币找零问题：凑出6美分

仅用便士的找零序列

仅用镍币的找零序列

计数序列的生成函数

含7枚便士的便士生成函数

含2枚镍币的镍币生成函数

为何生成函数相乘是可行的

例题：凑出6美分

含7枚便士与2枚镍币的展开乘积

从系数读取答案

生成函数的主要优势

32美分四枚硬币问题的设定

用于凑出 32 美分找零的有限多项式编码

详细学习笔记

x

A(x)A(x)A(x)

a0a_0a0​, a1a_1a1​, a2a_2a2​, …\ldots…

ana_nan​

n

y

a0a_0a0​,a1a_1a1​,a2a_2a2​,…\ldots…

A(x)A(x)A(x)

x

1,1,1,1,1,1,1,0,0,0,…\ldots…

1,0,0,0,0,1,0,0,0,0,1,0,0,…\ldots…

x

生成函数作为一列数字的晾衣绳

斐波那契数列编码为生成函数

将 x 视为一个形式变量，而非收敛意义上的输入值

生成函数的正式定义

常数数列1、1、1、……的生成函数

计数数列1、2、3、4、……的生成函数

生成函数的定义

最终为零的序列给出多项式型生成函数

帕斯卡三角形某一行的生成函数

硬币找零计数问题的设定

仅使用便士的换零钱序列

仅使用五美分硬币的找零序列

此处生成函数无需被视为收敛函数

形式变量的名称是任意的

因式分解生成函数有助于理解系数

x6x^6x6的系数等于2

该乘积即为硬币找零问题的完整生成函数。

共有 17 种方式凑出 32 美分

整体生成函数是四种硬币生成函数的乘积。

C(x)C(x)C(x) 的系数解释

一个乘积同时处理所有金额

从斐波那契数列构造其生成函数

从一个数列过渡到一般的生成函数记号

从帕斯卡三角形的行到（1+x1+x1+x）^n

推导仅使用便士的找零数列

推导仅使用镍币的找零序列

从项的乘积中推导出凑出6美分的两种方式

展开组合生成函数

从有限多项式推导出凑出 32 美分的方法数。

从单一目标金额到完整的生成函数

从单种硬币的因子出发推导完整生成函数

斐波那契生成函数示例

全为一的数列示例

计数数列示例

序列1,2,1,0,0,…的多项式生成函数。

帕斯卡三角形第 n 行的生成函数

直接枚举凑出 6 美分的所有方式。

仅用便士凑出所有美分金额的方式数序列

$A(x)$

$a_0$ , $a_1$ , $a_2$ , $\ldots$

$a_n$

$a_0$ , $a_1$ , $a_2$ , $\ldots$

$A(x)$

1,1,1,1,1,1,1,0,0,0, $\ldots$

1,0,0,0,0,1,0,0,0,0,1,0,0, $\ldots$

$x^6$ 的系数等于2

$C(x)$ 的系数解释

从帕斯卡三角形的行到（ $1+x$ ）^n

硬币供应无限与之对比硬币供应有限

序列 1,1,1, $\ldots$ 和 1,2,3,4, $\ldots$ 的生成函数分别是什么？