@Carl Love

Thanks for the discovery of an analogy with the structures of polyominoes. Of course, if we have a description of all polyominoes of given type (fixed area) in terms of the coordinates of the vertices of the corresponding polygon, we can calculate it's areas through the coordinates of the vertices (by Area procedure) and to select the desired polygons.
I usually place the pictures on the website radical.ru and then use green tree in the corner to give the link.

@Markiyan Hirnyk

You are right. The main idea of ​​the solution is the same as in the topic  http://www.mapleprimes.com/questions/142492-How-Many-Routes-In-A-4x4-Square#comment142513  . Very useful formula for calculating the area of ​​a simple polygon (not self-intersecting) by the coordinates of its vertices  ( Area  procedure). In addition to reducing the amount of computations, I ultimately narrowed down the search area. It is easy to prove that any simple polygon bounded  N  matches can be placed in a polygon with vertices  (0, 0),  (n, 0),  (n, 1),  (m, n),  (0, m) , where  n=(N-2)/2  and  m=floor((n+1)/2) .

@Markiyan Hirnyk 

Thanks for the marked discrepancy. This happens when there is only one variant as in your example  N=10, S=6 .

Replace the lines

T1:=Categorize(f, T0);

T:=[seq(T1[i,1], i=1..nops([T1]))]:

by

T1:=[Categorize(f, T0)];

T:=[seq(T1[i,1], i=1..nops(T1))]:

 Now the procedure is working correctly in all cases.  As for visualization, the code for it is an particular case, and it  is written for N=12, S=6 only (here there are 35 variants).

@Markiyan Hirnyk 

In the example, replace  Polygon  into  Polygons . I found no link to edit my post. 

PS. Link found and the bug was fixed. 

for the detected error and improving of the algorithm! After correcting my code, I got the same result. Now there are no duplicates:

Routes(4, 6);
nops({op(T)});

      68272

      68272

for the detected error and improving of the algorithm! After correcting my code, I got the same result. Now there are no duplicates:

Routes(4, 6);
nops({op(T)});

      68272

      68272

Check the specification of your equation!

You also did not answer these questions: "What means your dual equality? The system of equations?"

Check the specification of your equation!

You also did not answer these questions: "What means your dual equality? The system of equations?"

Your code does not work, if the list  r  contains several  elements with the same maximum frequency:

r := [3, 3, 3, 3, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 4, 3, 1$13];

with(Statistics):

T := Tally(r);

lhs(op(select(c-> is(rhs(c) = max(map(rhs, T))), T)));

       r := [3, 3, 3, 3, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

                                            T := [1 = 13, 2 = 1, 3 = 13, 4 = 4]

Error, invalid input: lhs expects 1 argument, but received 2

Your code does not work, if the list  r  contains several  elements with the same maximum frequency:

r := [3, 3, 3, 3, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 4, 3, 1$13];

with(Statistics):

T := Tally(r);

lhs(op(select(c-> is(rhs(c) = max(map(rhs, T))), T)));

       r := [3, 3, 3, 3, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

                                            T := [1 = 13, 2 = 1, 3 = 13, 4 = 4]

Error, invalid input: lhs expects 1 argument, but received 2

@Markiyan Hirnyk 

When I add a new vertex to the already created route, I always check that the new vertex is not the same as the previous vertices of this route (in this fragment of the code):

if convert([seq(r[i]<>p, i=1..k-1)], `and`) then M:=[op(M),[op(r), p]]:  fi:

@Markiyan Hirnyk 

When I add a new vertex to the already created route, I always check that the new vertex is not the same as the previous vertices of this route (in this fragment of the code):

if convert([seq(r[i]<>p, i=1..k-1)], `and`) then M:=[op(M),[op(r), p]]:  fi:

@Markiyan Hirnyk

The subprocedure  Rule  is of fundamental importance in procedure  Routes. It allows you to extend the already created list of routes  K   one more step. Applying  Rule  to the list of all the vertices  L , we get a list of all routes of length 1. Applying the procedure  Rule  to the previous list, we get all routes of length 2, and so on.

@Markiyan Hirnyk

The subprocedure  Rule  is of fundamental importance in procedure  Routes. It allows you to extend the already created list of routes  K   one more step. Applying  Rule  to the list of all the vertices  L , we get a list of all routes of length 1. Applying the procedure  Rule  to the previous list, we get all routes of length 2, and so on.

nops(L1)  means the number of elements of the list  L1 . 

Fragment of the code

for i from 1 to n do

U[1, i]:=L1[i]; U[2, i]:=L2[i]; U[i, 1]:=M1[i]; U[i, 2]:=M2[i];

od;

 specifies the first two lines and columns of the matrix  U .

nops(L1)  means the number of elements of the list  L1 . 

Fragment of the code

for i from 1 to n do

U[1, i]:=L1[i]; U[2, i]:=L2[i]; U[i, 1]:=M1[i]; U[i, 2]:=M2[i];

od;

 specifies the first two lines and columns of the matrix  U .