3

多重総和記号を組み合わせ論的に考察する

1067
0

目次

  1. はじめに
  2. 問題
  3. 拡張
  4. 別解(2022/06/25追記)
  5. おわりに

1.はじめに

今回は通常では計算することができないような多重総和記号の式を組み合わせ論的に見ることで簡単に解く方法を皆さんにお伝えしていきたいと思います.必要な前提知識はほぼゼロです.

2.問題

多重総和記号

以下の式を計算せよ.

a1=14a2=1a1a15=1a14a15

シンプルな式ではありますが,地味に手が付けにくい問題です.こういった多重総和記号の式はお互いのシグマが絡み合っているので機械的に解く方法がありません.したがって,これほどにシンプルな問題も十分難しいのです.さらにただ単純に「組み合わせ論的に見る」というポイントだけではこの問題は解けません.これもこの問題を難しくしている要因でしょう.では,早速解いていきましょう!!

解説

fj(i)=a1=1ia2=1a1aj=1aj1aj
便宜上,上記のようにfj(i)を定義します.また,f1(i)=a1=1ia1とします.今回はf15(4)を求めれば良いのですね.まずは,シグマのせいでこの式がどんな式なのかとてもわかりにくいです.一旦簡単な状況でシグマをバラしてみましょう.

f1(4)=1+2+3+4f2(4)=(1)+(1+2)+(1+2+3)+(1+2+3+4)f3(4)={(1)}+{(1)+(1+2)}+{(1)+(1+2)+(1+2+3)}+{(1)+(1+2)+(1+2+3)+(1+2+3+4)}

なんだか法則性がある式ですね.例えば上の例では,こんなことが言えそうです.

f3(4)=f3(3)+f2(4)

これは定義から考えれば同様のことが全てのfに対して言えそうです.したがって,以下の補題が成立します.

2以上の任意の正整数i,jに対してfj(i)=fj1(i)+fj(i1)が成立する.

今回はこの補題を利用して解いていきます.ここで,表を考えてみましょう.

(๑╹ω╹๑ ) (๑╹ω╹๑ )

任意のjに対してfj(1)=1が成り立つことは容易にわかります.これと補題1を組み合わせて用いることで上のような表を書くことができます.表で言うと補題1は「あるマスの数はその左のマスと上のマスの和」と表現できます.さて,このような表に見覚えはありませんか?そうです.道順を数えるときに使うやつです!!

<参考:道順の数え上げ>
「下の図2において,地点Aから地点Bまで一度も引き返すことなく行く方法は何通りか?」
と言うような問題において頻出のテクニックです."ある地点に行く場合の数はその地点の下に行く場合の数と左に行く場合の数の和"という性質を利用してどんどん数字を書き込んで数え上げていく方法です.
これは主にnPr, nCrといった数え上げの記号を習っていない小学生が中学入試の際に使う手法として有名です.ですから,実際これらは7C3=35と計算することも可能です.
中学受験で頻出のアレ 中学受験で頻出のアレ

実は,図1の表はこの道順の数え上げと全く同じことをしているのです.図1の表に便宜上0行目と-1行目を追加すると見えやすいかと思います.

0,-1行目を追加した図1の表 0,-1行目を追加した図1の表

これより,fj(i)=(j+1)+(i1)Ci1であることがわかりますね.したがって今回求めるf4(15)=19C3=969となるわけです.

3.拡張

ほとんど「2.問題」で扱いましたが,今回の事実は一般の数に拡張することができますね。最後に公式のような形で表して終わりにしましょう.

多重総和記号の計算法則

任意の正整数n,mに対して以下が成立する.

a1=1na2=1a1am=1am1am=n+mCn1

まとめ

定義より,
a1=1n1a2=1a1am=1am1am=a1=1n1a2=1a1am=1am1am+a1=1na2=1a1am1=1am2am1
である.また,任意の正整数kに対し,a1=11a2=1a1ak=1ak1ak=1
である.これらより,求める式は原点から(n1,m+1)へ一度も引き返さずにいくような場合の数と等しい.したがって,()=n+mCn1である.題意は示された.

4.別解(2022/06/25追記)

二項係数で遊んでいたら別解を思いつきました.今回利用する公式は以下の通りです.

二項係数の関係式

n=kmnCk=m+1Ck+1

これを繰り返し適用するとどうなるでしょうか??以下ではとりあえずk=1として考えてみます.

公式2を繰り返し適用

a1=1na2=1a1am=1am1amC1=a1=1na2=1a1am1=1am2am1+1C2=a1=1nn+m1Cm=n+mCm+1=n+mCn1

nという数字を二項係数をnC1と捉えることで目的の式を得ることができました.ただしaCbにおいて,a<bであるときは0とします.

5.終わりに

今回の問題は組み合わせ論的に見ることで見通しよく計算できる問題でした.このような多重総和記号を含んだ計算をしなければならない場面が存在するのかわかりませんが,もしそのような機会があるなら使ってみてください!!(少なくとも僕は一度しか使ったことがありません.)

この記事は,新たに多重総和記号の計算法則が見つかれば随時追加していきたいと思います.一応,追加報告は twitter でしていきますのでもしよかったらチェックして行ってくださ〜い.拙く,長い記事でしたが最後まで見てくれてありがとうございました!!

投稿日:2022611
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

自己満足

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 目次
  2. 1.はじめに
  3. 2.問題
  4. 3.拡張
  5. 4.別解(2022/06/25追記)
  6. 5.終わりに