Let $N^{(k)}_{a,b,c}$ be the number of possible unnumbered layouts of the last $k$ columns, given that there are $a$ numbers left to assign in the first row, $b$ in the second row, and $c$ in the third row. Given the rules (at least one number per column), you have the recursion
$$
\begin{eqnarray}
N^{(k)}_{a,b,c}&=&N^{(k-1)}_{a-1,b-1,c-1}+N^{(k-1)}_{a-1,b-1,c}+N^{(k-1)}_{a-1,b,c-1}+N^{(k-1)}_{a,b-1,c-1} + N^{(k-1)}_{a-1,b,c}+N^{(k-1)}_{a,b-1,c}+N^{(k-1)}_{a,b,c-1},
\end{eqnarray}
$$
with the boundary conditions that $N^{(0)}_{0,0,0}=1$ and $N^{(k)}_{a,b,c}=0$ unless all indices are between $0$ and $k$. You want to find $N^{(9)}_{5,5,5}$. The following Python function performs the calculation:
def N(a,b,c,k,cache={(0,0,0,0):1}):
if min(a,b,c)<0 or max(a,b,c)>k:
return 0
if not cache.has_key((a,b,c,k)):
val = N(a-1,b-1,c-1,k-1)
val += N(a-1,b-1,c,k-1) + N(a-1,b,c-1,k-1) + N(a,b-1,c-1,k-1)
val += N(a-1,b,c,k-1) + N(a,b-1,c,k-1) + N(a,b,c-1,k-1)
cache[(a,b,c,k)] = val
return cache[(a,b,c,k)]
N(5,5,5,9)
> 735210
The result is below the upper bound of ${{9}\choose{5}}^3=126^3=2000376$ obtained by allowing all-blank columns, as it should be.
For numbered layouts, the recursion is slightly different, because the number of ways to choose the numbers depends on the column. Here, let $m_k$ be the number of allowed numbers in the $k$-th column from the end: $m_1=11$, $m_9=9$, and $m_k=10$ otherwise. In a column with no blanks, there are ${m_k}\choose{3}$ ways to choose the numbers; with one blank, ${m_k}\choose{2}$; and with two blanks, $m_k$. The recursion is therefore
$$
\begin{eqnarray}
M^{(k)}_{a,b,c}&=&{{m_k}\choose{3}}M^{(k-1)}_{a-1,b-1,c-1}+ {{m_k}\choose{2}}\left(M^{(k-1)}_{a-1,b-1,c}+M^{(k-1)}_{a-1,b,c-1}+M^{(k-1)}_{a,b-1,c-1}\right) \\ && + m_k\left(M^{(k-1)}_{a-1,b,c}+M^{(k-1)}_{a,b-1,c}+M^{(k-1)}_{a,b,c-1}\right).
\end{eqnarray}
$$
Not unexpectedly, the result here is much larger:
$$
M^{(9)}_{5,5,5} = 3669688706217187500.
$$
As a sanity check on this result, one might consider the average branching factor for the $15$ numbers in an average unnumbered layout:
$$
\left(\frac{M^{(9)}_{5,5,5}}{N^{(9)}_{5,5,5}}\right)^{\frac{1}{15}} \approx 7.023.
$$
Since in a typical row (with $m_k=10$) the possible outcomes have average branching factors ${{10}\choose{3}}^{1/3}\approx 4.93$, ${{10}\choose{2}}^{1/2}\approx 6.71$, and $10$, this seems very reasonable.
Note that we can also enumerate the possible unnumbered layouts in an entirely different way, using inclusion-exclusion. The basic idea is to count all the ways of placing $5$ numbers in each of the three rows, then remove the cases with an all-blank column, then add back in the cases with two all-blank columns, and so on:
$$
\begin{eqnarray}
N^{(9)}_{5,5,5} &=& {{9}\choose{5}}^3 - {{9}\choose{1}}{{8}\choose{5}}^3 + {{9}\choose{2}}{{7}\choose{5}}^3 - {{9}\choose{3}}{{6}\choose{5}}^3 + {{9}\choose{4}} \\
&=& 735210,
\end{eqnarray}
$$
as above. This is an elegant solution to the unnumbered case, but I do not see a way to extend it to the numbered layouts.
This has a very straightforward answer using the Burnside lemma. With
$n$ rows, $m$ columns and $q$ possible values we simply compute the
cycle index of the cartesian product group ($S_n \times S_m$, consult
Harary and Palmer, Graphical Enumeration, section 4.3) and evaluate
it at $a[p]=q$ as we have $q$ possibilities for an assignment that is
constant on the cycle. The cycle index is easy too -- for two cycles
of length $p_1$ and $p_2$ that originate in a permutation $\alpha$
from $S_n$ and $\beta$ from $S_2$ the contribution is
$a[\mathrm{lcm}(p_1, p_2)]^{\gcd(p_1, p_2)}.$
We get for a $3\times3$ the following colorings of at most $q$ colors:
$$1, 36, 738, 8240, 57675, 289716, 1144836, 3780288,\ldots$$
which points us to OEIS A058001 where
these values are confirmed.
We get for a $4\times 4$ the following colorings of at most $q$ colors:
$$1, 317, 90492, 7880456, 270656150, 4947097821,
\\ 58002778967, 490172624992,\ldots$$
which points us to OEIS A058002 where
again these values are confirmed.
We get for a $5\times 5$ the following colorings of at most $q$ colors:
$$1, 5624, 64796982, 79846389608, 20834113243925, 1979525296377132,
\\ 93242242505023122, 2625154125717590496,\ldots$$
which points us to OEIS A058003 where
here too these values are confirmed.
This was the Maple code.
with(combinat);
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_cycleind_symmNM :=
proc(n, m)
local indA, indB, res, termA, termB, varA, varB,
lenA, lenB, instA, instB, p, lcmv;
option remember;
if n=1 then
return pet_cycleind_symm(m);
else
indA := pet_cycleind_symm(n);
fi;
if m=1 then
return pet_cycleind_symm(n);
else
indB := pet_cycleind_symm(m);
fi;
res := 0;
for termA in indA do
for termB in indB do
p := 1;
for varA in indets(termA) do
lenA := op(1, varA);
instA := degree(termA, varA);
for varB in indets(termB) do
lenB := op(1, varB);
instB := degree(termB, varB);
lcmv := lcm(lenA, lenB);
p :=
p*a[lcmv]^(instA*instB*lenA*lenB/lcmv);
od;
od;
res := res + lcoeff(termA)*lcoeff(termB)*p;
od;
od;
res;
end;
mat_count :=
proc(n, m, q)
subs([seq(a[p]=q, p=1..n*m)],
pet_cycleind_symmNM(n, m));
end;
Addendum Nov 17 2018. Note that a product of powers of variables
implements the multiset of cycles concept through indets (distinct
elements) and degree (number of occurrences). Here we iterate
over pairs of monomials representing a conjugacy class from $Z(S_n)$
and $Z(S_m)$ and compute $a[\mathrm{lcm}(p_1, p_2)]^{\gcd(p_1, p_2)}$
for pairs of cycles $a_{p_1}$ and $a_{p_2}.$ This makes for the highly
compact algorithm shown above, which will produce e.g. for a three by
four,
$${\frac {{a_{{1}}}^{12}}{144}}+1/24\,{a_{{1}}}^{6}{a_{{2}}}^{3}
+1/18\,{a_{{1}}}^{3}{a_{{3}}}^{3}+1/12\,{a_{{2}}}^{6}
\\+1/6\,{a_{{4}}}^{3}+1/48\,{a_{{1}}}^{4}{a_{{2}}}^{4}
+1/8\,{a_{{2}}}^{5}{a_{{1}}}^{2}+1/6\,a_{{1}}a_{{2}}a_{{3}}a_{{6}}
\\+1/8\,{a_{{3}}}^{4}+1/12\,{a_{{3}}}^{2}a_{{6}}
+1/24\,{a_{{6}}}^{2}+1/12\,a_{{12}}.$$
Best Answer
I'm unsure what you mean by "the columns are always equally spaced".
If each row can have any number of columns, up to five, then perhaps the simplest thing to do is to find the number of layouts for a specific number of rows; then sum these quantities.
If there are $i$ rows, then there are $5^i$ different layouts.
For example, if there are two rows, then there are 5 choices for the number of columns in row 1 and 5 choices for the number of columns in row two; so there are $5^2$ layouts when you have two rows.
So, the total number of layouts is $$ 5 + 5^2+ 5^3+ 5^4+ 5^5+ 5^6. $$