Tag: 组合数学

2024
算法算法分析

n节点的无序标号树有多少种：拉格朗日反演的应用

摘要: 拉格朗日反演的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们继续来讨论算法分析的问题。 对于图论中的很多算法，其时间复杂度的分析经常需要基于 n 节点的无序标号树共有多

算法算法分析

二叉树的计数：直接方法与间接方法

摘要: 通过二叉树计数的基础问题，了解生成函数计数的直接方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在对与二叉树相关的算法进行算法分析时，一个非常基本的问题是：给定一些条件，问满足这些条件的

算法算法分析

生成函数的性质速查

摘要: 生成函数的性质 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 生成函数即母函数，有时也叫形式幂级数。是组合数学中的一个重要理论和工具。 生成函数的一个重要线索来自于 18

2023
算法数学算法

先找规律后推公式，自然数幂和公式

摘要: 找规律，推公式 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们看一个值域二分的问题。假设有一个 $f(x)$，我们想知道使得 $f(x) \geq M$ 成

算法动态规划

不同路径系列问题：计数DP，以初等计数原理划分阶段和子问题

摘要: 状态的各决策间满足加法原理，决策划分的子状态间满足乘法原理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 动态规划中的计数类问题，主要强调“不重不漏”。因此如果用动态规划解决的话，子结构的划

数组合数学

鸽巢原理及其加强形式

摘要: 鸽巢原理 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 鸽巢原理是组合数学中最古老的原理之一，也称为抽屉原理或Dirichlet原理。Dirichlet 在 1834 年提

数组合数学

字典序法枚举组合

摘要: 按照字典序来枚举组合 $\binom{n}{r}$ 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 字典序法枚举排列 中，我们用字典序方法完成了排列的枚举。在 C++ 中，std::n

数数论

阶乘数系统与康托编码

摘要: 阶乘数系统、康托编码，全排列和字典序互相转换 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 回溯法的思想、设计与分析 中，我们系统学习了回溯法。回溯法将解空间看做树形结构，称为状态空

数组合数学

字典序法枚举排列

摘要: 按照字典序来枚举全排列 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 回溯法的思想、设计与分析 中，我们系统学习了回溯法。回溯法将解空间看做树形结构，称为状态空间树，在文章 回溯法三

数组合数学

SJT算法：沿哈密顿路径枚举全排列

摘要: 枚举全排列与哈密顿路径 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 回溯法的思想、设计与分析 中，我们系统学习了回溯法。回溯法将解空间看做树形结构，称为状态空间树，在文章 回溯法三

算法搜索

回溯法的思想、设计与分析

摘要: 回溯法基本思想 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 回溯法思想回溯法是一种在解空间中搜索可行解或最优解的方法。该方法通常将解空间看做树形结构，称为状态空间树。 搜索过程以 DFS

数概率

从抛硬币实验得出沃利斯公式

摘要: 从伯努利试验序列中找到沃利斯公式 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 沃利斯公式是我们大学数学分析中的一个著名公式，由沃利斯 1655 年发表在《无穷算术》上，发

数组合数学

卢卡斯定理

摘要: 求组合数的代码模板和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 卢卡斯定理是由法国数学家爱德华·卢卡斯在1878年提出的，涉及到组合数和模运算，广泛应用于组合数学和数论中。 卢卡斯

数组合数学

多重组合数的应用-集合的划分数、对称群的共轭类计数

摘要: 多重组合的若干应用场景 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在 n 元对称群中，每个置换根据其轮换分解中各个长度的轮换的个数，可以将置换分为各个型号。一个自然的问

数组合数学

放球模型总结-集合间映射计数

摘要: 12 种放球模型，以及对应的集合间映射的角度的理解 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在 组合数学1-排列组合 中，我们大致串一下基础排列组合的公式，其中放球模型是一种重要的理解

数组合数学

形式幂级数的运算、性质、应用

摘要: 全面梳理形式幂级数的理论和应用 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 数学分析-级数论 中，我们系统学习过函数项级数，首先是收敛性、收敛半径以及各种判别法，

数组合数学

组合恒等式-基于六个基本组合恒等式

摘要: 六个基本组合恒等式 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 组合的定义： \binom{n}{k} = \frac{n!}{k!(n-k)!}二项式定理： (1 + x)^{n}

数组合数学

微积分方法证明组合恒等式

摘要: 组合恒等式：微积分方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在组合数学、概率、分析中，经常会在推导中使用组合恒等式，很多组合恒等式事先不知道的话，是不容易看出来的。在文章 组合恒等

数分析

数学赏析：牛顿推导广义二项式定理的过程；欧拉和柯西的证明思路

摘要: 沿着历史的脉络推导二项式定理 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在现代数学分析的教材中，都会介绍广义二项式定理，也就是 $(1 + x)^{\alpha}$

算法leetcode

力扣372-超级次方

摘要: 力扣 372：快速幂、扩展欧拉定理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 题目 372. 超级次方 你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正

2022
任意门连载合集

【合集】马昱春组合数学

摘要: 这是马昱春组合数学公开课的笔记合集。2020 年写的。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 其它已完结的合集参见 合集栏 组合数学1-排列组合 组合数学2-母函数,递推关系 组合

