Блоковая ходьба

Информацию о встречах с избирателями на выборах см. в разделе «Агитация» .

В комбинаторной математике обход блоков — это метод, полезный для графического представления сумм комбинаций как «прогулок» по треугольнику Паскаля . Как следует из названия, задачи ходьбы по кварталам включают в себя подсчет количества способов, которыми человек может пройти от одного угла A городского квартала до другого угла B другого городского квартала с учетом ограничений на количество кварталов, которые человек может пройти, а также направления, в которых человек может пройти. может путешествовать, расстояние от А до Б и так далее.

Пример задачи ходьбы по блоку

Предположим, что такой человек, скажем «Фред», должен пройти ровно k блоков, чтобы добраться до точки B, которая находится ровно в k кварталах от A. Удобно рассматривать начальную точку A Фреда как начало ( 0,0 ) точки a. прямоугольный массив точек решетки и B как некоторая точка решетки $(e,n)$, e единиц «восток» и n единиц «север» от A, где $e+n=k$ и e и n неотрицательны.

Решение методом грубой силы

Решение этой проблемы « грубой силой » может быть получено путем систематического подсчета количества способов, которыми Фред может добраться до каждой точки. $X=(x_{1},x_{2})$ где

$0\leq x_{1}\leq e$ и $0\leq x_{2}\leq n$

без возврата (т.е. перемещаясь только на север или восток от одной точки к другой) до тех пор, пока не будет обнаружена закономерность. Например, количество способов, которыми Фред мог перейти от ( 0,0 ) к ( 1,0 ) или ( 0,1 ), равно одному; to ( 1,1 ) равно двум; to ( 2,0 ) или ( 0,2 ) равно единице; до ( 1,2 ) или ( 2,1 ) — три; и так далее. На самом деле, вы можете получить количество способов добраться до определенной точки, сложив количество способов добраться до точки к югу от нее и количество способов добраться до точки к западу от нее. точка равна нулю, а все точки, расположенные непосредственно к северу и югу от нее, равны единице.) В общем, вскоре обнаруживается, что количество путей от A до любого такого X соответствует входу в треугольник Паскаля .

Комбинаторное решение

Поскольку задача включает в себя подсчет конечного дискретного числа путей между точками решетки, разумно предположить, что существует комбинаторное решение этой проблемы. С этой целью заметим, что для того, чтобы Фред все еще находился на пути, который приведет его из A в B через k блоков, в любой точке X он должен либо двигаться по одному из единичных векторов ⟨1,0⟩ и ⟨0, 1⟩ . Для ясности позвольте $E=\langle 1,0\rangle$ и $N=\langle 0,1\rangle$. Учитывая координаты B, независимо от пути, по которому идет Фред, он должен пройти по векторам E и N ровно e и n раз соответственно. Таким образом, проблема сводится к нахождению количества различных перестановок слова.

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

что эквивалентно нахождению количества способов выбрать e нечетких объектов из группы k . Таким образом, общее количество путей, которые Фред мог бы пройти от A до B, пройдя только k блоков, равно

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

Другие проблемы с известными комбинаторными доказательствами обхода блоков

• Доказывая это

$\sum _{k=0}^{n}{n \choose k}^{2}\ ={2n \choose n}$

можно сделать с помощью простого применения ходьбы с блоком.

См. также

• Решетчатая дорожка