设第k首歌是一定要玩的,则其它歌平均积分为。
把P看作一个置换,设k在置换P下所在循环长度为l,即。考虑P所在的循环,一共有种情况,此时P限制在剩余的n-l首歌上也是一个置换,一共有种情况。所以k在置换P下所在循环长度为l的情况个数为。容易看出,此时的期望得分为。
因此,总期望得分为。