数组合数学

【leetbook】组合数学-目录

摘要: 组合数学的 Leetbook 目录，附链接 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 排列组合 母函数基础 递推关系基础 k阶线性常系数齐次递推关系 指数型母函数 特殊计数序

数组合数学

组合数学6-polya计数

摘要: Polya 定理、立方体旋转、欧拉定理、母函数型 Polya、图的计数 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式

数分析

数学分析-级数论

摘要: 2015 年写的史济怀数学分析课程笔记，第二部分：级数论 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 2015 年，史济怀数学分析课程笔记，共 3 部分 数学分析-一元微积分 数学分析-

算法算法分析

具体数学

摘要: 《具体数学》，算法分析的数学基础 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 书名《具体数学》 豆瓣链接: 具体数学 : 计算机科学基础 时间: 2013 具体数学 递归问题

算法疑难杂症

【组合数学】马拦过河卒

摘要: 很经典并且非常综合的组合数学问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文的第一题，标准的马拦过河卒问题是入门的棋盘 DP 的题目。 如果没有马拦着过河卒，那么 leetcode

2021
数组合数学

编程中的组合数学

摘要: 本文介绍一本编程中的组合数学的书 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 程序设计中的组合数学

算法动态规划

矩阵快速幂及其动态规划优化中的应用

摘要: 本文介绍矩阵快速幂的算法原理与代码模板，并解决一个例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 多米诺与托米诺骨牌平铺 中，我们用矩阵快速幂优化 DP 的方式解决了一个计数问题

算法数学算法

leetcode数学题目汇总

摘要: 本文系统梳理了数学相关的算法。并汇总了 leetcode 上的相关的题目。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文总结了力扣上 2000 题以内的关于数学的 49 道题。将场景相

算法leetcode

【DP难题】力扣1411-给Nx3网格图涂色的方案数

摘要: 使用动态规划解决计数问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，最大子数组和这个系列此前连续写了八篇，有些审美疲劳了。今天我们换换脑子，看个使用动态规划解决计数问题的一个例子

2020
数组合数学

偏序集与Dilworth定理

摘要: 偏序集、Dilworth定理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 此前我们系统第学习了组合数学，详细内容见下面这些文章： 组合数学1-排列组合 组合数学2-母函数,递推关系 组合

数集合论

集合,关系,函数的概念

摘要: 集合、关系、函数 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 此前我们系统第学习了组合数学，详细内容见下面这些文章： 组合数学1-排列组合 组合数学2-母函数,递推关系 组合数学3-特殊

算法leetcode

【DP难题】力扣1617-统计子树中城市之间最大距离

摘要: 力扣 1617，比较难的树形 DP 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 今天我们来看一个比较难的图论题，力扣 1617，也就是第 210 周赛 D 题。抽象之后是求树的直径

数组合数学

多重集的组合数

摘要: 多重集合的组合，推导与计算方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型，以及排列组合的相关公式。进一步在文章 组合数

数组合数学

容斥计数

摘要: 容斥计数的例题，可以作为代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于一些计数或者概率类型的动态规划问题，有时候答案是要求恰好满足某条件时的答案，但是难以限制成恰好的情况，可以

算法字符串

用字典树处理字典序的问题

摘要: 几个字符串上的字典序问题，用字典树可以解决 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 字典序法枚举排列 中，我们了解到对于一个排列来说，可以用字典序来定义这些排列的大小，进一步可

数组合数学

组合数学5-群论

摘要: 群、置换群、共轭类、对换、等价类、Burnside引理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式；在 组合数学2

算法动态规划

计数DP

摘要: 本文简要介绍一下计数类的问题，以及 leetcode 上的相关题目。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 计数是组合数学的重要内容。不考虑用母函数等手段求解析解的话，计数问题一般有

算法搜索

常见的枚举方式

摘要: 本文梳理一下常见的枚举方式，以及对应的代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 枚举与分类讨论、找规律、按位单独处理、分别计算各元素贡献、逆向思维、惰性更新 等一样，也是一种思

算法图算法

拓扑排序的方案数

摘要: 一个综合算法问题：树形DP + BST 建树 + 预处理组合数 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们通过力扣的一个题目，来看一下拓扑排序方案数问题怎么解决。这是第 204

数组合数学

组合数

摘要: 求组合数的代码模板和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型，以及排列组合的相关公式。本文我们研究编程求组合数的几

数组合数学

组合数学4-容斥原理,鸽巢原理

摘要: 组合数学：容斥原理、鸽巢原理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式；在 组合数学2-母函数,递推关系 中我们

数组合数学

组合数学3-特殊计数序列,指数型母函数

摘要: 组合数学：特殊计数序列、指数型母函数 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式；在 组合数学2-母函数,递推关系

数组合数学

组合数学2-母函数,递推关系

摘要: 组合数学：母函数与递推关系 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式，本文我们看一下组合数学的第二部分，母函数和

数组合数学

组合数学1-排列组合

摘要: 组合数学的基本模型，以及排列组合的相关公式 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 组合数学的核心内容是深入离散对象的计数方法，而计算机的核心内容是使用算法处理离散数据，因此随着计算机