Block_walking
選挙で有権者に会うことについては、戸別訪問を参照してください では、組み合わせ数学、ブロックウォーキングはグラフィカルに「歩く」などの組み合わせの合計を考えるにおける有用な方法であるパスカルの三角形。名前が示すように、街区の問題は、人が歩くことができる街区の数、人の方向に制限がある場合、個人が街区の1つのコーナーAから別の街区の別のコーナーBまで歩くことができる方法の数を数えることを含みます移動する可能性があります、AからBまでの距離など。
コンテンツ
1 ブロックウォーキングの問題の例
1.1 力ずくによる解決 1.2 組み合わせソリューション
2 既知のブロックウォーキングの組み合わせ論的証明に関するその他の問題
3 も参照してください
4 参考文献
ブロックウォーキングの問題の例
まさに歩く必要があり、そのような個人は、「フレッド」と言ったとkの正確さの点Bに到達するためにブロックをk個のそれのようにFredの始点Aを考えるのが便利であるA.からブロックを起源、（（ 0 0 ）。 { displaystyle（0，0）}
、格子点の長方形配列といくつかの格子点としてのB（（ e
、 ）。
{ displaystyle（e、n）}
、Aのeユニット「東」およびnユニット「北」、ここで e + = k {e + n = k}
と両方 e {e}
と {n}
非負です。
力ずくによる解決
「ブルートフォース」この問題に対する解決策は、系統的フレッドが各点に達することができる方法の数をカウントすることによって得ることができます =（（ 1
、 2）。
{X =（x_ {1}、x_ {2}）}
どこ 0 ≤ 1≤ e
{0 leq x_ {1} leq e}
と 0 ≤ 2
≤ {0 leq x_ {2} leq n}
パターンが観察されるまで、バックトラックなしで（つまり、あるポイントから別のポイントに北または東に移動するだけ）。たとえば、フレッドが行くことができる方法の数（（ 0 0 ）。 { displaystyle（0，0）}
に（（ 1 0 ）。 { displaystyle（1，0）}
または（0，1）は正確に1つです。to（1，1）は2です。to（2，0）または（0，2）は1です。（1，2）または（2，1）は3です。等々。実際には、特定のポイントに到達する方法の数を、そのポイントの南のポイントに到達できる方法の数と、そのポイントの西のポイントに到達できる方法の数を合計することによって受け取ることができます。ポイントはゼロであり、そのすぐ北と南にあるすべてのポイントは1です。）一般に、AからそのようなXへのパスの数は、パスカルの三角形のエントリに対応することがすぐにわかります。
組み合わせソリューション
この問題には、格子点間の有限の離散数のパスのカウントが含まれるため、問題の組み合わせ解が存在すると想定するのが妥当です。この目的に向けて、フレッドがまだAからBへと向かう道を進んでいることに注意して k {k}
ブロック、任意の点Xで、彼は単位ベクトル<1，0>および<0，1>のいずれかに沿って移動する必要がわかりやすくするために、E = ⟨ 1 0 ⟩
{E = langle 1，0 rangle}
と =⟨ 0 1 ⟩
{N = langle 0，1 rangle}
。Bの座標が与えられると、フレッドが移動するパスに関係なく、彼はベクトルEとNに正確に沿って歩く必要が e {e}
と {n}
それぞれ回。このように、問題は単語の明確な再配置の数を見つけることに還元されますE E ⋯
E⏞ e
タイムズ ⋯ ⏟ タイムズ
{ overbrace {EE cdots E} ^ {e { text {times}}} underbrace {NN cdots N} _ {n { text {times}}}}
、
これは、選択する方法の数を見つけることと同等です e {e}
のグループからの不明瞭なオブジェクト k {k}
。したがって、フレッドがAからBに移動できるパスの総数は、 k {k}
ブロックは （k e）。 = （（k
NS）。= k ！ e ！ ！ {{ binom {k} {e}} = { binom {k} {n}} = { frac {k！} {e！n！}}。}
既知のブロックウォーキングの組み合わせ論的証明に関するその他の問題
それを証明する
∑k =
0 （（NS
k）。2 = （（ 2 ）。
{ sum _ {k = 0} ^ {n} {n choice k} ^ {2} = {2n choice n}}
ブロックウォーキングの簡単なアプリケーションで行うことができます。
も参照してください
格子パス
参考文献
^ Lehoczky、SandorおよびRichardRusczyk。問題解決の芸術、第2巻。ページ231。”