Combinatorics: on the number of Celtic knots in an n × m frame Everybody has seen a Celtic knot like the ones below.
Mathematically speaking  a rectangular Celtic knot of size $(n, m)$ may be built as:
We draw the boundaries of a $2n \times 2m$ rectangle .
Then we draw some barriers, which are horizontal or vertical segments whose starting, ending and crossing points all have integer even-sum coordinates.
Let $K_{n, m}$ be the number of Celtic knots of size $(n, m)$, two knots that differ only by rotations and reflections are considered the same.
Of course $K_{0, 0} = 1$, $K_{1, 1} = 1$, $K_{n, m} = K_{m, n}$.
I have been able to calculate $K_{1, n}$, but failed to calculate $K_{2, 2}$.
Any idea?
Explanation of the examples:
In #8 the green barrier starts at point $(0, 2)$ whose sum is even, and ends at point $(4, 2)$ whose sum is even. The orange barrier starts at point $(1, 1)$ whose sum is even and ends at point $(3, 1)$ whose sum is even.
In #18 the green barrier starts at point $(1, 3)$ whose sum is even, and ends at point $(3, 3)$ whose sum is even. The orange barriers start at point $(3, 1)$ whose sum is even and ends at point $(3, 3)$ whose sum is even.
In the third example, the green and the red barriers cross each other at point $(2, 3)$ whose sum is odd, hence not valid.
The 21 $K_{2, 2}$ I know:

Examples of the construction:

Celtic knots:

 A: I can confirm your $K_{2,2}$ count and have a formula for the number of the number of Celtic knots without symmetry.
Call a point $(x,y)$ even if $x+y$ is even, similarly for odd.  Each $2 \times 2$ square with odd corners (such as the one bounded by $(1,0)$, $(1,2)$, $(3,0)$, $(3,2)$ in your examples diagram) can contain a vertical segment, a horizontal segment, or neither, but not both.  These squares are independent of one another in terms of the segments.  For $K_{2,2}$, there are four of these squares, so there are $3^4 = 81$ possible combinations of barriers without accounting for symmetry.  For general $K_{m,n}$, this quantity is $3^{mn-m-n}$.
In the $2 \times 2$ case, the 21 symmetry classes each have size 1, 2, 4, or 8 with the connection $$3\cdot1 + 3\cdot2 + 12 \cdot4 + 3\cdot8 = 81.$$  Computations for $K_{2,n}$ with $n \ge 3$ will have less symmetry (no 90 degree rotations or diagonal reflections), so I think symmetry class sizes are only 1, 2, or 4.

Edit: Actually, this is a classic Burnside's lemma kind of problem (a result known by many names).  For $K_{n,n}$ the symmetry group is the dihedral group of the square: identity, rotations through 90, 180, and 270 degrees, and 4 reflections, horizontal, vertical, the two diagonals.  The number of states fixed by the actions in the following computation are in that order:
$$ \frac{3^4 + 3^1 + 3^2 + 3^1 + 3^3 + 3^3 + 3^2 + 3^2}{8} = 21.$$
I think that approach gives $K_{3,3} = 67{,}257$.
For $m \ne n$, the symmetry group has four elements: identity, 180 degree rotation, and horizontal and vertical reflections.  For the next case I get
$$K_{2,3} = \frac{3^7 + 3^4 + 3^5 + 3^4}{4} = 648.$$
Looking towards a general $K_{2,n}$ formula, I think it breaks into cases for $n$ odd or even.  Next I get
$$K_{2,4} = \frac{3^{10} + 3^5 + 3^7 + 3^6}{4} = 15{,}552.$$
These two approaches should lead to formulas for all $K_{m,n}$ (I've worked something out for $K_{2,n}$, the general square and strictly rectangular cases shouldn't be too much harder, although they may again be modifications based on parity).
A: Thanks to Brian, I've been able to solve the general problem.
I wrote a 9-page document to explain it all, unfortunately I cannot upload it here, so I give you the final results (the formulas could be written with just one formula but it would be a lot more confusing)
Non Square Celtic Knot
$\begin{array} {|c|r|l|}\hline
n \text{ even} / m \text{ even} & K_{(n, m)} = & \dfrac{3^{2nm - (n+m)} + 3^\frac{2nm - (n+m)}{2} + 3^\frac{2nm - m}{2} + 3^\frac{2nm - n}{2}}{4} \\ \hline
n \text{ even} / m \text{ odd} & K_{(n, m)} = & \dfrac{ 3^{2nm - (n+m)}+ 3^\frac{2nm - (n+m)+1}{2} +  3^\frac{2nm - m -1}{2} + 3^\frac{2nm - n}{2}}{4} \\ \hline
n \text{ odd} / m \text{ even} & K_{(n, m)} = & \dfrac{3^{2nm - (n+m)} + 3^\frac{2nm - (n+m)+1}{2} + 3^\frac{2nm - m}{2} + 3^\frac{2nm - n - 1}{2}}{4} \\ \hline
n \text{ odd} / m \text{ odd} & K_{(n, m)} = & \dfrac{ 3^{2nm - (n+m)} + 3^\frac{2nm - (n+m)}{2} + 3^\frac{2nm - m -1}{2} + 3^\frac{2nm - n - 1}{2}}{4} \\ \hline
\end{array}$
Square Celtic Knots
$\begin{array} {|c|r|l|}\hline
\rule[-3ex]{0pt}{8ex}n \text{ even}  & K_{(n, n)} = & K_{(n, n)} = \dfrac{3^{2n^2 - 2n} + 2*3^\frac{n(n-1)} {2} + 3*3^{n(n-1)} + 2*3^\frac{2n^2-n} {2}}{8}     \\ \hline
\rule[-3ex]{0pt}{8ex}n \text{ odd}   & K_{(n, n)} = & K_{(n, n)} = \dfrac{ 3^{2n^2 - 2n} + 2*3^\frac{n(n-1)} {2} + 3*3^{n(n-1)} + 2*3^\frac{2n^2-n-1} {2} }{8} \\ \hline
\end{array}$
