软件项目管理 组合数学 学习笔记

授课老师是冯子玹,极其抽象.

这个老师采用逆天的上座签到机制,老师会在下课的时候亲自到座位上挨个让同学报学号,也就是彻底断绝了代课之外的一切签到手段了.
这个老师还极度厌恶AI,会出持续时间非常短的测试题,美其名曰”让同学们来不及用AI,自己思考”,AI都顾不上答的题目人怎么可能答的上来,所以这个老师极度抽象,不是避雷课程,而是避雷这个老师.

上个学期Fluu的组合数学就是这个老师带的,签到也是这个签到形式,极其逆天.

不过这个课采用经典的大作业制,平常的题目都答了应该是挂不了的…

应该吗?应该吧…

软件项目管理

最后的时候做一个word形式的报告就行.
鉴于AI比重过大,所以在这里不展示了.

组合数学

平时的课都可以不用去,最后的时候找个时间做个PPT给老师答辩就行了.
Fluu这一年的主题是”只要和组合数学有关就行”.

下面是Fluu的PPT.
本着开源精神,Fluu会开放源代码,不过Fluu不管怎么编译…

不知道为什么,Fluu本地的tex需要刷两遍才能把项目编译对,感觉是tex编译第一遍刷新中间产物,第二遍才会使用正确的中间产物去覆写正确的pdf.

拿着这个很偏算法的PPT去找老师答辩的时候,这个老师是一脸懵逼的,什么是贝尔数?什么是OEIS?
怎么就成功优化这个算法了???
这只能说这个老师因循守旧墨守成规胸无大局满足现状…

当然Fluu看了一下其他人的PPT,那只能说更水,因为他们列举什么组合数学的应用,还用一眼AI的文案,跟过家家一样.

\documentclass{beamer}
\usepackage{ctex, hyperref}
\usepackage[T1]{fontenc}
\usepackage[most]{tcolorbox} % 支持圆角、阴影等
\usepackage{ctex}

% other packages
\usepackage{latexsym,amsmath,xcolor,multicol,booktabs,calligra}
\usepackage{graphicx,pstricks,listings,stackengine}
\usepackage{etoolbox} % 可选，用于条件判断（如果不需要也可以用 \newif 方案）


