The number of fillings a prism with prisms
RADOVAN POTŮČEK
Department of Mathematics and Physics
University of Defence
Kounicova 65, 662 10 Brno
CZECH REPUBLIC
Abstract: This paper is inspired by very interesting YouTube video of Burkard Polster, professor of mathematics
at Monash University in Melbourne, Australia, which, among other things, concerned the number of ways to fill
a part of the plane with dominoes, i.e. rectangles. First we deal with the numbers of fillings the
prism with elementary prisms for . Special symbolism and figures showing the filling
of the prism are used as well as the concept of matching from graph theory and the corresponding graph diagrams.
Then we generalize these specific considerations and derive a general recurrence formula for any , which
expresses the number of fillings of the prism with elementary prisms, which in a way can
be considered as spatial domino cubes, if we do not consider their marking with pairs of numbers from 0 to 6.
Key-Words: prism filling, elementary prism, heuristic search, domino, recurrence formula, enumeration
Received: December 19, 2022. Revised: August 16, 2023. Accepted: September 11, 2023. Published: October 3, 2023.
1 Introduction
This article, inspired by YouTube video [8], was
written, among other reasons, because no article
concerning the number of fillings of a
prism with prisms was available on the
website even to the average reader, only mentions [2]
within the social question-and-answer website and
the article [3].
Domino tilling is still a very hot topic in
combinatorics and recreational mathematics – see
e.g. books [4] and [5] or e.g. papers [6], [7], [8], [9].
When filling a prism (box, brick),
which we will further briefly denote as the
prism, with elementary prisms, which we
will briefly call e-prisms, they can be oriented in
three directions – vertically, horizontally to the right
and horizontally up. These three types of e-prisms we
will briefly call v-prism, r-prism and u-prism.
For example, the filling of the prism in the
following figure:
Figure 1: One prism filling with six e-prisms.
we can represent as the table containing
appropriate of seven possible elements labelled by
the symbols and .
These symbols represent v-prism, two u-
prisms placed above each other in both horizontal
layers, two r-prisms placed above each other in
both horizontal layers, left part of a r-prism placed
in the upper layer above a u-prism, right part of a
r-prism placed in the upper layer above a u-prism,
lower part of a u-prism placed in the upper layer
above a r-prism and upper part of a u-prism
placed in the upper layer above a r-prism,
respectively.
So the filling shown in Figure 1 can be
represented as the following table:
Here and further on in the pictures, we will
distinguish the individual types of e-prisms by
colour: v-prisms in yellow, r-prisms in green and u-
prisms in light blue. Mostly, however, we will
represent a filling of the prism using a
table.
It is obvious that the number of v-prisms in the
prism must be an even number. Otherwise, it
would not be possible to fill the two remaining
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
104
Volume 3, 2023
horizontal layers formed by an odd number of unit
cubes with horizontal e-prisms.
If we rotated the prism by 90 degrees around
its axis passing perpendicular to the base, then
the previously u-prisms would become v-prisms, so
the number of u-prisms must also be an even number.
Moreover, since the volume of the prism is
always an even number, the number of r-prisms must
also be an even number.
Therefore, for example, for the prism there
are seven possible configurations describing
the numbers of pairs of prisms:
, , It is
clear that the remaining configuration does
not exist, because six r-prisms do not fill the
prism. Obviously, the configuration exists
only for the prism, where is even number.
Let denote the number of pairs of horizontal e-
prisms used. Then the number of remaining pairs of
v-prisms is . In the following text, we will use
the notation for the number of fillings of the
prism when using horizontal pairs of e-prisms
and the notation for the number of all filings of
the prism.
When determining the number of fillings of the
prism, we will first determine all possible
numbers of pairs of horizontal e-prisms and
subsequently for each such partial filling we will
determine the number of all possible fillings of
the prism.
2 The number of fillings of the
prism
It is clear that for the prism there are only two
configurations: and so
as is shown in the following figure:
Figure 2: The only two fillings of the prism.
These two fillings of the prism can of course
also be represented by these two tables:
If each of the four unit cube will represent a vertex
of the undirected graph
, where the
number of vertices
and the number of edges
, then we can represent both fillings using
two matchings, shown in the following figure:
Figure 3: Two matchings in the graph .
3 The number of fillings of the
prism
For the prism, there are six
configurations: , , , ,
and . Because the prism
contains unit cubes, then it can be filled with
at most four horizontal e-prisms. Therefore, the
number of pairs of horizontal e-prisms can take the
values . We will now analyse these three partial
cases.
▶ For , corresponding to the
configuration, there is only one filling of the
prism, namely with four v-prisms, represented by
table
so we have .
▶ For , corresponding to the and
configurations, there are four fillings of the
prism consisting of two fillings with one pair of
u-prisms and two fillings with one pair of r-prisms.
These four fillings are represented by the tables
so we have
.
▶ For , corresponding to the ,
and configurations, there are four fillings of
the prism: one with two pairs of u-prisms, two
with one pair of u-prisms and one pair of r-prisms and
one filling with two pairs of r-prisms as represented
by the following tables:
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
105
Volume 3, 2023
so we have .
We have thus derived that the total number of
fillings of the prism is
(2)
These nine fillings of the prism are
illustrated in Figure 4.
If each of the eight unit cube will represent a
vertex of the undirected graph
, where
and , then we can represent these
nine fillings using the following nine matchings
forming the vertex cover of the graph in Figure 5.
Figure 4: Nine fillings of the prism.
When displaying graphs with matchings, the unit
cubes in the top row and top layer will correspond to
the highest-placed vertex group, and the unit cubes in
the bottom row in the upper layer will correspond to
the lowest-placed vertex group. The vertices
corresponding to the unit cubes of the lower layer will
be placed in the middle.
Figure 5: Nine matchings in the graph .
The slanted edges apparently correspond to v-
prisms, the vertical edges correspond to u-prisms and
the horizontal edges correspond to r-prisms.
4 Case
For the prism, there are nine
configurations:
and (but
not ).
Because the prism contains
unit cubes, then it can be filled at most with 6
horizontal e-prisms. Therefore, the number of pairs
of horizontal e-prisms can take the values
▶ For , corresponding to the
configuration, there is only one filling of the
prism represented by table
so we have , in accordance with the remark
at the end of the first paragraph.
▶ For , corresponding to the and
configurations, there are four fillings of the
prism with one pair of r-prisms placed one
above the other.
There are also three fillings with one pair of u-
prisms placed one above the other, so we have
.
The following 2 × 3 tables represent these seven
fillings:
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
106
Volume 3, 2023
▶ The case corresponds to three
configurations: and
For the configuration there are three
fillings of the prism with two pairs of u-prisms
placed one above the other.
For the configuration there are four
fillings of the prism forming a cube
containing one pair of u-prisms and one pair of r-
prisms and four another L-shaped fillings consisting
of one pair of u-prisms and one pair of r-prisms.
For the configuration there are four
fillings of the prism with two pairs of r-prisms
forming a cube and also with two pairs of
r-prisms shifted by one unit cube from each other.
So we have fillings,
as represented by the following tables:
▶ For , corresponding to the ,
and configurations, there are a total of
fillings of the prism
with three pairs of horizontal e-prisms as represented
by the following tables:
We have thus derived that the total number of
fillings of the prism of the e-prisms is
(3)
In Figure 6 divided into two parts, 32 corresponding
pairings are shown.
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
107
Volume 3, 2023
Figure 6: Thirty-two matchings in the graph .
Note that the thirty-two graphs above with color-
coded matchings represent graphs
,
where
and .
5 The number of L-prism fillings
Before deriving the main result in the following part
of the article, we will define an L-prism and then
derive the numbers of filling the L-prism of the e-
prisms.
The hexagonal prism that for results from a
prism after removing one of its two v-
prisms or one of its two u-prisms located on the far
right, we will call L-prism of length and denoted by
So there are exactly four L-prisms that differ
from each other by a 90 degree rotation about an axis
passing perpendicular to the base. Four such L-
prisms without their specific e-prism fillings are
shown in the following figure:
Figure 7: Four L-prisms
The first of the L-prisms shown above, which is in
the shape of two steps of a staircase, we will call the
L-prism in the basic position and we will work with
it in the next explanation. We will use the notation
for the number of all fillings of the prism
in the basic position.
Apparently, we have , with the
prism filled by one u-prism. Now, we will determine
the numbers of fillings and then
for any .
▶ For there are 3 fillings of the prism, as
shown in the following figure:
Figure 8: Three fillings of the prism.
It is clear that the L-prism in the basic position is
always filled with an even number of v-prisms and
r-prisms and an odd number of u-prisms. Note that in
Figure 8 the right overhang is formed in two cases by
one u-prism and in one case by the right halves of two
r-prisms.
Let us denote such two types of L-prism by
the symbols and and the corresponding
filling numbers by the symbols and .
The number of fillings apparently
corresponds to the number of fillings the
prism, and the number of fillings
corresponds to the number of fillings the
prism.
So we get
(4)
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
108
Volume 3, 2023
▶ For there are the following 12 fillings of the
prism:
Figure 9: Twelve fillings of the prism.
The number of fillings apparently
corresponds to the number of fillings the
prism, and the number of fillings
corresponds to the number of fillings the
prism. So we have
(5)
▶ For , clearly there are
fillings of the prism of type and
fillings of the prism of type .
These two types of the prism fillings are shown
in the following figure:
Figure 10: Two types of the prism fillings.
So, in total, we get
(6)
fillings of the prism.
6 Case
Assume that we have a prism filled in some
way. For the prism, there can be three
possibilities for the number of placements of the right
halves of the r-prisms in the last 4th layer on the right.
This layer:
i) may not contain the right half of any r-prism,
ii) may contain the right halves of 2 adjacent r-
prisms,
iii) can be formed by the right halves of 4 r-prisms.
We will now analyse these three individual cases:
i) If the P(4) prism contains no right half of the r-
prism in the 4th layer on the right, then the first three
layers form a P(3) prism and the 4th layer itself on
the right forms a P(1) prism as shown in the
following figure:
Figure 11: prism without r-prisms in the 4th
layer on the right.
In this case, there are fillings of the
prism and fillings of the prism,
so, in total, there are fillings of
the prism in the considered configuration.
ii) If the prism contains the right halves of 2
adjacent r-prisms in the 4th layer on the right,
then it is formed by an L-prism and by the
complementary prism, formed by two r-prisms
as shown in Figure 12:
Figure 12: prism with 2 right halves of
adjacent r-prisms in the 4th layer on the right.
In this case, there are fillings of the
prism, which is in one of 4 possible positions as
shown in Figure 7, and only filling of the
specific prism. So, in total, for this considered
configuration, we have
fillings of the prism.
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
109
Volume 3, 2023
iii) If the prism contains the right halves of
4 r-prisms in the 4th layer on the right, then the first
two layers form a prism and the 3rd and 4th
layers are formed by 4 r-prisms as shown in the
following figure:
Figure 13: prism with 4 right halves of
r-prisms in the 4th layer on the right.
In this case, there are fillings of the
prism and only 1 filling of the prism
residue by 4 r-prisms. So we get
additional partial fillings of the prism.
In total we thus obtained
(7)
fillings of the prism.
Due to the above considerations, we can write
If we consider the representation of r-prisms in the
penultimate layer on the right side of the prism,
we also receive the result , as we will
now justify and derive.
i) If the prism does not contain any right half of
the r-prism in the penultimate layer, i.e. in the 3rd
layer on the right, then the first two layers on the left
form a prism and the remaining two layers on
the right form two prisms as shown in the
following figure:
Figure 14: prism without r-prisms in the 3th
layer on the right.
In this case, there are fillings of the
prism and fillings in each prism
so there are
fillings of the
prism in the considered configuration.
ii) If the prism contains two halves of 2 adjacent
r-prisms in the 3rd layer on the right, then these
2 r-prisms can be located either in the 2nd and 3rd
layers, or in the 3rd and 4th layers, as is shown in
Figure 15:
Figure 15: Two options for placing r-prisms in the
2nd and 3rd layers, or in the 3rd and 4th layers of
the prism.
In the first case shown in the figure above on the
left, given the four possible positions of two adja-
cent r-prisms, there are
ways of filling the prism.
In the second case shown in the figure above on
the right, given four possible positions of two
adjacent r-prisms, there are
ways of filling the prism.
In total we have
fillings
of the prism in the considered configuration.
iii) If the prism contains halves of 4 r-prisms in
the 3rd layer on the right, then these 4 r-prisms can
be located either in the 2nd and 3rd layers, or in the
3rd and 4th layers, or they can overlap with their
halves as is shown in Figure 16:
Figure 16: Three options for placing r-prisms in the
2nd and 3rd layers, or in the 3rd and 4th layers of
the prism, or the overlapping case.
In the first case shown in the figure above on the
left there are ways of filling
the prism.
In the second case shown in the figure above on
the right, given the four possible positions of two
adjacent r-prisms, there are ways of filling
the prism.
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
110
Volume 3, 2023
In the third case shown in the middle bottom
figure, given the four possible positions of two
adjacent r-prisms, there are
ways of filling the prism.
In total we have
fillings of the prism in the considered
configuration.
In total we thus obtained
(9)
fillings of the prism.
6 Case
Assume that we have a prism filled in some
way. For the prism, as for the prism, there
are three possibilities for the number of placements
of the right halves of the r-prisms in the last 5th layer
on the right.
i) If the prism contains no right half of the
r-prism in the 5th layer on the right, then the first four
layers form a prism and the 5th layer itself on
the right forms a prism:
Figure 17: prism without r-prisms in the 5th
layer on the right.
In this case, there are fillings of the
prism and fillings of the prism,
so, in total, there are fillings
of the prism in the considered configuration.
ii) If the prism contains the right halves of 2
adjacent r-prisms in the 5th layer on the right, then it
is formed by an L-prism and by the
complementary prism, formed by two r-prisms
as shown in Figure 18:
Figure 18: prism with 2 right halves of
adjacent r-prisms in the 5th layer on the right.
In this case, there are fillings of the
prism, which is in one of 4 possible positions,
and only 1 filling of the specific prism.
So, in total, for this considered configuration we have
fillings of the prism.
iii) If the prism contains the right halves of
4 r-prisms in the 5th layer on the right, then the first
three layers form a prism and the 4th and 5th
layers are formed by 4 r-prisms as shown in
Figure 19:
Figure 19: prism with 4 right halves of
r-prisms in the 5th layer on the right.
In this case, there are fillings of the
prism and only 1 filling of the prism
residue by 4 r-prisms. So we have
additional partial fillings of the prism.
In total we thus obtained
(10)
fillings of the prism.
Due to the above considerations, we can write
Since according to equation (1), we can
rewrite equations (8) and (11) in the form
and
After subtracting equation (12) from equation
(13), we get the equation
(14)
Since according to equation (6) we have
we can write ) in the form
.
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
111
Volume 3, 2023
i.e. in the recurrent form
(16)
After substituting the values into the right side of
the equation, we get that the number of fillings
prism is
which is consistent with result (10).
8 General case for
Equations (4), (5) and (6) contain a series of these
equalities:
.
.
We now generalize these equalities to the equality
Let us consider the following Figure 20
illustrating the prism, which contains the
and L-prisms, and derive the
difference between the filling numbers and
of these L-prisms.
Figure 19: prism containing and
prisms.
Assume that we have a prism filled in
some way. For the reasons stated in the three previous
paragraphs, when determining the number of fillings
of the L-prism , we will again consider three
cases for the number of placements of the right halves
of the r-prisms in the last th layer on the right.
i) If the prism contains no right half of the
r-prism in the th layer on the right, then the
first layers form a prism and the th
layer itself on the right forms a prism as shown
in the following figure:
Figure 20: prism without r-prisms in the
th layer on the right.
In this case, there are fillings of the
prism and fillings of the prism, so in
total there are fillings of the
prism in the considered configuration.
ii) If the prism contains the right halves of
2 adjacent r-prisms in the th layer on the
right, then it is formed by an L-prism and by the
complementary prism, formed by two r-prisms
as shown in Figure 21:
Figure 21: prism with two right halves of
adjacent r-prisms in the th layer on the right.
In this case, there are fillings of the
prism, which is in one of 4 possible positions, and
only filling of the specific prism. So
in total for this considered configuration we have
fillings of the
prism.
iii) If the prism contains the right halves of
4 r-prisms in the th layer on the right, then the
first layers form a prism and the th
and th layers are formed by 4 r-prisms as
shown in Figure 22:
Figure 22: prism with 4 right halves of
r-prisms in the th layer on the right.
In this case, there are fillings of the
prism and only 1 filling of the
prism residue by 4 r-prisms. Therefore, we have
additional
partial fillings of the prism.
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
112
Volume 3, 2023
Since we have
,
we get the equation
expressing the number of fillings of the
prism, whence
Analogously, we would derive the equation
After subtracting equation (21) from equation
(20), we get the equation
(22)
According to equation (18) we can equation (22) for
write in the form
.
If we rewrite this equation in recurrent form, we
obtain the main result of this paper:
Theorem 1. The number of fillings a
prism with prisms is for all
positive integer given by the recurrent
equation
,
(23)
Remark 1. The first 40 numbers of fillings a
prism with prisms were
calculated by using the following for statement
written by the programming language in the
computer algebra system Maple 2022. The results are
stated into Table 1.
a:=2: b:=9: c:=32:
for n from 4 to 40 do
d:=3*c+3*b-a: a:=b: b:= c: c:=d:
print("F(",n,")=",d);
end do;
Table 1: The values of for .
1
2
21
637815097922
2
9
22
2380358351281
3
32
23
8883618307200
4
121
24
33154114877521
5
450
25
123732841202882
6
1681
26
461777249934009
7
6272
27
1723376158533152
8
23409
28
6431727384198601
9
87362
29
24003533378261250
10
326041
30
89582406128846401
11
1216800
31
334326091137124352
12
4541161
32
1247721958419651009
13
16947842
33
4656561742541479682
14
63250209
34
17378525011746267721
15
236052992
35
64857538304443591200
16
880961761
36
242051628206028097081
17
3287794050
37
903348974519668797122
18
12270214441
38
3371344269872647091409
19
45793063712
39
12582028104970919568512
20
170902040409
40
46956768150011031182641
4 Conclusion
In this paper the numbers of fillings a
prism with prisms were
determined. The recurrence formula
,
for was derived.
The first 40 numbers F(n) were calculated by
using the programming language in the computer
algebra system Maple 2022. The obtained numerical
results correspond to the results [10] given at The On-
Line Encyclopedia of Integer Sequences.
Area of Further Development
The result in this paper can be generalized to the
number of fillings a prism with
prisms for arbitrary integer .
Acknowledgement:
This research work was supported by the Project for
the Development of the Organization „DZRO
Military autonomous and robotic systems“.
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
113
Volume 3, 2023
References:
[1] Mathloger, The ARCTIC CIRCLE THEOREM
or Why do physicists play dominoes? 2020.
www.youtube.com/watch?v=Yy7Q8IWNfHM
[2] Quora, In how many ways can you fit
sized dominoes into a domino of dimensions
, where is a variable? 2022.
https://www.quora.com/In-how-many-ways-
can-you-fit-1-X-1-X-2-sized-dominoes-into-a-
domino-of-dimensions-2-X-2-X-N-where-N-is-
a-variable
[3] Németh, L., Tillings of -board with
colored cubes and bricks. International Journal
of Mathematical Education in Science and
Technology. Vol. 51, No. 5, 2019, pp.786-798.
https://doi.org/10.1080/0020739X.2019.167692
7. https://arxiv.org/abs/1909.11729
[4] Björner, A., Stanley, R. P., A Combinatorial
Miscellany. L’Enseignement mathématique,
series Enseignement mathématique /
Monographie. No. 42. Geneva 2010. ISBN 978-
2-940264-09-4. https://math.mit.edu/
rstan/papers/comb.pdf
[5] Tulleken, H., Polynomies: Shapes and Tilings.
First published 2018, last modified 2022. 403
pp. https://www.researchgate.net/publication/
333296614Polyominoes
[6] Ardila, F., Stanley, R. P., Tilings. Based
on a Clay Public Lecture by the second
author at the IAS/Park City Mathematics
Institute in July 2004. 21 pp.
https://arxiv.org/abs/math/0501170v3
[7] Klarner, D. A., Pollack, J. B., Domino tilings of
rectangles with fixed width. Discrete
Mathematics, Vol. 32, Issue 1, 1980, pp. 45-52.
https://doi.org/10.1016/0012-365X(80)90098-9
[8] Mathar, R. J., Tilings of Rectangular Regions by
Rectangular Tiles: Counts Derived from
Transfer Matrices. 2014, 21 pp.
https://arxiv.org/abs/1406.7788v1
[9] Nabiyev, V., Pehlivan, H., A heuristic approach
to domino grid problem. Indian Journal of Pure
and Applied Mathematics, 2022, 14 pp.
https://doi.org/10.1007/s13226-022-00321-x
[10] Sloane, N. J. A., The On-Line Encyclopedia of
Integer Sequences. Number of perfect
matchings (or domino tilings) in C_4 X P_N,
2023. https://oeis.org/A006253
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
The author contributed in the present research, at all
stages from the formulation of the problem to the
final findings and solution.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
Conflict of Interest
The author has no conflict of interest to declare that
is relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
This research work was supported by the Project for
the Development of the Organization „DZRO
Military autonomous and robotic systems“.
EQUATIONS
DOI: 10.37394/232021.2023.3.12
Radovan Potůček
E-ISSN: 2732-9976
114
Volume 3, 2023
