How many patterns of length 3?

Question

I asked another question that I guess is too hard to be answered, so I have to change the problem: how many patterns with length three we can draw on an android device?

Answer 1

For the solution of this problem, a clear definition of the pathways that are allowed and not allowed is necessary. I interpreted the question according to the following:

• we have to determine what is the number of all possible patterns characterized by three consecutive lines of total length 3, where "length 1" is defined as any line that directly connects two points without crossing another point. For example, calling 1,2,3 the three points in the upper horizontal row from left to right, 4,5,6 those in the middle row, and 7,8,9 those in the lower row, if I start from point 1, we have the following lines of "length 1": 1-2, 1-4, 1-5, 1-6, 1-8;

• we can have consecutive lines of length 1 that are aligned (e.g., the line 1-7 is considered of length 2, resulting from the sequence of lines of unitary length 1-4 and 4-7);

• the pattern can be "closed", that is to say that the initial and the final point can be the same (e.g., the path 1-4-2-1 is allowed);

• coming back over a line already drawn is not allowed (e.g., the path 1-2-1-4-5-3, albeit finally resulting of length 3, is not allowed);

• crossing between lines is allowed (e.g., the path 7-2-5-4 is allowed).

Based on these assumptions, the simplest way to solve this interesting problem is to divide the 9 points in 3 types: the 4 angles (we will call them A-points), the other 4 points placed in the middle of each side of the 3x3 square (M-points), and the central point (C-point).

Let us start by considering the second line of our pattern, which connects the second and the third point of our path with length 1. Consider the type of the second point:

• Case 1 - if it is one of the four A-points, it can be connected to another point by lines of unitary length in five ways (4 towards a M-point, 1 towards the C-point);

• Case 2 - if it is one of the four M-points, it can be connected in seven ways (4 towards an A-point, 2 towards a M-point, and 1 towards the C-point);

• Case 3 - lastly, if it is the C-point, it can be connected in eight ways (4 towards an A-point, 4 towards a M-point).

Now reconsider these possible connections, which refer to the second line of our path, by taking into account the first line. The first line can be of seven types: writing the two letters of the first and second point we have CA, MA (referring to case 1 of the list above); CM, AM, MM (referring to case 2); AC, MC (referring to case 3). In rewriting the possible second lines, we have to take into account that the first point of our path must be excluded from the possible endpoints of the second line. For example, let us consider the case of first line CA. There are clearly 4 possible first lines CA. In this case, among all possible second lines described in point 1 of the list above, we have to eliminate the connection from the A-point towards the C-point, so that there remain only 4 possible connections towards a M-point; thus we can write $4CA\rightarrow{4AM}$, indicating that each of the four possible first lines CA can continue only with 4 possible second lines AM. We can procede in the same way, by rewriting all possible second lines for each type of first line (and also counting the possibilities for that type of first line). The following scheme is obtained:

1.1 - There are 4 possible first lines CA. We have $4CA\rightarrow{4AM}$;

1.2 - There are 16 possible first lines MA. We have $16MA\rightarrow{3AM,1AC}$;

2.1 - There are 4 possible first lines CM. We have $4CM\rightarrow{4MA,2MM}$;

2.2 - There are 16 possible first lines AM. We have $16AM\rightarrow{3MA,2MM,1MC}$;

2.3 - There are 8 possible first lines MM. We have $8MM\rightarrow{4MA,1MM,1MC}$;

3.1 - There are 4 possible first lines AC. We have $4AC\rightarrow{3CA,4CM}$;

3.2 - There are 4 possible first lines MC. We have $4MC\rightarrow{4CA,3CM}$.

Following this scheme, it is not difficult to check that all possible sequences for the first two lines can be grouped in fifteen different types: 16 CAM, 48 MAM, 16 MAC, 16 CMA, 8 CMM, 48 AMA, 32 AMM, 16 AMC, 32 MMA, 8 MMM, 8 MMC, 12 ACA, 16 ACM, 16 MCA, 12 MCM.

Lastly, we have to consider the third line. Note that the last scheme, applied to count all possible second lines for each type of first line, can be "shifted" and also applied to count all possible third lines for each type of second line. This is because the first point of the path is now available for possible connections (we have predefined that closed paths are allowed) and therefore we have only to exclude the second point among the possible endpoints of the third line. For example, for the case CAM, where the first line is CA and the second line is AM, for the successive third line we have to consider the number of possible connections stated in point 2.2 above, because the second line is AM. Therefore we can write $16CAM\rightarrow{\times6}$. The scheme, grouped for each of the fifteen initial sequences above, then becomes:

• $16CAM\rightarrow{\times6}=96$;

• $48MAM\rightarrow{\times6}=288$;

• $16MAC\rightarrow{\times7}=112$;

• $16CMA\rightarrow{\times4}=64$;

• $8CMM\rightarrow{\times6}=48$;

• $48AMA\rightarrow{\times4}=192$;

• $32AMM\rightarrow{\times6}=192$;

• $16AMC\rightarrow{\times7}=112$;

• $32MMA\rightarrow{\times4}=128$;

• $8MMM\rightarrow{\times6}=64$;

• $8MMC\rightarrow{\times7}=56$;

• $12ACA\rightarrow{\times4}=48$;

• $16ACM\rightarrow{\times6}=96$;

• $16MCA\rightarrow{\times4}=64$.

• $12MCM\rightarrow{\times6}=72$;

The sum of these numbers gives the final answer of $1632$ total possibilities for a path of length 3.