怨言数---日本小学竞赛题

bbs.aoshu.cn 2004-05-27 12:31:00

有从一年级到六年级的儿童各一人，排成一列领取糖果。

　　如果一个高年级的儿童站在低年级的儿童前面，那么高级年儿童后面所有比他年级低的儿童都会各有一次“怨言”。

　　在一种排列顺序里，我们把所有“怨言”的总数叫“怨言数”。（注：一个人可以有两次以上的“怨言”。）

　　例如：下面的排列，其“怨言数”就是4。

　　（前） “怨言”

　　1年级生 0次

　　4年级生 0次

　　3年级生 1次

　　2年级生 2次

　　6年级生 0次

　　5年级生 1次

　　“怨言数”…4次

　　问：“怨言数”为7的排列顺序有几种？
有没有什么规律？

过路人

我本来想以7=2+5=1+1+5=3+4=1+2+4=1+1+1+4=......这种方式来排的，排了一些发现方法不对，一是种类太多，二是容易遗漏。看了马版主给的链接中的解，发现确实很巧妙。下面是我读后的理解：

此主题相关图片如下：
　

老杨

这里所说的怨言数，其实就是大学一年级的“线性代数”中排列的“逆序数”。

日本竞赛题目是用找规律的方法得到答案。

我再把它的意思说说：

当有3个人排列,对应于逆序数分别是0、1、2……时，其不同排列的个数如下：
1    1
     1    1
+         1    1
------------------
1    2    2    1
=========================================================================================
当有4个人排列,对应于逆序数分别是0、1、2……时，其不同排列的个数如下：
1    2    2    1
     1    2    2    1
          1    2    2    1
+              1    2    2    1
---------------------------------
1    3    5    6    5    3    1
=========================================================================================
当有5个人排列,对应于逆序数分别是0、1、2……时，其不同排列的个数如下：
1    3    5    6    5    3    1
     1    3    5    6    5    3    1
          1    3    5    6    5    3    1
               1    3    5    6    5    3    1
+                   1    3    5    6    5    3    1
-----------------------------------------------------
1    4    9    15   20   22   20   15   9    4    1
=========================================================================================
当有6个人排列,对应于逆序数分别是0、1、2……时，其不同排列的个数如下：
1    4    9    15   20   22   20   15   9    4    1
     1    4    9    15   20   22   20   15   9    4    1
          1    4    9    15   20   22   20   15   9    4    1
               1    4    9    15   20   22   20   15   9    4    1
                    1    4    9    15   20   22   20   15   9    4    1
+                        1    4    9    15   20   22   20   15   9    4    1
------------------------------------------------------------------------------
1    5    14   29   49   71   90   101  101  90   71   49   29   14   5    1