0
競技数学解説
最小値の総和について
23
0
$$$$
こんにちは．今回は
$$\sum_{0\leq a_1,a_2,\ldots,a_m\leq n}\mathrm{min}\{a_1,a_2,\ldots ,a_m\}$$ について考えていきます．
正の整数 $m,n$ と $0$ 以上 $n$ 以下の整数組 $(a_1,a_2,\ldots,a_m)$ について，$k$ を $n$ 以下の非負整数とし，$\mathrm{min}\{a_1,a_2,\ldots ,a_m\}=k$ となるような整数組 $(a_1,a_2,\ldots,a_m)$ の個数は $(n-k+1)^m-(n-k)^m$ 個である．
理由
条件を満たす整数組は $k \leq a_1,a_2,\ldots,a_m \leq n$ を満たす組から $k+1 \leq a_1,a_2,\ldots,a_m \leq n$ を満たす組の個数を除いたものである．
したがって
$$\begin{aligned} \sum_{0\leq a_1,a_2,\ldots,a_m\leq n}\mathrm{min}\{a_1,a_2,\ldots ,a_m\}&=\sum_{k=0}^{n} k\left\{(n-k+1)^m-(n-k)^m \right\} \\ &=\sum_{k=0}^{n} \left\{(k-1)(n-k+1)^m-k(n-k)^m \right\}+\sum_{k=0}^{n}(n-k+1)^m \end{aligned}$$
$$ \sum_{k=0}^{n} \left\{(k-1)(n-k+1)^m-k(n-k)^m \right\}= -(n+1)^m$$
理由
$f(k)=(k-1)(n-k+1)^{m}$ とすると求めたい総和は $\displaystyle \sum_{k=0}^{n} \{f(k)-f(k+1)\}$ より，所謂，望遠鏡和を用いれば総和は $$f(n+1)-f(0)= -(n+1)^m$$
であるから，
$$\begin{aligned} \sum_{0\leq a_1,a_2,\ldots,a_m\leq n}\mathrm{min}\{a_1,a_2,\ldots ,a_m\}&=\sum_{k=0}^{n} \left\{(k-1)(n-k+1)^m-k(n-k)^m \right\}+\sum_{k=0}^{n}(n-k+1)^m \\ &= -(n+1)^m+\sum_{k=0}^{n}(n-k+1)^m\\ &= \sum_{k=1}^{n}(n-k+1)^m \\ &= \sum_{k=1}^n k^m \end{aligned}$$
よって結論として以下が得られました．
$$ \sum_{0\leq a_1,a_2,\ldots,a_m\leq n}\mathrm{min}\{a_1,a_2,\ldots ,a_m\}=\sum_{k=1}^{n}k^m$$
かなり綺麗な式になりました．嬉しい．
投稿日：7日前
この記事を高評価した人
この記事を高評価した人
高評価したユーザはいません
この記事に送られたバッジ
この記事に送られたバッジ
バッジはありません。
投稿者
投稿者
よね
10
5691
コメント
コメント
他の人のコメント
コメントはありません。
読み込み中...
読み込み中
