document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1210221>Question 1210221</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Find the number of paths from A to B in the grid below, where each step is down or to the right.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The grid is 3 by 3, with A in the upper-left and B in the lower-right. </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #851679 by </B><A HREF=/tutors/aboutme.mpl?userid=CPhill><B>CPhill(1959)</B></A><img src=\"/images/stars/stars-12.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=CPhill><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=CPhill><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=851679\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> You're asking for the number of paths from the top-left corner (A) to the bottom-right corner (B) of a 3x3 grid, where each step is either down or to the right.\r<BR>\n" );
document.write( "\n" );
document.write( "In a 3x3 grid, to get from A to B, you need to make a total of:<BR>\n" );
document.write( "* 3 steps to the right (R)<BR>\n" );
document.write( "* 3 steps down (D)\r<BR>\n" );
document.write( "\n" );
document.write( "Any valid path will consist of a sequence of these 6 steps (3 R's and 3 D's). The problem then becomes finding the number of distinct arrangements of these 6 steps.\r<BR>\n" );
document.write( "\n" );
document.write( "This is a combination problem. We have 6 total steps, and we need to choose 3 of them to be \"right\" steps (the remaining will be \"down\" steps). The number of ways to do this is given by the binomial coefficient:\r<BR>\n" );
document.write( "\n" );
document.write( "$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$\r<BR>\n" );
document.write( "\n" );
document.write( "Where:<BR>\n" );
document.write( "* $n$ is the total number of steps (6)<BR>\n" );
document.write( "* $k$ is the number of steps in one direction (either 3 right or 3 down)\r<BR>\n" );
document.write( "\n" );
document.write( "Let's calculate this:\r<BR>\n" );
document.write( "\n" );
document.write( "$$ \binom{6}{3} = \frac{6!}{3!(6-3)!} = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (3 \times 2 \times 1)} = \frac{720}{6 \times 6} = \frac{720}{36} = 20 $$\r<BR>\n" );
document.write( "\n" );
document.write( "Therefore, there are **20** different paths from A to B in the 3x3 grid following the given rules.\r<BR>\n" );
document.write( "\n" );
document.write( "**Answer:** There are **20** paths from A to B. </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );