几种数学公式(环排列 母函数 唯一分解定理 卡特兰数 默慈金数 贝尔数 那罗延数)

本文主要是介绍几种数学公式(环排列 母函数 唯一分解定理 卡特兰数 默慈金数 贝尔数 那罗延数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一:环排列

把一个m个元素的环在m个不同的位置拆开记得到m个不同的线排列。由于n个不同元素中任取m个元素的排列方法为P(n,m)种,所以n个不同元素中任取m个元素的环排列方法有P(n,m)/m种。(p是排列组合中的A)
特别的,n个不同元素的环排列方法有P(n,n)/n=(n-1)!种。

二:母函数(用来解决:有N种重量的物品,每种物品有M个(1-无穷),求可以组合出来的重量的个数和该重量的方案数。

题意:火星上的货币有1,4,9,16,25.....17^2这17中面值的硬币,问任意给定一个不大于300的正整数面额,用这些硬币来组成此面额总共有多少种组合种数。

2
10
30
0

Sample Output

1
4
27
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 300 + 10;
int a[MAXN];
int b[MAXN];
int main()
{int n;while(cin >> n && n){for(int i = 0; i <= 300; i++) // 初始化{a[i] = 1; // 模拟第一个括号,各项的系数为1b[i] = 0; // 中间数组}for(int i = 2; i <= 17; ++i) // 外层括号数{for(int j = 0; j <= n; ++j) // 因为没有限制硬币的数量,每步新形成的括号,{for(int k = 0; k + j <= n; k += i * i) 增量。{b[k + j] += a[j];}}for(int j = 0; j <= n; ++j) // 因为{ a[j] = b[j];b[j] = 0;}}cout << a[n] << endl;}return 0;
}

三:唯一分解定理

<1>容斥原理 

容斥原理中经常用到的有如下两个公式:

1.两集合的容斥关系公式:A∪B=A+B-A∩B。

2.三个集合的容斥关系公式:A∪B∪C=A+B+C-A∩B-A∩C-B∩C+A∩B∩C。

需要注意的是,以上两个公式分别主要针对两种情况:第一个公式是针对涉及到计算两类事物的个数,第二个公式是针对涉及到三类事物的个数。

<2>抽屉原理

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

四:卡特兰数

实际上就是出栈序列的种数

令h(0)=1,h(1)=1,catalan数满足递推式:

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

例如:h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

另类递推式:

h(n)=h(n-1)*(4*n-2)/(n+1);

递推关系的解为:

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

递推关系的另类解为:

h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

eg:

As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.

Input

The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.

Output

For each test case, you should output how many ways that all the trains can get out of the railway.

Sample Input

1
2
3
10

Sample Output

1
2
5
16796
Hint
The result will be very large, so you may not process it by 32-bit integers.
//h(n)=h(n-1)*(4*n-2)/(n+1)
#include<cstdio>
#include<algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
ll a[105][100];
void f()
{ll i,j,yu,len;a[2][0]=1;a[2][1]=2;a[1][0]=1;a[1][1]=1;len=1;for(i=3;i<101;i++){yu=0;for(j=1;j<=len;j++){ll t=(a[i-1][j])*(4*i-2)+yu;yu=t/10;a[i][j]=t%10;}while(yu){a[i][++len]=yu%10;yu/=10;}for(j=len;j>=1;j--){ll t=a[i][j]+yu*10;a[i][j]=t/(i+1);yu = t%(i+1);}while(!a[i][len])len--;a[i][0]=len;}}
int main()
{f();ll n,i;while(scanf("%d",&n)!=EOF){for(i=a[n][0];i>0;i--)printf("%lld",a[n][i]);puts("");}return 0;
}

再来一个例题

As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.

Input

The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.

Output

For each test case, you should output how many ways that all the trains can get out of the railway.

Sample Input

1
2
3
10

Sample Output

1
2
5
16796由于满足1 2 5 所以为卡特兰数  又因为数比较大  所以用java写    要学java  看这喽https://blog.csdn.net/zcy19990813/article/details/81173275            https://blog.csdn.net/zcy19990813/article/details/81173071
import java.math.BigInteger;
import java.util.Scanner;
import java.io.*;
public class Main{public static void main(String args[]) {Scanner cin=new Scanner(System.in);int n;while(cin.hasNext()) {n=cin.nextInt();BigInteger ans=BigInteger.valueOf(1);for(int i=1;i<=n;i++){ans=ans.multiply(BigInteger.valueOf(4*i-2));ans=ans.divide(BigInteger.valueOf(i+1));}System.out.println(ans);}}
}

五:默慈金数   默慈金数是在数学中,一个给定的数n的默慈金数是“在一个圆上的n个点间,画出彼此不相交的弦的全部方法的总数”。

六  贝尔数

Bell数,又称为贝尔数。
B(n)是包含n个元素的集合的划分方法的数目。
B(0) = 1, B(1) = 1, B(2) = 2, B(3) = 5, 
B(4) = 15, B(5) = 52, B(6) = 203,..
递推公式为,
B(0) = 1,
B(n+1) = Sum(0,n) C(n,k)B(k). n = 1,2,...
其中,Sum(0,n)表示对k从0到n求和,C(n,k) = n!/[k!(n-k)!]

七  那罗延数

N(n,k) = 1/n * C(n,k) * C(n,k-1)

八  斯特林公式

公式为:   n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}.

 从图中看出,对于足够大的整数n,这两个数互为近似值。更加精确地:   

      \lim_{n \rightarrow \infty} {\frac{e^n\, n!}{n^n \sqrt{n}}} = \sqrt{2 \pi}.       或者        \lim_{n \rightarrow \infty} {\frac{n!}{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}} = 1

eg:

输入N求N的阶乘的10进制表示的长度。例如6! = 720,长度为3。

Input

第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 1000)
第2 - T + 1行:每行1个数N。(1 <= N <= 10^9)

Output

共T行,输出对应的阶乘的长度。

Sample Input

3
4
5
6

Sample Output

2
3
3

判断n的长度,就是log10(n)+1,将n!代入化简就可以啦

#include<cstdio>
#include<iostream>
#include <cmath>
using namespace std;
const int MAXN = 300 + 10;
#define pi 3.1415926535898
#define e 2.718281828459
typedef long long ll;
int main()
{ll t,n,ans;scanf("%lld",&t);while(t--){scanf("%lld",&n);ans=1/2.0*log10(2*pi*n)+n*log10(n)-n*log10(e)+1;printf("%lld\n",ans);}return 0;
}

 

这篇关于几种数学公式(环排列 母函数 唯一分解定理 卡特兰数 默慈金数 贝尔数 那罗延数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Flutter打包APK的几种方式小结

《Flutter打包APK的几种方式小结》Flutter打包不同于RN,Flutter可以在AndroidStudio里编写Flutter代码并最终打包为APK,本篇主要阐述涉及到的几种打包方式,通... 目录前言1. android原生打包APK方式2. Flutter通过原生工程打包方式3. Futte

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Python实现Microsoft Office自动化的几种方式及对比详解

《Python实现MicrosoftOffice自动化的几种方式及对比详解》办公自动化是指利用现代化设备和技术,代替办公人员的部分手动或重复性业务活动,优质而高效地处理办公事务,实现对信息的高效利用... 目录一、基于COM接口的自动化(pywin32)二、独立文件操作库1. Word处理(python-d

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

SpringBoot项目使用MDC给日志增加唯一标识的实现步骤

《SpringBoot项目使用MDC给日志增加唯一标识的实现步骤》本文介绍了如何在SpringBoot项目中使用MDC(MappedDiagnosticContext)为日志增加唯一标识,以便于日... 目录【Java】SpringBoot项目使用MDC给日志增加唯一标识,方便日志追踪1.日志效果2.实现步

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

kotlin的函数forEach示例详解

《kotlin的函数forEach示例详解》在Kotlin中,forEach是一个高阶函数,用于遍历集合中的每个元素并对其执行指定的操作,它的核心特点是简洁、函数式,适用于需要遍历集合且无需返回值的场... 目录一、基本用法1️⃣ 遍历集合2️⃣ 遍历数组3️⃣ 遍历 Map二、与 for 循环的区别三、高