Need help with a variation of the domino tiling 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:

Similar threads

Back
Top