Blokovat chůzi - Block walking

v kombinatorická matematika, blokovat chůzi je metoda užitečná při grafickém uvažování o součtech kombinací jako o „procházkách“ Pascalův trojúhelník. Jak název napovídá, problémy s blokováním chůze zahrnují počítání počtu způsobů, jakými může jednotlivec chodit z jednoho rohu A městského bloku do jiného rohu B jiného městského bloku vzhledem k omezením počtu bloků, kterými může osoba kráčet, podle pokynů, které má osoba může cestovat, vzdálenost z A do B atd.

Příklad problému s chůzí

Předpokládejme, že takový jedinec, řekněme „Fred“, musí chodit přesně k bloky, abyste se dostali do bodu B, který je přesně k bloky od A. Je vhodné považovat Fredův výchozí bod A za původ, ${ displaystyle (0,0)}$, a obdélníkové pole z mřížové body a B jako nějaký mřížkový bod ${ displaystyle (e, n)}$, e jednotky "východ" a n jednotky "severně" od A, kde ${ displaystyle e + n = k}$ a obojí ${ displaystyle e}$ a ${ displaystyle n}$ jsou negativní.

Řešení hrubou silou

A "hrubou silou" řešení tohoto problému lze dosáhnout systematickým počítáním počtu způsobů, jakými může Fred dosáhnout každého bodu ${ displaystyle X = (x_ {1}, x_ {2})}$ kde

${ displaystyle 0 leq x_ {1} leq e}$ a ${ displaystyle 0 leq x_ {2} leq n}$

bez zpětného sledování (tj. pouze cestování na sever nebo na východ z jednoho bodu do druhého), dokud není pozorován vzorec. Například počet způsobů, kterými se Fred mohl vydat ${ displaystyle (0,0)}$ na ${ displaystyle (1,0)}$ nebo (0,1) je přesně jedna; až (1,1) jsou dva; až (2,0) nebo (0,2) je jedna; až (1,2) nebo (2,1) jsou tři; a tak dále. Ve skutečnosti můžete získat počet způsobů, jak se dostat do konkrétního bodu, sečtením počtu způsobů, jak se můžete dostat do bodu jižně od něj, a počtu způsobů, jak se dostat do bodu na západ od něj. (S počátečním bod je nula a všechny body přímo na sever a na jih jeden.) Obecně jeden brzy zjistí, že počet cest od A k libovolnému takovému X odpovídá vstupu Pascalův trojúhelník.

Kombinatorické řešení

Protože problém zahrnuje počítání konečného, ​​diskrétního počtu cest mezi mřížovými body, je rozumné předpokládat a kombinatorické řešení k problému existuje. Za tímto účelem si povšimneme, že Fred musí být stále na cestě, která ho přivede z bodu A do bodu B. ${ displaystyle k}$ bloků, v každém bodě X musí buď cestovat po jednom z jednotkových vektorů <1,0> a <0,1>. Kvůli jasnosti dovolte ${ displaystyle E = langle 1,0 rangle}$ a ${ displaystyle N = langle 0,1 rangle}$. Vzhledem k souřadnicím B, bez ohledu na cestu, kterou Fred cestuje, musí kráčet po vektorech E a N přesně ${ displaystyle e}$ a ${ displaystyle n}$ krát. Jako takový se problém redukuje na zjištění počtu odlišných přeskupení slova

${ displaystyle overbrace {EE cdots E} ^ {e { text {times}}} underbrace {NN cdots N} _ {n { text {times}}}}$,

což odpovídá nalezení počtu způsobů, jak si vybrat ${ displaystyle e}$ nejasné předměty ze skupiny ${ displaystyle k}$. Celkový počet cest, které Fred mohl cestovat pouze z A do B, tedy mohl cestovat ${ displaystyle k}$ bloků je

${ displaystyle { binom {k} {e}} = { binom {k} {n}} = { frac {k!} {e! n!}}.}$

Další problémy se známými kombinovanými důkazy blokové chůze

• To dokazuji

${ displaystyle sum _ {k = 0} ^ {n} {n zvolit k} ^ {2} = {2n zvolit n}}$

lze provést přímou aplikací blokové chůze.^[1]

Viz také

• Příhradová cesta

Reference