g*y
1 楼
November 06
一日3题
第一题。给一个数组a[1]到a[n] : 例如 1，2，3，4，5，6
现在随机生成a的一个permutation: b[1]到b[n] （例如：3 1 5 2 4 6）
问, a和b数组在每一位上都不相同的概率是多少？假设a本身没有重复的数
我的解法：
主问题：F(n) = 给定长度为n的a数组，b数组有多少种取法
辅助问题：结果用f(n)表示。 b数组是{1….i-1,x,i+1…n}的一个排列，其中x!=i，满
足a，b在每一位上都不相同，有多少种b？例如，a = 1,2,3,4; b是{1,2,5,4}的一个排
列。换句话说，组成b的元素中，有且只有一个数不在a中。
这样定义了F(n),f(n)后，很显然有递推关系：
F(n) = (n-1) * f(n-1) //解释：第一位有n-1种选择，任意一种选择后，问题变为
一个 n-1规模的辅助问题
f(n) = F(n-1) + (n-1)*f(n-1) //情况一，在b数组的第i位置填入x，考虑剩下的n-
1个位置，即是一个n-1规模的主问题；情况二，i位置填入非x的数，考虑剩下的n-
一日3题
第一题。给一个数组a[1]到a[n] : 例如 1，2，3，4，5，6
现在随机生成a的一个permutation: b[1]到b[n] （例如：3 1 5 2 4 6）
问, a和b数组在每一位上都不相同的概率是多少？假设a本身没有重复的数
我的解法：
主问题：F(n) = 给定长度为n的a数组，b数组有多少种取法
辅助问题：结果用f(n)表示。 b数组是{1….i-1,x,i+1…n}的一个排列，其中x!=i，满
足a，b在每一位上都不相同，有多少种b？例如，a = 1,2,3,4; b是{1,2,5,4}的一个排
列。换句话说，组成b的元素中，有且只有一个数不在a中。
这样定义了F(n),f(n)后，很显然有递推关系：
F(n) = (n-1) * f(n-1) //解释：第一位有n-1种选择，任意一种选择后，问题变为
一个 n-1规模的辅助问题
f(n) = F(n-1) + (n-1)*f(n-1) //情况一，在b数组的第i位置填入x，考虑剩下的n-
1个位置，即是一个n-1规模的主问题；情况二，i位置填入非x的数，考虑剩下的n-
