精华内容
下载资源
问答
  • 研究一个排列错排个数的问题,叫做错排问题或称为更列问题。 当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用D(n)表示,那么D(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数...

    题目:小林给四个朋友写信,但四个朋友收到的都是他给别人写的信,问:小林装信装错的情况又多少种?

    错排问题,是组合数学中的问题之一。考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个数的问题,叫做错排问题或称为更列问题。

    当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用D(n)表示,那么D(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.

    第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;

    第二步,放编号为k的元素,这时有两种情况:⑴把它放到位置n,那么,对于剩下的n-1个元素,由于第k个元素放到了位置n,剩下n-2个元素就有D(n-2)种方法;⑵第k个元素不把它放到位置n,这时,对于这n-1个元素,有D(n-1)种方法;

    综上得到

    D(n) = (n-1) [D(n-2) + D(n-1)]

    特殊地,D(1) = 0, D(2) = 1.

    下面通过这个递推关系推导通项公式:

    为方便起见,设D(k) = k! N(k), k = 1, 2, …, n,

    则N(1) = 0, N(2) = 1/2.

    n ≥ 3时,n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)

    即 nN(n) = (n-1) N(n-1) + N(n-2)

    于是有N(n) - N(n-1) = - [N(n-1) - N(n-2)] / n = (-1/n) [-1/(n-1)] [-1/(n-2)]…(-1/3) [N(2) - N(1)] = (-1)^n / n!.

    因此

    N(n-1) - N(n-2) = (-1)^(n-1) / (n-1)!,

    N(2) - N(1) = (-1)^2 / 2!.

    相加,可得

    N(n) = (-1)^2/2! + … + (-1)^(n-1) / (n-1)! + (-1)^n/n!

    因此

    D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].

    此即错排公式。

    根据上述内容,我们便可以解决这道题了。

    解答:D(4)=3*(D(3)+D(2))=3*(2+1)=9(种)

    展开全文
  • 欧拉错排公式

    千次阅读 2014-04-28 12:38:51
    欧拉错排公式经常在ACM中遇到 void init() { s[0]=0; s[1]=0; s[2]=1; int i; for (i=3;i;i++) s[i]=(i-1)*(s[i-1]+s[i-2])%mod; }
    欧拉错排公式经常在ACM中遇到
    void init()
    {
        s[0]=0; s[1]=0; s[2]=1;
        int i;
        for (i=3;i<=100;i++)
            s[i]=(i-1)*(s[i-1]+s[i-2])%mod;
    }

    展开全文
  • 错排问题

    千次阅读 2018-11-14 18:43:25
    最早的错排是伯努利-欧拉信封问题,n封信装入n个信封结果没有一封装入正确的地址的方案数。类似的还有写贺卡问题,n个人互相写贺卡互相赠送自己写的不能赠送给自己,问赠送的方案数。还有拿出来n本书放回去的时候...

    1.错排问题很早就别研究起来,并且形式多样。最早的错排是伯努利-欧拉信封问题,n封信装入n个信封结果没有一封装入正确的地址的方案数。类似的还有写贺卡问题,n个人互相写贺卡互相赠送自己写的不能赠送给自己,问赠送的方案数。还有拿出来n本书放回去的时候恰好都不在原来的位置的方案数。等等很多类似的问题,错排的准确的意义就是每个元素都不在自己原来的位置。如果只是有几个元素不在自己原来的位置,不能叫做错排,这叫做非完全错排,当然这也是很好解决的,只要在这几个人中间进行错排,又转化为错排的问题。

    2.错排的公式:错排的公式有很多种,每一种意义下的都有不同的公式,但是殊途同归,结果都是一样的,只不过出发点不同。我们给出几种错排的公式,但是只证明其中一种,其他的有兴趣的可以自己证明。

    普通意义下的错排:D(n)=(n-1)*(D(n-1+D(n-2)),其实这个公式的推导很简单的,我们来严格证明一下(口嗨)。我们考虑第一个元素a1,他的位置可以有n-1中选择,假设它现在是在第i个位置,那么对于第i个元素就会有两种选择。

    (1)i在a1原来的位置。那么其实a1和ai独立于整个排列。也就是D(n-2)

    (2)i不在原来的位置,那么也很简单,这个时候a1已经排列好了,那么就可以丢掉了,继续考虑ai占据的这个元素的位置,其实也就是D(n-1)转移过来。

    综合1,2可以得到。D(n)=(n-1)(D(n-1)+D(n-2)).当然通过容斥也是可以推导出来的,以及给出O(1)的公式。

    容斥原理推导的错排公式:D(n) = n! - n!/1! + n!/2! - n!/3! + … + (-1)^n*n!/n! = ∑(k=2~n) (-1)^k * n! / k!,
    简化版的公式:D(n) = [n!/e+0.5] ,其中e是自然对数的底,[x]为x的整数部分。

    3.小数据范围下的错排数:

    D(0) = 1(所有的元素都放回原位、没有摆错的情况)

    D(1) = 0(只剩下一个元素,无论如何也不可能摆错)

    D(2) = 1(两者互换位置)

    D(3) = 2(ABC变成BCA或CAB)

    D(4) = 9

    D(5) = 44

    D(6) = 265

    D(7) = 1854

    D(8) = 14833

    D(9) = 133496

    4.几个裸题:

    //HDU1465
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    #define ll long long
    ll mis[30];
    int n;
    void init()
    {
    	mis[0] = 1;
    	mis[1] = 0;//一个元素不会排错
    	for (int i = 2; i <= 30; i++)
    	{
    		mis[i] = (i - 1)*(mis[i-1] + mis[i - 2]);
    	}
    }
    #pragma warning(disable:4996)
    int main()
    {
    	int n;
    	init();
    	while (~scanf("%d", &n))
    	{
    		printf("%lld\n", mis[n]);
    	}
        return 0;
    }
    l范围内只在不取模的情况下只能将mis计算到23,也就是D(22)是正确的。大于这个范围就是爆掉ll
    //HDU2068
    #include<iostream>
    using namespace std;
    #define ll long long
    #pragma warning(disable:4996)
    ll C(int n, int m)                //组合数公式
    {
        ll u, d, i;         //组合数公式中的 分子u和分母d
        if (m>n / 2) m = n - m;                     //防止溢出 
        for (u = d = i = 1; i <= m; i++)
        {
            u = u * (n - i + 1);
            d = d * i;
        }
        return u / d;
    }
    int main()
    {
        int i, M, N;
        ll f[14] = { 1,0,1 }, sum;
        for (i = 3; i <= 13; i++)
            f[i] = (i - 1)*(f[i - 1] + f[i - 2]);
        while (scanf("%d", &N), N)
        {
            for (sum = i = 0; i <= N / 2; i++)
                sum += C(N, N - i)*f[i];
            printf("%lld\n", sum);
    
        }
        return 0;
    }
    //HDU2049
    #include<iostream>
    using namespace std;
    #define ll long long
    #pragma warning(disable:4996)
    ll C(int n, int m)                
    {
        ll u, d, i;        
        if (m>n / 2) m = n - m;                     
        for (u = d = i = 1; i <= m; i++)
        {
            u = u * (n - i + 1);
            d = d * i;
        }
        return u / d;
    }
    int main()
    {
        int i;
        int m, N;
        ll f[20] = { 1,0,1 }, sum;
        for (i = 3; i <= 20; i++)
            f[i] = (i - 1)*(f[i - 1] + f[i - 2]);
        int t;
        cin >> t;
        while (t--)
        {
            while (cin >> N >> m)
            {
            /*    for (sum = i = 0; i <= m; i++)
                    sum += C(N, N - i)*f[i];*/
                sum = C(N, m)*f[m];
                printf("%lld\n", sum);
    
            }
        }
        return 0;
    }

     

    展开全文
  • 错排问题--错排公式的推导及应用

    万次阅读 多人点赞 2017-08-12 11:05:19
    错排问题是组合数学中的问题之一。...最早研究错排问题的是尼古拉·伯努利和欧拉,因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本,如在写信时将n封信装到n个不同的信封里,有多少

    错排问题组合数学中的问题之一。考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为Dn。 研究一个排列错排个数的问题,叫做错排问题或称为更列问题

    最早研究错排问题的是尼古拉·伯努利欧拉,因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本,如在写信时将n封信装到n个不同的信封里,有多少种全部装错信封的情况?又比如四人各写一张贺年卡互相赠送,有多少种赠送方法?自己写的贺年卡不能送给自己,所以也是典型的错排问题。


    例如有{\displaystyle n}n封写好了的信,收件人不同,胡乱放入{\displaystyle n}n个写了地址的信封中,寄出,求没有一个收件人收到他所应接收的信的概率。当{\displaystyle n=4}n=4,在4! = 24个排列之中,只有9个是错排:

    BADC, BCDA, BDAC,
    CADB, CDAB, CDBA,
    DABC, DCAB, DCBA,

    所以有关概率为9/24 = 37.5%


    推导:

    显然D1=0,D2=1。当n≥3时,不妨设n排在了第k位,其中k≠n,也就是1≤k≤n-1。那么我们现在考虑第n位的情况。

    • 当k排在第n位时,除了n和k以外还有n-2个数,其错排数为Dn-2
    • 当k不排在第n位时,那么将第n位重新考虑成一个新的“第k位”,这时的包括k在内的剩下n-1个数的每一种错排,都等价于只有n-1个数时的错排(只是其中的第k位会换成第n位)。其错排数为Dn-1

    所以当n排在第k位时共有Dn-2+Dn-1种错排方法,又k有从1到n-1共n-1种取法,我们可以得到:

    D n=(n-1)(D n-1+D n-2

    在上面我们得到Dn=(n-1)(Dn-1+Dn-2) 从这个公式中我们可以推出Dn的通项公式,方法如下:

    为书写方便,记Dn = n!Mn,则M1 = 0, M2 = {\displaystyle {\frac {1}{2}}}{\frac {1}{2}}

    当n大于等于3时,由Dn = (n-1)(Dn-1 + Dn-2),即{\displaystyle n!M_{n}=(n-1)(n-1)!M_{n-1}+(n-1)(n-2)!M_{n-2}=n!M_{n-1}-(n-1)!M_{n-1}+(n-1)!M_{n-2}}n!M_{n}=(n-1)(n-1)!M_{​{n-1}}+(n-1)(n-2)!M_{​{n-2}}=n!M_{​{n-1}}-(n-1)!M_{​{n-1}}+(n-1)!M_{​{n-2}}。 所以,{\displaystyle nM_{n}-nM_{n-1}=-M_{n-1}+M_{n-2}}nM_{n}-nM_{​{n-1}}=-M_{​{n-1}}+M_{​{n-2}}

    于是有 {\displaystyle M_{n}-M_{n-1}=-{\frac {1}{n}}(M_{n-1}-M_{n-2})=...=(-{\frac {1}{n}})(-{\frac {1}{n-1}})...(-{\frac {1}{3}})(M_{2}-M_{1})=(-1)^{n}{\frac {1}{n!}}.}M_{n}-M_{​{n-1}}=-{\frac  {1}{n}}(M_{​{n-1}}-M_{​{n-2}})=...=(-{\frac  {1}{n}})(-{\frac  {1}{n-1}})...(-{\frac  {1}{3}})(M_{2}-M_{1})=(-1)^{n}{\frac  {1}{n!}}.

    所以

    {\displaystyle {\begin{aligned}M_{n}-M_{n-1}&=(-1)^{n}{\frac {1}{n!}}\\M_{n-1}-M_{n-2}&=(-1)^{(n-1)}{\frac {1}{(n-1)!}}\\\vdots \quad &=\quad \vdots \\M_{2}-M_{1}&=(-1)^{2}{\frac {1}{2!}}\\\end{aligned}}}{\begin{aligned}M_{​{n}}-M_{​{n-1}}&=(-1)^{​{n}}{\frac  {1}{n!}}\\M_{​{n-1}}-M_{​{n-2}}&=(-1)^{​{(n-1)}}{\frac  {1}{(n-1)!}}\\\vdots \quad &=\quad \vdots \\M_{2}-M_{1}&=(-1)^{2}{\frac  {1}{2!}}\\\end{aligned}}

    将上面式子分边累加,得{\displaystyle M_{n}=(-1)^{2}{\frac {1}{2!}}+(-1)^{3}{\frac {1}{3!}}...+(-1)^{n}{\frac {1}{n!}}.}M_{n}=(-1)^{2}{\frac  {1}{2!}}+(-1)^{3}{\frac  {1}{3!}}...+(-1)^{​{n}}{\frac  {1}{n!}}.

    因此,我们得到错排公式{\displaystyle D_{n}=n!M_{n}=n!({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}).}D_{n}=n!M_{n}=n!({\frac  {1}{2!}}-{\frac  {1}{3!}}+...+(-1)^{n}{\frac  {1}{n!}}).

    简化公式


    错位排列数的公式可以简化为:{\displaystyle D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor ,}D_{n}=\left\lfloor {\frac  {n!}{e}}+0.5\right\rfloor ,

    其中的 {\displaystyle \lfloor n\rfloor }\lfloor n\rfloor  为高斯取整函数(小于等于 n 的最大整数)。

    这个简化公式可以由之前的错排公式推导出来。事实上,考虑指数函数在 0 处的泰勒展开:

    {\displaystyle {\begin{aligned}e^{-1}&=1+{\frac {\left(-1\right)^{1}}{1!}}+{\frac {\left(-1\right)^{2}}{2!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+{\frac {e^{-c}}{(n+1)!}}\left(c-1\right)^{n}\\&={\frac {1}{2!}}-{\frac {1}{3!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+R_{n}\\&={\frac {D_{n}}{n!}}+R_{n}\\\end{aligned}}}{\begin{aligned}e^{​{-1}}&=1+{\frac  {\left(-1\right)^{1}}{1!}}+{\frac  {\left(-1\right)^{2}}{2!}}+\cdots +\left(-1\right)^{n}{\frac  {1}{n!}}+{\frac  {e^{​{-c}}}{(n+1)!}}\left(c-1\right)^{n}\\&={\frac  {1}{2!}}-{\frac  {1}{3!}}+\cdots +\left(-1\right)^{n}{\frac  {1}{n!}}+R_{n}\\&={\frac  {D_{n}}{n!}}+R_{n}\\\end{aligned}}

    所以,{\displaystyle {\frac {n!}{e}}-D_{n}=n!\,R_{n}}{\frac  {n!}{e}}-D_{n}=n!\,R_{n}。其中 Rn 是泰勒展开的余项,c 是介于 0 和 1 之间的某个实数。Rn 的绝对值上限为

    {\displaystyle |R_{n}|\leqslant {\frac {e^{0}}{(n+1)!}}={\frac {1}{(n+1)!}}}|R_{n}|\leqslant {\frac  {e^{0}}{(n+1)!}}={\frac  {1}{(n+1)!}}
    {\displaystyle {\Big |}{\frac {n!}{e}}-D_{n}{\Big |}\leqslant {\frac {n!}{(n+1)!}}={\frac {1}{(n+1)}}}{\Big |}{\frac  {n!}{e}}-D_{n}{\Big |}\leqslant {\frac  {n!}{(n+1)!}}={\frac  {1}{(n+1)}}

    当 n≥2 时,{\displaystyle {\frac {1}{(n+1)}}}{\frac  {1}{(n+1)}} 严格小于 0.5,所以 {\displaystyle D_{n}=n!\left({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}\right)}D_{n}=n!\left({\frac  {1}{2!}}-{\frac  {1}{3!}}+...+(-1)^{n}{\frac  {1}{n!}}\right) 是最接近 {\displaystyle {\frac {n!}{e}}}{\frac  {n!}{e}} 的整数,可以写成

    {\displaystyle D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor .}D_{n}=\left\lfloor {\frac  {n!}{e}}+0.5\right\rfloor .

    错位排列数的公式可以简化为:{\displaystyle D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor ,}D_{n}=\left\lfloor {\frac  {n!}{e}}+0.5\right\rfloor ,

    其中的 {\displaystyle \lfloor n\rfloor }\lfloor n\rfloor  为高斯取整函数(小于等于 n 的最大整数)[5]

    这个简化公式可以由之前的错排公式推导出来。事实上,考虑指数函数在 0 处的泰勒展开

    {\displaystyle {\begin{aligned}e^{-1}&=1+{\frac {\left(-1\right)^{1}}{1!}}+{\frac {\left(-1\right)^{2}}{2!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+{\frac {e^{-c}}{(n+1)!}}\left(c-1\right)^{n}\\&={\frac {1}{2!}}-{\frac {1}{3!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+R_{n}\\&={\frac {D_{n}}{n!}}+R_{n}\\\end{aligned}}}{\begin{aligned}e^{​{-1}}&=1+{\frac  {\left(-1\right)^{1}}{1!}}+{\frac  {\left(-1\right)^{2}}{2!}}+\cdots +\left(-1\right)^{n}{\frac  {1}{n!}}+{\frac  {e^{​{-c}}}{(n+1)!}}\left(c-1\right)^{n}\\&={\frac  {1}{2!}}-{\frac  {1}{3!}}+\cdots +\left(-1\right)^{n}{\frac  {1}{n!}}+R_{n}\\&={\frac  {D_{n}}{n!}}+R_{n}\\\end{aligned}}

    所以,{\displaystyle {\frac {n!}{e}}-D_{n}=n!\,R_{n}}{\frac  {n!}{e}}-D_{n}=n!\,R_{n}。其中 Rn 是泰勒展开的余项,c 是介于 0 和 1 之间的某个实数。Rn 的绝对值上限为

    {\displaystyle |R_{n}|\leqslant {\frac {e^{0}}{(n+1)!}}={\frac {1}{(n+1)!}}}|R_{n}|\leqslant {\frac  {e^{0}}{(n+1)!}}={\frac  {1}{(n+1)!}}
    {\displaystyle {\Big |}{\frac {n!}{e}}-D_{n}{\Big |}\leqslant {\frac {n!}{(n+1)!}}={\frac {1}{(n+1)}}}{\Big |}{\frac  {n!}{e}}-D_{n}{\Big |}\leqslant {\frac  {n!}{(n+1)!}}={\frac  {1}{(n+1)}}

    当 n≥2 时,{\displaystyle {\frac {1}{(n+1)}}}{\frac  {1}{(n+1)}} 严格小于 0.5,所以 {\displaystyle D_{n}=n!\left({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}\right)}D_{n}=n!\left({\frac  {1}{2!}}-{\frac  {1}{3!}}+...+(-1)^{n}{\frac  {1}{n!}}\right) 是最接近 {\displaystyle {\frac {n!}{e}}}{\frac  {n!}{e}} 的整数,可以写成

    {\displaystyle D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor .}D_{n}=\left\lfloor {\frac  {n!}{e}}+0.5\right\rfloor .


    递推公式:Dn=(n-1)(Dn-1+Dn-2)  n>3, D= 0 , D2 = 1;也就是上述中推导错排公式所用到的公式


    下面用错排递推公式做几个几个例子;

    例1;装错信封的问题(经典原型)HDU1465题

    写n封信,全部装错信封,求有多少种全部装错的方式

    #include<iostream>
    using namespace std;
    
    int main() {
    	int n;
    	long long d[21] = {0,0,1};//将d[0],d[1],d[2]初始化
    	for(int i=3;i<=20;i++) {
    		d[i] = (i-1)*(d[i-1]+d[i-2]);
    	} 
    	while(cin >> n) {
    		cout << d[n] <<endl;
    	}
    	return 0;
    }


    例2:考新郎HUD2049

    首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

    阅读题目后我们不难发现,这道题的本质就是求解排列组合C(n,m)与错排m个元素D(m)的乘积,因此这道题的代码也十分简单,以下提供两种AC程序:

    //#方法1:递推公式--D(n)=(n-1)*(D(n-1)+D(n-2)) [D(1)=0,D(2)=1]
    #include<bits/stdc++.h>//万能头文件,只有少部分oj支持
    using namespace std;
    
    int main() {
    	int ti,n,m;
    	long long f[21] = {0,0,1},t[21] = {1,1,2};
    	for(int i=3;i<=20;i++) {
    		f[i] = (i-1)*(f[i-1]+f[i-2]);
    		t[i] = t[i-1]*i;
    	}
    	cin >> ti;
    	while(ti--) {
    		cin >> n >> m;
    		long long a = t[n]/t[m]/t[n-m];
    		cout << a*f[m] <<endl;
    	}
    	return 0;
    }

    /*#方法2:通项公式--D(n)=n!*(1/2!-1/3!+1/4!- 1/5!+ ··· ··· +((-1)^(n-1))/(n-1)!+((-1)^n)/n! )
    这里可以根据题目做一下变形:
    F(n,m)=C(n,m)*D(m)=n!*(1/2!-1/3!+1/4!- 1/5!+ ··· ··· +((-1)^(n-1))/(n-1)!+((-1)^n)/n! )/(n-m)!*/
    #include<bits/stdc++.h>
    using namespace std;
    
    int ti,n,m;
    long long f[21] = {0,0,1},t[21] = {1,1,2};
    
    long long sol() {
    	long long sum=0,a=t[n],b=t[n-m];
    	for(int i=2; i<=m; ++i) {
    		a/=i;
    		if(i%2==0)
    			sum+=a;
    		else
    			sum-=a;
    	}
    	return sum/b;
    }
    
    int main() {
    	for(int i=3; i<=20; i++) {
    		f[i] = (i-1)*(f[i-1]+f[i-2]);
    		t[i] = t[i-1]*i;
    	}
    	cin >> ti;
    	while(ti--) {
    		cin >> n >> m;
    		cout << sol() <<endl;
    	}
    	return 0;
    }

    关于 #include<bits/stdc++.h> ACM常用C++常用模板,可以访问 ACM常用C++模板 包括常用头文件

    展开全文
  • 错排问题(全错排)

    千次阅读 2018-11-11 17:15:37
    错排问题(全错位排列问题 Derangement) 概念: 考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个...
  • FZU 2282 Wand(错排公式)

    2018-09-08 10:53:28
    错排公式为n个数都不在自己位置上的所有可能情况数量,递推求得错排数Staggered[i] ∑ i − k n C n i ∗ S t a g g e r e d [ n − i ] \sum_{i-k}^{n}C^{i}_{n}*Staggered[n-i] ∑ i − k n ​ C n i ​ ∗ S t ...
  • 题目解释: 某人写了n封信,还有n个信封,如果所有的信都装错了信封,求共有多少种可能的情况?... 研究一个排列错排个数的问题,叫做错排问题或称为更列问题。 当n个编号元素放在n个编号位置,元素编号...
  • 【证明】错排公式

    2017-10-04 20:01:55
    来源:百度百科问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放... 研究一个排列错排个数的问题,叫做错排问题或称为更列问题。当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用D
  • 关于错排公式的推导与应用

    千次阅读 2016-03-24 13:52:00
    错排公式的详细推导过程和简单应用
  • 从n个里面选取k表示这k个在各自的位置,剩下n-k个用错排排一下。因为k较小,所以要求从k到n这个区间的值较大,我们可以求不符合条件的情况,即符合条件的魔杖有0个,有1个,有2个...有k-1个,然后拿总的排列数减去不...
  • 伯努利错排列问题

    千次阅读 2017-10-01 16:37:37
    全错位排列:即被著名数学家欧拉(Leonhard Euler,1707-1783)称为组合数论的一个妙题的“装错信封问题”。 “装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli,1667-1748)的儿子丹尼尔·...
  • https://vj.xtuacm.cf/contest/view.action?cid=57#problem/O这题要转换成求两个区间内互斥的数 有多少对 并且不重复 题目大意:求1到b内x,1到d内y,gcd(x,y)= k 的对数,二元组无序,要求不重复 ...
  • 错位排列递推公式推导

    万次阅读 2015-12-01 17:11:15
    全错位排列:即被著名数学家欧拉(Leonhard Euler,1707-1783)称为组合数论的一个妙题的“装错信封问题”。 “装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli,1667-1748)的儿子丹尼尔·...
  • 神奇的错排问题

    2021-05-20 18:50:28
    原标题:神奇的错排问题小谜题大世界有一道经典的数学问题:A和B每人持一门花色的牌(各13张),背面向上,并打乱。然后每人出一张牌比较大小,共出13轮,试求这13轮中点数均不一样的概率。这个问题看起来很简单,实则...
  • 错排问题-C++实现

    2020-05-26 13:08:44
    最早研究错排问题的是尼古拉·伯努利和欧拉,因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本,如在写信时将n封信装到n个不同的信封里,有多少种全部装错信封的情况?又比如四人各写一张贺...
  • 错排问题比较难,但是也是经典算法问题 文章目录1 错排问题2 总结 1 错排问题 家中阳台有10盆不同的花,为保持新鲜感,希望每天重新摆放,使得每盆花都不在第一天放的位置。...也称作“伯努利-欧拉错...
  • 错排问题及错排公式

    2014-08-05 16:04:06
    问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题,是组合数学中的问题之一。...错排问题最早被尼古拉·伯努利和欧拉研究,因此历史上也
  • 错排

    2017-07-23 16:42:20
    错排导入: 问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题,是组合数学中的问题之一。...错排问题最早被尼古拉·伯努利和欧拉研究,
  • 容斥原理 + 欧拉函数

    2018-07-16 21:29:58
    对容斥原理的描述 容斥原理是一种重要的组合数学方法,可以让你求解任意大小的集合,或者计算复合事件的概率。 描述 &amp;amp;amp;amp;nbsp;&amp;amp;amp;...容斥原理可以描述如下:
  • 错排公式

    2018-11-15 15:21:52
    结论: 递推式: D(n) = (n-1) [D(n-2) + D(n-1)] 其中,D(1) = 0, D(2) = 1. 通项公式: D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!]. ...这个问题推广一下,就是错排问题...
  • 也称 伯努利-欧拉装错信封问题 n错排公式:F[n]=(n-1)*(F[n-1]+F[n-2]) 证明: 1.当前n-1个错排时:将其任意一封信与n对调,共(n-1)*F[n-1] 2.当前n-2个错排,1个不错排时,将不错排的那封信与n对调,共(n-1)*F[n-...
  • 错排问题,错位排列

    千次阅读 2016-02-16 08:39:39
    1、问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题,是组合数学中的问题之一。...错排问题最早被尼古拉·伯努利和欧拉研究,
  • 错排公式问题引入问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?这个问题推广一下,就是错排问题,是组合数学中的问题之一...错排问题最早被尼古拉·伯努利和欧拉研究,因此历

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 433
精华内容 173
关键字:

欧拉错排