记PAT一道找规律题
刷PAT准备机试的时候碰到的一道题,只用到一点排列组合的知识。
PAT_A1104
给定一个有限项的实数列\(A=\{a_1,a_2,...,a_n\}\),设\(B=\{a_{k_1},a_{k_2},...a_{k_m}\}\),其中\(m\le n\)。若\(k_1,...,k_m\)为\(m\)个相邻的整数,则称\(B\)是\(A\)的一个片段。一个数列中所有元素之和称为该数列的元素和。
证明:\(A\)的所有片段的元素和的总和为 \[\sum_{i=1}^n ia_i(n+1-i)\]
证明:考虑出现元素\(a_i\)的片段的数量。在\(a_1\)到\(a_i\)共\(i\)个元素中选一个作为片段的头,在\(a_i\)到\(a_n\)共\(n-i+1\)个元素中选一个作为片段的尾,这样的片段包含\(a_i\),根据乘法原理,一共有\(i*(n-i+1)\)个。所以元素\(a_i\)出现\(i*(n-i+1)\)次,求和即可。