记PAT一道找规律题

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 416 阅读时长 ≈ 1 分钟

刷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)\)次，求和即可。