Tag: 组合数学

2023
数概率

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

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

数组合数学

卢卡斯定理

摘要: 求组合数的代码模板和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 卢卡斯定理设 p 是一个素数，将 m 和 n 写成 p 进制数： n = a_{0} + a_{1}p + a_{2

数组合数学

多重组合数的应用-集合的划分数

摘要: 多重组合的若干应用场景 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 多重集的排列与多重组合在 组合数学1-排列组合 中，我们提到过多重组合数，这里做个复习。 多重集的排列

数组合数学

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

摘要: 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
数组合数学

组合数学拾遗2-偏序集,Dilworth定理

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

数组合数学

组合数学拾遗1-集合,关系,函数

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

算法leetcode

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

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

算法搜索

滑动谜题和八数码

数字华容道可行性: 108. 奇数码问题 数字华容道1: 773. 滑动谜题 数字华容道2: 179. 八数码 置换群理论判定数字华容道可行性 组合数学5-群论 DFS BFS Astar IDAstar 用康拓编码给排列的哈希做空间压缩 排列算法 $0 置换群理论判定可行性原理算法基于置换群的理论，Ref : 组合数学5-群论 涉及到奇置换，偶置换，循环，对换的概念 奇置换：一

数组合数学

多重集的组合数

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

数组合数学

容斥计数

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

算法字符串

字典序

386. 字典序排数 440. 字典序的第K小数字 1643. 第 K 条最小指令 1415. 长度为 n 的开心字符串中字典序第 k 小的字符串 $1 386. 字典序排数算法1: 字典树前序遍历字符集是 0123456789，将所有数字插入到字典树 按字典序输出所有数字，即对字典树前序遍历，将所有插入的数字输出，实现时与 N 叉树的前序遍历没有区别 123456789101112131

算法动态规划

排列计数

526. 优美的排列: 状态压缩DP求满足条件的排列方案数 搭积木问题: DFS + 剪枝，枚举所有满足条件的排列，一个一个计数 装饰围栏: 线性DP求满足条件的排列方案数 + 康拓编码求若干排列的字典序第K大 $1 526. 优美的排列算法：状态压缩DP1234dp[state] := 当前使用数字为 state(状态压缩) 情况下的排列dp[0] = 1状态转移: 枚

算法基础算法

排列算法

枚举排列: 无重复: 46. 全排列 有重复: 47. 全排列 II DFS: 可以处理重复, 枚举 字典序法: 可以处理重复 SJT算法: 不能处理重复 下一个排列 31. 下一个排列 字典序法 第 K 个排列 60. 第k个排列 DFS + 剪枝 阶乘数系统 康托展开与康托编码 排列的哈希 $1 枚举排列 46. 全排列 47. 全排列 II 以上两题为输出所有的排列，一个

数组合数学

组合数学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-排列组合 中我们详细梳理了组合数学的基本模型，以及排列组合的相关公式。本文我们研究编程求组合数的几

算法leetcode

【DP难题】力扣920-播放列表数量

无串线性 dp 容斥原理 交集 = 并集 - 差集 组合数学解法：官方题解，并没有看懂 求有限制的排列个数问题 生成函数和中国剩余定理的应用 $1 题目题目链接920. 播放列表的数量 题目描述你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复）。请你为她按如下规则创建一个播放列表： 每首歌至少播放一次。一首歌只有在其他 K 首歌播放完

数组合数学

组合数学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 组合数学的核心内容是深入离散对象的计数方法，而计算机的核心内容是使用算法处理离散数据，因此随着计算机