容斥原理公式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

相关文章

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

鸿蒙中@State的原理使用详解(HarmonyOS 5)

《鸿蒙中@State的原理使用详解(HarmonyOS5)》@State是HarmonyOSArkTS框架中用于管理组件状态的核心装饰器,其核心作用是实现数据驱动UI的响应式编程模式,本文给大家介绍... 目录一、@State在鸿蒙中是做什么的?二、@Spythontate的基本原理1. 依赖关系的收集2.

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、