\author{NaraFluorine}
\title{贝尔数 Bell Numbers}
\subtitle{\url{https://oeis.org/A000110}}
\institute{吉林大学软件学院}
\date{2025年6月19日}
\usepackage{JilinUniv}


% defs
\def\cmd#1{\texttt{\color{red}\footnotesize $\backslash$#1}}
\def\env#1{\texttt{\color{blue}\footnotesize #1}}
\definecolor{deepblue}{rgb}{0,0,0.5}
\definecolor{deepred}{rgb}{0.6,0,0}
\definecolor{deepgreen}{rgb}{0,0.5,0}
\definecolor{halfgray}{gray}{0.55}
\definecolor{bblue}{RGB}{51,102,153}
\definecolor{strongred}{RGB}{200,0,0}
\definecolor{lightred}{RGB}{255,240,240}

\lstset{
	basicstyle=\ttfamily\small,
	keywordstyle=\bfseries\color{deepblue},
	emphstyle=\ttfamily\color{deepred},	% Custom highlighting style
	stringstyle=\color{deepgreen},
	numbers=left,
	numberstyle=\small\color{halfgray},
	rulesepcolor=\color{red!20!green!20!blue!20},
	frame=shadowbox,
}

\tcbset{
  myblock/.style={
	enhanced,
	colback=deepblue!5,		% 内容区背景：淡一点的 deepblue
	colframe=bblue,		 % 边框颜色
	coltitle=white,			% 标题文字颜色
	fonttitle=\bfseries,	   % 标题字体
	title=formula,
	attach boxed title to top left={yshift=-2mm,xshift=2mm},
	boxed title style={
	  colback=bblue,			  % 标题背景色
	  colframe=bblue,			 % ✅ 标题边框颜色
	  rounded corners
	},
	sharp corners=south,
	boxrule=0.5pt,
	drop shadow
  }
}

\tcbset{
  prove/.style={
	enhanced,
	colback=lightred,		   % 内容区背景：浅红
	colframe=strongred,		 % 主框边框颜色
	coltitle=white,			 % 标题文字颜色
	fonttitle=\bfseries,		% 标题字体
	title=proof,				 % 框的标题
	boxed title style={
	  colback=strongred,		% 标题栏背景色
	  colframe=strongred,	   % 标题栏边框色
	  boxrule=0pt,			  % 去除标题边框线条
	  top=1mm, bottom=1mm, left=2mm, right=2mm,
	  rounded corners
	},
	sharp corners=south,
	boxrule=0pt,				% 内容框边框不画线（或可留0.5pt）
	drop shadow,				% 添加阴影
	left=2mm, right=2mm, top=1mm, bottom=1mm
  }
}


% 定义一个标记，控制是否生成章节目录页幻灯片
\newif\ifskipTOC
\skipTOCfalse

% 修改 AtBeginSection 钩子，只有当 skipTOC 为 false 时生成目录页幻灯片
\AtBeginSection[]{
  \ifskipTOC
	% 如果跳过，则什么都不做
  \else
	\begin{frame}{Outline}
	  \tableofcontents[currentsection]
	\end{frame}
  \fi
}

\begin{document}

\kaishu
\begin{frame}
	\setbeamertemplate{headline}{} % 移除本页页眉（其余页面保留）
	\vfill
	\centering
	\titlepage
	\vfill
\end{frame}

% 针对章节 D，先将跳过标记设为真，这样 AtBeginSection 就不会生成目录页幻灯片，
% 但仍然会把章节“D”计入页眉导航。
\skipTOCtrue
\section{$\mathrm{Introduction}$}
\skipTOCfalse % 头顶上的小圆圈


\begin{frame}{集合划分}
	\begin{itemize} 
		\item 将集合$\mathrm{S}$划分为若干个两两不相交的非空子集的族,且他们的并是$\mathrm{S}$,求有多少种方法?
		\pause
		\item 假设集合为${1,2,3}$,则有$5$种划分方法如下:
		\item $\{\{1\},\{2\},\{3\}\}$
		\item $\{\{1\},\{2,3\}\}$
		\item $\{\{2\},\{1,3\}\}$
		\item $\{\{3\},\{1,2\}\}$
		\item $\{\{1,2,3\}\}$
		\pause
		\item 于是我们得到数列
		\item $1,2,5,15,52,203,877,4140,21147,115975,...$
	\end{itemize}
\end{frame}


\skipTOCtrue
\section{$\mathrm{Recursion}$}
\skipTOCfalse




\begin{frame}{递推公式}
\tcbset{width=\textwidth}
\begin{tcolorbox}[myblock]
	\begin{itemize}
		\item 贝尔数可以如此递推:
	\end{itemize}
	$$\mathrm{B}_{\mathit{n}+1}=\sum_{\mathit{k}=0}^{\mathit{n}}\binom{\mathit{n}}{\mathit{k}}\mathrm{B}_{\mathit{k}}$$
\end{tcolorbox}
\end{frame}

\begin{frame}{递推公式}
	\begin{tcolorbox}[prove]
		$\mathrm{B}_{\mathit{n}+1}$是含有$\mathit{n}+1$个元素集合的划分个数,设$\mathrm{B}_\mathit{n}$的集合为$\{\mathit{b}_1,\mathit{b}_2,\mathit{b}_3,\dots,\mathit{b}_\mathit{n}\}$,$\mathrm{B}_{\mathit{n}+1}$的集合为$\{\mathit{b}_1,\mathit{b}_2,\mathit{b}_3,\dots,\mathit{b}_\mathit{n},\mathit{b}_{\mathit{n}+1}\}$,那么可以认为$\mathrm{B}_{\mathit{n}+1}$是有$\mathrm{B}_{\mathit{n}}$增添了一个$\mathit{b}_{\mathit{n}+1}$而产生的,考虑元素$\mathit{b}_{\mathit{n}+1}$.
		\begin{itemize}
			\item 假如它被单独分到一类,那么还剩下$\mathit{n}$个元素,这种情况下划分数为$\binom{\mathit{n}}{\mathit{n}}\mathrm{B}_{\mathit{n}}$;
			\item 假如它和某$1$个元素分到一类,那么还剩下$\mathit{n}-1$个元素,这种情况下划分数为$\binom{\mathit{n}}{\mathit{n}-1}\mathrm{B}_{\mathit{n}-1}$;
			\item 假如它和某$2$个元素分到一类,那么还剩下$\mathit{n}-2$个元素,这种情况下划分数为$\binom{\mathit{n}}{\mathit{n}-2}\mathrm{B}_{\mathit{n}-2}$;
			\item ......
		\end{itemize}
		以此类推即可.
	\end{tcolorbox}
\end{frame}




\skipTOCtrue
\section{$\mathrm{Nature}$}
\skipTOCfalse

\begin{frame}{性质}
\tcbset{width=\textwidth}
	\begin{tcolorbox}[myblock]
		\begin{itemize}[<+-| alert@+>]
			\item 每个贝尔数都是相应的第二类斯特林数的和.
			\item 因为第二类斯特林数是把基数为$\mathit{n}$的集合划分为正好$\mathit{k}$个非空集的方法数目.
			\item $$\mathrm{B}_{\mathit{n}}=\sum_{\mathit{k}=0}^\mathit{n}{\mathit{n}\brace \mathit{k}}$$
		\end{itemize}
	\end{tcolorbox}
\end{frame}


\skipTOCtrue
\section{$\mathrm{Calculate}$}
\skipTOCfalse


\begin{frame}{计算}
	之前我们提到了递推公式,时间复杂度是$\mathit{O}(\mathit{n}^2)$的,还可以优化.
	\begin{itemize}
		\item 我们把上文递推公式的组合数展开:
		\item $$\mathrm{B}_{\mathit{n}+1}=\sum_{\mathit{k}=0}^{\mathit{n}}\binom{\mathit{n}}{\mathit{k}}\mathrm{B}_{\mathit{k}}=\sum_{\mathit{k}=0}^\mathit{n}\frac{\mathit{n}!}{\mathit{k}!(\mathit{n}-\mathit{k})!}\times\mathrm{B}_{\mathit{k}}$$
		\pause
		\item 分离$\mathit{k}$和$\mathit{n}$得到:
		\item $$\frac{\mathrm{B}_{\mathit{n}+1}}{\mathit{n}!}=\sum_{\mathit{k}=0}^\mathit{n}\frac{1}{(\mathit{n}-\mathit{k})!}\times\frac{\mathrm{B}_\mathit{k}}{\mathit{k}!}$$
		\pause
		\item 令$\mathit{f}_\mathit{x}=\frac{1}{\mathit{x}!}$,$\mathit{g}_\mathit{x}=\frac{\mathrm{B}_\mathit{x}}{\mathit{x}!}$,有:
		\item $$\frac{\mathrm{B}_{\mathit{n}+1}}{\mathit{n}!}=\sum_{\mathit{k}=0}^{\mathit{n}}\mathit{f}_{\mathit{n}-\mathit{k}}\mathit{g}_{\mathit{k}}$$
	\end{itemize}
\end{frame}


\begin{frame}{计算}
	得到的式子
	\begin{itemize}
		\item $$\frac{\mathrm{B}_{\mathit{n}+1}}{\mathit{n}!}=\sum_{\mathit{k}=0}^{\mathit{n}}\mathit{f}_{\mathit{n}-\mathit{k}}\mathit{g}_{\mathit{k}}$$
		\item 使用多项式求逆即可,时间复杂度$\mathit{O}(\mathit{n}\log \mathit{n})$.
		\item 也可以使用分治FFT处理,时间复杂度是$\mathit{O}(\mathit{n}\log^2\mathit{n})$,在此不表.
	\end{itemize}
\end{frame}


\begin{frame}{多项式求逆}
	\begin{itemize}
		\item 不妨设$\mathit{F}(\mathit{x})=\sum_{\mathit{i}=0}^\infty \mathit{f_i x^i},\mathit{G}(\mathit{x})=\sum_\mathit{i=0}^\infty \mathit{g_i x^i}$ ,且$\mathit{g}_0=0$
		\pause
		\item 那么有$$\mathit{F}(\mathit{x})\mathit{G}(\mathit{x})=\sum_{\mathit{i}=0}^\infty \mathit{x^i}\sum_{\mathit{j}+\mathit{k}=\mathit{i}}\mathit{f_jg_k}=\mathit{F}(\mathit{x})-\mathit{f}_0\mathit{x}^0$$
		\pause
		\item 所以有$$\mathit{F}(\mathit{x})\mathit{G}(\mathit{x})\equiv(\mathit{F}(\mathit{x})-\mathit{f}_0)\mod \mathit{x^n}$$
		\pause
		\item 所以有$$\mathit{F}(\mathit{x})\equiv\left( \frac{\mathit{f}_0}{1-\mathit{G}(\mathit{x})}\right)\mod \mathit{x^n}$$
		\item 使用多项式求逆可以解决,时间复杂度是$\mathit{O}(\mathit{n}\log \mathit{n})$.
	\end{itemize}
\end{frame}

\skipTOCtrue
\section{$\mathrm{Example}$}
\skipTOCfalse


\begin{frame}{例题}
	留给感兴趣的同学们探索.
	\begin{itemize}
		\item 板子题1
		\item \url{https://uicoj.net/problem/1026}
		\item 板子题2
		\item \url{https://www.luogu.com.cn/problem/P5748}
		\item 应用1
		\item \url{https://codeforces.com/problemset/problem/568/B}
	\end{itemize}
\end{frame}


\skipTOCtrue
\section{$\mathrm{End}$}
\skipTOCfalse


\begin{frame}{结尾}
	\begin{center}
	  {\Huge\calligra Thanks!}
	\end{center}
\end{frame}

\end{document}


% refs:
% https://uicoj.net/problem/1026
% https://www.luogu.com.cn/article/hsw7fzdn
% https://www.cnblogs.com/lfri/p/11549652.html
% https://mathworld.net.cn/BellNumber.html
% https://codeforces.com/problemset/problem/568/B