排列组合. 有K个无重复的自然数集合(1,2,...,K).给定一个序列1 2 3 ... K, 请问有多少个不同序列?所求序列需要满足下列条件: 1)每个序列需要 无重复,用全部的的自然数,组成;2)相对于给定序列 1 2 3 ... K, 新产生的序列在相同的位置的数值与给定序列的数值不能相同. 举例,K=3,已知序列1 2 3, 需要求的序列就是 2 3 1 和 3 2 1.总共为2个.K=4, 已知序列 1 2 3 4, 要求的序列,如 2 1 4 3, 3 1 4 2,..., 总共为 9个.
问题描述:
排列组合. 有K个无重复的自然数集合(1,2,...,K).给定一个序列1 2 3 ... K, 请问有多少个不同序列?
所求序列需要满足下列条件:
1)每个序列需要 无重复,用全部的的自然数,组成;
2)相对于给定序列 1 2 3 ... K, 新产生的序列在相同的位置的数值与给定序列的数值不能相同.
举例,K=3,已知序列1 2 3, 需要求的序列就是 2 3 1 和 3 2 1.总共为2个.
K=4, 已知序列 1 2 3 4, 要求的序列,如 2 1 4 3, 3 1 4 2,..., 总共为 9个.
答
第一问很简单是K!或A(K,K)
第二问是全错位排列问题,用容斥原理来解
答案为K!(1/2!-1/3!+1/4!-1/5!+……+(-1)^K/K!)
可参考下面链接