「组合数」错排问题

前言——为什么要写这篇文章

学校数学学案上的一道计数原理的题目:

有4个小球和4个盒子,编号分别为1,2,3,4,要求编号为n的盒子不能放编号为n的小球,求一功能有多少种方法放球. ans = 44

我当时真的没有任何思路,上课讲也没怎么听懂,回家用把这道题用程序解了一下,代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define N 105
int a[N],vis[N],n,k;
long long ans;
void out(){
    if(!k){
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
}
void dfs(int dep){
    if(dep==n+1){ans++;return ;}
    for(int i=1;i<=n;i++){
        if(!vis[i] && i!=dep){
            vis[i]=1;
            a[dep]=i;
            dfs(dep+1);
            vis[i]=0;
        }
    }
}
int main(){
    k=0;
    while(1){
        cin>>n;
        ans=0;
        memset(vis,0,sizeof(vis));
        if(n==0){cout<<0<<endl;continue;}
        if(n==1){cout<<0<<endl;continue;}
        dfs(1);
        printf("所求n值为 %d 时的解个数: %lld \n",n,ans);
    }
    /*cin>>k;
    for(int i=0;i<=k;i++){
        n=i;
        ans=0;
        if(n==0){cout<<0<<endl;continue;}
        if(n==1){cout<<0<<endl;continue;}
        dfs(1);
        printf("所求n值为 %d 时的解个数: %lld \n",n,ans);
    }
    */
    return 0;
}
/*
所求n值为 2 时的解个数: 1 
所求n值为 3 时的解个数: 2 
所求n值为 4 时的解个数: 9 
所求n值为 5 时的解个数: 44 
所求n值为 6 时的解个数: 265 
所求n值为 7 时的解个数: 1854 
所求n值为 8 时的解个数: 14833 
所求n值为 9 时的解个数: 133496 
所求n值为 10 时的解个数: 1334961 
所求n值为 11 时的解个数: 14684570 
所求n值为 12 时的解个数: 176214841 
*/

思路很容易想,就是回溯法。得出的结论很重要,顺手在网上搜了一下:

1 4 9 44 265 1854 14833 133496 1334961

我好像发现了什么不得了的事情

这个,貌似就是 BZOJ 4563 [HAOI2016]放棋子的标程(改点东西就是了)…

貌似也是这道 HDUOJ 2068

BZOJ 4563:

Time Limit: 10 Sec Memory Limit: 128 MB Submit: 454 Solved: 298

Description

给你一个N*N的矩阵,每行有一个障碍,数据保证任意两个障碍不在同一行,任意两个障碍不在同一列,要求你在

这个矩阵上放N枚棋子(障碍的位置不能放棋子),要求你放N个棋子也满足每行只有一枚棋子,每列只有一枚棋子

的限制,求有多少种方案。

Input

第一行一个N,接下来一个N*N的矩阵。N<=200,0表示没有障碍,1表示有障碍,输入格式参考样例

Output

一个整数,即合法的方案数。

Sample Input

2
0 1
1 0

Sample Output

1

分析

方案数:错排问题

洛谷给的标签:[高精度][二分图][递推]

有点像加强版的八皇后

本巨弱还没看题。。。

HDUOJ 2068

RPG的错排

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 14066 Accepted Submission(s): 5733

Problem Description

今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜,第一次猜:R是公主,P是草儿,G是月野兔;第二次猜:R是草儿,P是月野兔,G是公主;第三次猜:R是草儿,P是公主,G是月野兔;……可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动,做ACM的女生越来越多,我们的野骆驼想都知道她们,可现在有N多人,他要猜的次数可就多了,为了不为难野骆驼,女生们只要求他答对一半或以上就算过关,请问有多少组答案能使他顺利过关。

Input

输入的数据里有多个case,每个case包括一个n,代表有几个女生,(n<=25), n = 0输入结束。

Sample Input

1
2
0

Sample Output

1
1

这并不是今天的重点

回归学案上的那道题,有一个比较著名的问题叫做:错排问题

推导公式:

F(n)=(n-1)*(f(n-1)+f(n-2))

推导

F(1)=0

F(2)=1

设n个不同元素分别标号1,2,3,…,n,要求它们分别

被放入标号为1,2,3,……,n的位置上,一个位置有且有一个元素,且元素的标号与位置的标号不能相同,记其方法数为F(n)

  1. 从中任取一个元素,不妨取1号元素,还剩n-1个元素,再从这n-1个元素对应的位置中选一个,共n-1种方法
  2. 假设选取的位置是2号位,以下分两种情况

第一种,1号元素放入2号位置且2号元素也放入1号位置,此时剩下n-2个元素继续错排,共F(n-2)种方法

第二种,1号元素放入2号位置但2号元素不放入1号位置,既然2号元素不放入1号位置,不妨把2号元素看作1号元素,于是等价于新的1号元素不放入1号位置,那么剩下n-1个元素继续错排,共F(n-1)种方法

所以有递推式:

F[n]=(n-1)*(f[n-1]+f[n-2])

感想

这道题本来只是学案上的一道题,数学课讲的有点没听懂,好事儿的我就研究了一下。发现和OI有很大交集,数学上可以拿容斥原理证明,我的OI经验却趋势我用一种类似DP的方法思考了许久,结果发现,这种思想帮助了我轻松的证明了这个问题。

参考英文文献:

Number of derangements

There are no approved revisions of this page, so it may not have been reviewed.

This article needs more work.
Please help by expanding it!

The number of (complete) derangements, or number of permutations with no rencontres[1] of \scriptstyle n \, distinct objects (i.e. the number of permutations of \scriptstyle n \, distinct objects with no fixed point) is given by the subfactorial \scriptstyle !n \, of \scriptstyle n \,. The derangement numbers are given by the subfactorial numbers.

Formula

Subfactorial numbers

A000166 Subfactorial or rencontres numbers,[2] or derangements: number of permutations of n elements with no fixed points.

The last digit (base 10) of \scriptstyle !n,\, n \,\ge\, 0, \, seems to follow the pattern (of length 10)

Example

You have 6 balls in 6 different colors, and for every ball you have a box of the same color. How many derangements do you have, if no ball is in a box of the same color?

Comparison of derangement, permutation and arrangement numbers

n \, Number of derangementsd_n \equiv n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \,d_n \approx (1/e) ~ n! \,d_n = \left[ \frac {n!}{e} \right] = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor,\, n \ge 1 \, Number of permutationsn! \, Number of arrangementsa_n \equiv n! \sum_{k=0}^{n}\frac{1}{k!} \,a_n \approx e ~ n! \,a_n = \left\lfloor e ~ n! \right\rfloor,\, n \ge 1 \,
0 1 1 1
1 0 1 2
2 1 2 5
3 2 6 16
4 9 24 65
5 44 120 326
6 265 720 1957
7 1854 5040 13700
8 14833 40320 109601
9 133496 362880 986410
10 1334961 3628800 9864101
11 14684570 39916800 108505112
12 176214841 479001600 1302061345
13 2290792932 6227020800 16926797486
14 32071101049 87178291200 236975164805
15 481066515734 1307674368000 3554627472076
16 7697064251745 20922789888000 56874039553217
17 130850092279664 355687428096000 966858672404690
18 2355301661033953 6402373705728000 17403456103284421
19 44750731559645106 121645100408832000 330665665962404000
20 895014631192902121 2432902008176640000 6613313319248080001

Recurrences

Note that the factorial has a similar recurrence

So, for \scriptstyle n \,\ge\, 2, \,

Other formulae

where \scriptstyle e \, (Cf. A001113) is Euler’s number and \scriptstyle \Gamma(z,a) \, is the incomplete gamma function.

A very good approximation is given by

If rounded, you get a perfect formula for \scriptstyle n \,\ge\, 1 \,

If you add 1 to the factorial, before dividing, you can truncate instead of rounding to get a perfect formula for \scriptstyle n \,\ge\, 1 \,

n \, !n \, \frac{n!}{e} \, \left[ \frac {n!}{e} \right] \, \frac{n!+1}{e} \, \left\lfloor \frac{n!+1}{e} \right\rfloor \,
0 1 0,3679 0 0,7358 0
1 0 0,3679 0 0,7358 0
2 1 0,7358 1 1,1036 1
3 2 2,2073 2 2,5752 2
4 9 8,8291 9 9,1970 9
5 44 44,1455 44 44,5134 44
6 265 264,8732 265 265,2411 265
7 1854 1854,1124 1854 1854,4803 1854
8 14833 14832,8991 14833 14833,2669 14833
9 133496 133496,0916 133496 133496,4595 133496

where \scriptstyle \left[ n \right] \, is the round function and \scriptstyle \left\lfloor n \right\rfloor \, is the floor function.

There is a sequence (Cf. A000255) \scriptstyle a_n \,=\, !(n+1)+!n \,=\, !(n+2)/(n+1) \, with the members \scriptstyle a_0 \,=\, 1,\, a_1 \,=\, 1 \,, and the recursive rule:

With this sequence you can calculate the subfactorial

!n \, 1 0 1 2 9 44 265 1854 14833 133496 1334961
n \, 0 1 2 3 4 5 6 7 8 9 10
a_n \, 1 1 3 11 53 309 2119 16687 148329 1468457 16019531

Generating function

Ordinary generating function

where \scriptstyle {\rm Ei}(x) \, is the exponential integral.

Exponential generating function

Asymptotic behaviour

The limit of the quotient of \scriptstyle n\, factorial and \scriptstyle n\, subfactorial converges to \scriptstyle e \, (Cf. A001113 and Euler’s number)

Proof:

The limit of the quotient of the number of arrangements \scriptstyle a_n \, of any subset of \scriptstyle n \, distinct objects over the number of derangements \scriptstyle d_n \, of \scriptstyle n \, distinct objects converges to \scriptstyle e^2 \, (Cf. A072334)

The geometric mean of the number of arrangements and the number of derangements is asymptotic to the number of permutations

Permutations having at least one fixed point

The number of permutations \scriptstyle f_n \, having at least one fixed point, thus not being (complete) derangements is given by

where the second summation gives the empty sum (defined as the additive identity, i.e. 0) for \scriptstyle n \,=\, 0 \,.

Sequences

The subfactorial numbers (or rencontres numbers, or derangements: number of permutations of \scriptstyle n\, elements with no fixed points) \scriptstyle !n,\, n \ge 0, \, (Cf. A000166) are

\scriptstyle a_n \,=\, !(n+1)+!n \,=\, \frac{!(n+2)}{n+1} \,=\, n a(n-1) + (n-1) a(n-2),\, a(0) \,=\, 1,\, a(1) \,=\, 1, \, (Cf. A000255) gives

The number \scriptstyle n! - !n \, of permutations of \scriptstyle n,\, n \,\ge\, 0 \,, having a fixed point (Cf. A002467) are

See also

Notes

  1. “Rencontre” being a french word meaning encounter.
  2. Number of permutations with 0 rencontres, i.e. number of permutations with 0 fixed points.

References

Categories: Articles needing more work | Number of derangements

分享到