容斥原理公式c语言,【笔记】组合数学 - osc_3md1xrlp的个人空间 - OSCHINA - 中文开源技术交流社区...

本文主要是介绍容斥原理公式c语言,【笔记】组合数学 - osc_3md1xrlp的个人空间 - OSCHINA - 中文开源技术交流社区...,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

开新坑辣。。。。。

排列组合

排列:P(n,r) = n! / (n-r)! 组合:C(n,r) = n! / r!(n-r)! 圆排列:P(n,r) / r 多重集排列:

令S是一个多重集,它有k个不同类型的元素,每一个元素都有无穷重复个数。那么S的r-排列的个数为k^r。

令S是一个多重集,它有k个不同类型的元素,各元素重数为n1,n2,...,nk。设S的大小为n = n1 + n2 + ... + nk。则排列数等于n! / (n1!n2!...nk!)

抽屉原理(鸽巢原理)

wiki百科介绍 理解起来还是比较容易的,拓展有拉姆齐定理(虽然是图论上的内容)

特殊序列

掌握它们的应用和推导方式

Catalan序列

wiki百科介绍

f420ef8257447467cc9f8bd6cea23b91.png

214fbe1794f42d6d806ab1d3a3d7ccaf.png

23a78a28770f949c7a303cb2a4e68e4a.png

c44b5d47e55125ac168f965b4cf92e43.png 前20项为(OEIS中的数列A000108):1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190

Stiring数

wiki百科介绍 第一类:将p个有区别的球排成k个非空的圆排列的方案数

4e22bb3ae5c94e337878adf22209fa0c.png

5260ad786591afaf0f8bfcffcabd28d6.png

4be7dead2dd2791810b3b13192d875c0.png 第二类:将p个有区别的球放到k个相同盒子中,奥球没有空盒的方案数

af0914c09d92f4c3b33369689ae048cc.png

4b911982b08b39d0942faf45a53ab062.png 两者关系:

0a7dbfe147b60a47e9ed652ea0888e08.png

容斥原理

60835765823fe76e74b7048872a5e617.png

错位排列

公式法:

c2fdb7dc5b30aefd13b9d0a618e9db25.png 递推法: 考察n≥3时的错位排列,把数字n单独拿出来看,先把n放在第n位。设P是{1,2,...,n-1}的一个排列

如果P是一个错位排列,把其中任意一个数与n交换仍然是一个错位排列,这样的情形可以得到(n-1)D_n-1个{1,2,...,n}的错位排列

如果P不是错位排列,并且只存在一个位置不符合要求(P_x = x)将x和n交换后又是一个错位排列。这里可以得到(n-1)D_n-2个{1,2,...,n}的错位排列。

其他情形都不能得到错位排列

D_n = (n-1)(D_n-1 + D_n-2) (D1 = 0, D2 = 1)

Mobius反演

NULL

棋盘多项式

母函数(生成函数)

普通型生成函数讲解 在学习FFT的时候,已经知道可以用卷积来计算生成函数计数问题,它可以针对一般的多项式计算乘积,而在整数拆分这个问题里,有n个表达式,需要做n次卷积,复杂度O(n²logn),但FFT常数是很大的,观察得知每个多项式是很有规律的,它的第i个多项式中系数为1的项都间隔了i-1个系数为0项,所以我们可以用一个每次变化i-1的k循环来遍历得到每层卷积后的多项式 指数型生成函数讲解

Polya计数定理

置换群

首先给你一个序列,假如: s = {1 2 3 4 5 6} 然后给你一个变换规则 t = {6 3 4 2 1 5} 就是每一次按照t规则变换下去 第一次:6 3 4 2 1 5 第二次:5 4 2 3 6 1 第三次:1 2 3 4 5 6 发现经过几次会变换回去,再变换下去就是循环的了,这就是一个置换群 我们可以这样表示一个置换群,比如按照上面变化规则 1->6->5->1 这些是一个轮换 2->3->4->2 这些是一个轮换 所以可以写为 t = { {1 6 5},{ 2 3 4 } }

如果一个状态经过置换f后跟原来相同, 即S[1]=S[a1],S[2]=S[a2],…,S[n]=S[an] 则称该状态为f 的不动点。

题目中常常出现“本质不同的方案数”,一般是指等价类的数目,题目定义一个等价关系,满足等价关系的元素属于同一等价类。等价关系通常是一个置换集合F,如果一个置换能把其中一个方案映射到另一个方案,则二者是等价的。 那么,置换构成的群就是置换群,就是交换排列顺序而已

二面体群

wiki百科介绍 翻转本质上也是一种置换规则

557d1d72a7cbba8d3c9a5887fcb5f153.png

Burnside引理

设G是集合X上的一个置换群(可以理解为合理的所有的置换方案的集合),S(g)为C中的不动点的着色集合,则可以证明等价类数目为所有S(g)的平均值。

一正方形分成4格,2着色,有多少种方案?其中,经过转动相同的图象算同一方案 对于每种格子我们都有两种选择,所以会有一下16种方案

adf96bf893b4b23092a326431bb94709.png

不动:所有的情况都是不动点 16

旋转90° (1)(2)是不动点 2

旋转180° (1)(2)(11)(12)是不动点 4

旋转270° (1)(2)是不动点 2 (16+2+4+2)/4=6种

Polya计数定理

先把所有方案重复计算相同的次数,再把结果除以重复的次数 设G是集合x上的一个置换群,X中每个元素可以被染成k种颜色,则不等价的着色数为:P=(1 / |G|) *∑K^(nc(g)),nc(g) 为置换中循环节的个数

这篇关于容斥原理公式c语言,【笔记】组合数学 - osc_3md1xrlp的个人空间 - OSCHINA - 中文开源技术交流社区...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/256901

相关文章

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

利用Python实现添加或读取Excel公式

《利用Python实现添加或读取Excel公式》Excel公式是数据处理的核心工具,从简单的加减运算到复杂的逻辑判断,掌握基础语法是高效工作的起点,下面我们就来看看如何使用Python进行Excel公... 目录python Excel 库安装Python 在 Excel 中添加公式/函数Python 读取

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超