Block walking

Block walking

In combinatorics, block walking is a method useful in thinking about sums of combinations graphically as "walks" on Pascal's triangle. As the name suggests, block walking problems involve counting the number of ways an individual can walk from one corner A of a city block to another corner B of another city block given restrictions on the number of blocks the person may walk, the directions the person may travel, the distance from A to B, et cetera.

An Example Block Walking Problem

Suppose such an individual, say "Fred", must walk exactly k blocks to get to a point B that is exactly k blocks from A. It is convenient to regard Fred's starting point A as the origin, (0,0), of a rectangular array of lattice points and B as some lattice point (e,n), e units "East" and n units "North" of A, where e+n=k and both e and n are nonnegative.

olution by Brute Force

A "brute force" solution to this problem may be obtained by systematically counting the number of ways Fred can reach each point X=(x_1,x_2) where:0 le x_{1} le e and 0 le x_{2} le nwithout backtracking (i.e. only traveling North or East from one point to another) until a pattern is observed. For example, the number of ways Fred could go from (0,0) to (1,0) or (0,1) is exactly one; to (1,1) is two; to (2,0) or (0,2) is one; to (1,2) or (2,1) is three; and so on. In general, one soon discovers that the number of paths from A to any such X corresponds to an entry of Pascal's Triangle.

Combinatorial Solution

Since the problem involves counting a finite, discrete number of paths between lattice points, it is reasonable to assume a combinatorial solution exists to the problem. Towards this end, we note that for Fred to still be on a path that will take him from A to B over k blocks, at any point X he must either travel along one of the unit vectors <1,0> and <0,1>. For the sake of clarity, let E=<1,0> and N=<0,1>. Given the coordinates of B, regardless of the path Fred travels he must walk along the vectors E and N exactly e and n times, respectively. As such, the problem reduces to finding the number of distinct rearrangements of the word: overbrace{ EE cdots E }^{e times}underbrace{ NN cdots N }_{n times},which is equivalent to finding the number of ways to choose e indistinct objects from a group of k. Thus the total number of paths Fred could take from A to B traveling only k blocks is:inom{k}{e}=inom{k}{n}=frac{k!}{e! n!}.

Other Problems with Known, Block Walking Combinatorial Proofs

* Proving that: sum_{k=0}^n { n choose k}^2 = { 2n choose n} can be done with a straightforward application of block walking. [Lehoczky, Sandor and Richard Rusczyk. "The Art of Problem Solving, Volume II". Page 231.]

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Block Island — Infobox Settlement official name = New Shoreham, Rhode Island settlement type = Town nickname = imagesize = image caption = image mapsize = map caption = mapsize1 = map caption1 = subdivision type = Country subdivision type1 = State subdivision… …   Wikipedia

  • Walking-Chair Design Studio — Das Walking Chair Design Studio ist ein von Karl Emilio Pircher (* 1963 in Bozen, Italien) und Fidel Peugeot (* 1969 in Basel, Schweiz) in Wien gegründetes, stark interdisziplinär ausgerichtetes Designstudio. Inhaltsverzeichnis 1 Profil 2… …   Deutsch Wikipedia

  • Block-Heads — Infobox Film name = Block Heads caption = Theatrical poster for Block Heads (1938) director = John G. Blystone producer = Hal Roach Jr. Hal Roach writer = Felix Adler Arnold Belgard Harry Langdon James Parrott Charley Rogers starring = Stan… …   Wikipedia

  • The Walking Dead — Infobox comic book title title = The Walking Dead caption =Cover art for The Walking Dead: Days Gone Bye trade paperback. Art by Tony Moore. schedule = Monthly ongoing = y publisher = Image Comics date=October 2003 Present issues = Zombie = y… …   Wikipedia

  • Fifty Dead Men Walking — Infobox Film name = Fifty Dead Men Walking caption = Advance Poster director = Kari Skogland producer = Kari Skogland Stephen Hegyes Peter La Terriere Shawn Williamson writer = Kari Skogland starring = Jim Sturgess Rose McGowan Ben Kingsley Kevin …   Wikipedia

  • Writer's block — is a phenomenon involving temporary loss of ability to begin or continue writing, usually due to lack of inspiration or creativity.Origins of writer s blockWriter s block can be closely related to depression and anxiety, [Flaherty, A. (2005). The …   Wikipedia

  • Jenny from the Block — Infobox Single Name = Jenny from the Block Caption = CD 1 cover Artist = Jennifer Lopez featuring Styles and Jadakiss Album = This Is Me... Then Released = August 2002 Format = CD single, 12 single Recorded = March 2002 at The Hit Factory (New… …   Wikipedia

  • My Block — On My Block Single by Scarface from the album The Fix B side G …   Wikipedia

  • Taft Brothers Block — Infobox nrhp | name =Taft Brothers Block nrhp type = caption = location= Uxbridge, Massachusetts lat degrees = 42 lat minutes = 4 lat seconds = 34 lat direction = N long degrees = 71 long minutes = 37 long seconds = 47 long direction = W locmapin …   Wikipedia

  • Down the Block There's a Riot — Episode no. Season 7 Episode 10 Directed by Larry Shaw Written by Bob Daily Original air date …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”