【杂谈】记一次有趣的推导

事情的开端是一道题……..

题目描述

在组合数学中排列是一个非常重要的内容。例如,1 2 3 4 5 and 1 3 5 4 2 是两个55的排列。

众所周知,n的排列数是n!,根据它们的数量关系,如果我们可以在每对相邻的排列数之间插入符号“<”或“>”,我们能得到一个符号排列。例如,1 2 3 4 5 能变成1<2<3<4<51 3 5 4 2能变成1<3<5>4>2

现在你的任务是计算有多少个用k个“<”组成的nn排列。

 

然后….

我一开始看错题了……

我以为是要求出n的所有排列中小于号的个数……

然后我开始了推导…….

推导

首先我推出了递推式:f\left(n\right)=f\left(n-1\right)+\frac{\left(n-1\right)n}{2}\left(n-2\right)!

恩…..虽然看着很不清真,但至少得到了一个能算的式子…….

但……..我会就此罢休吗?!显然不会!

于是次日,我尝试着求出了通项式:f\left(n\right)=\frac{n!}{2}+\sum_{i=n}^3\frac{\left(i-1\right)!i}{2}\left(i-2\right)!\cdot\frac{n!}{i!}

但这个通项式看着还是很不清真,因为我发现它能化简!

于是我化简了一波:

然后我看着这个式子陷入了沉思…………

这明显还能化简啊woc!!而且还能化简的非常简单:f\left(n\right)=\frac{\left(n-1\right)\cdot n!}{2}

推出这个式子没过多久我就恍然大悟,在n的所有排列中大于号和小于号的数量是相等的,所以只需要算出n的排列中符号位的数量然后除二就好了……..于是就直接得出了最后的式子。

想到这里,看着之前得出的各种不清真的奇葩式子,瞬间感觉自己智商下线……….

2 Comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注