Need help with a variation of the domino tiling problem

In summary, the request pertains to a variation of the domino tiling problem, which involves covering a specific grid or area with domino pieces while adhering to certain constraints or rules. The individual seeks assistance in understanding or solving this variation, potentially requiring insights into the mathematical principles, algorithms, or strategies applicable to the problem.
  • #1
Ading
1
0
There are two questions I need some help with. They both involve a ‘honeycomb strip’ (which is just a hexagonal tessellation of two rows), ‘worker bees’ (which take up two hexagons), and larvae (which take up one hexagon).

How can we count the number of ways there are for worker bees and larvae to arrange themselves in an n-cell honeycomb strip? Explain.
Superstitious worker bees will only face up-right. How many ways are there for superstitious worker bees and larvae to arrange themselves in an n-cell honeycomb strip? Why?

attached is a screenshot of the question for clarity
[Mentor Note: Image uploaded from stackexchange is below]

This kind of reminded me of that famous domino tiling problem, so it appears that we need to use induction. I tried to build to recurrences: when n = 2k (An) and when n = 2k+1 (Bn). And I got something like An = Bn-1 + An-1 + An-2 + Bn-2 , and Bn = An + Bn-1 + An-1 + Bn-2 , but apparently that’s not right

Thank you to any answers in advanced!

tiling.jpg
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
Let us number low row cells as 1 3 5 7 9….and high row cells 2 4 6 8… from the left.
Bee blocks are (c_n c_n+1) , and (c_n c_n+1 c_n+2 ) where the middle c_n+1 is larvae. Each of them has 2 bee directions to distinguish. number of bees n_B
[tex]n_B=n_2+n_3[/tex]
, and number of lavaes is
[tex]n_3+N-2n_2-3n_3=N-2n_2-2n_3=N-2n_B[/tex]
where N is number of total cells with all occupied, n_2 is number of (c_n c_n+1) blocks, and n_3 is number of (c_n c_n+1 c_n+2 ) blocks. With N and n_B given the number of permutation is
[tex]2^{n_B} \sum_{n_2+n_3=n_B,\ N-2n_2-3n_3 \geq 0}\frac{(N-n_2-2n_3)!}{n_2!n_3!(N-2n_2-3n_3)!}[/tex]
[tex]=2^{n_B} \sum_{k=max(0,3n_B-N)}^{n_B} \frac{(N-2n_B+k)!}{k!(n_B-k)!(N-3n_B+k)!}[/tex]
 
Last edited:

FAQ: Need help with a variation of the domino tiling problem

What is the domino tiling problem?

The domino tiling problem involves determining whether a given region can be completely covered by dominoes, which are rectangular tiles that cover two adjacent squares. The problem can be mathematically formulated and has applications in combinatorics, computer science, and statistical physics.

How can I determine if a specific shape can be tiled with dominoes?

To determine if a specific shape can be tiled with dominoes, one approach is to analyze the parity of the squares. A necessary condition is that the number of squares of each color (in a checkerboard coloring) must be equal. If they are not, the shape cannot be tiled with dominoes.

What are some common variations of the domino tiling problem?

Common variations of the domino tiling problem include tiling with different types of tiles (e.g., L-shaped trominoes), considering constrained tiling where certain squares cannot be covered, and exploring tilings on different surfaces or in higher dimensions.

Are there efficient algorithms for solving domino tiling problems?

Yes, there are efficient algorithms for solving certain instances of the domino tiling problem. For example, the problem can be solved using dynamic programming or graph-theoretic methods, particularly when dealing with rectangular grids or specific shapes where the number of configurations can be systematically enumerated.

Where can I find resources or tools to help with domino tiling problems?

Resources for domino tiling problems can be found in combinatorial mathematics textbooks, online courses, and research papers. Additionally, programming libraries and software tools that focus on combinatorial optimization or tiling problems may offer practical implementations and visualizations to aid in understanding and solving these problems.

Similar threads

Back
Top