Children face each other in two rows of $n$ people. The childern hold hands in different schemes. Count them (recurrence solution verification)

38 Views Asked by At

During preschool game, children face each other in two rows of $n$ people. Each child holds with its right hand:

  • the hand of the child opposite to them or
  • the hand of the neighbor to the right or
  • the hand of the child opposite the neighbor to the right.

An analogous rule applies to the left hand. No one shakes both hands to the same person.

Here is an example hand arrangement for two rows of $9$ children each:

enter image description here

Determine the number of possible hand arrangements. Formulate and justify the corresponding second-order homogeneous recursive equation with constant coefficients.


My solution:

I calculated manually the numbers of sequences for some of the initial values of $n$:

  • $a_1 = 0$, because $2$ children can't hold both hands

  • $a_2 = 2$, because we need to have a "wall" on the right and left sides, so we can have one of $2$ schemes:

    or

  • $a_3 = 4$, because we need to have a "wall" on the right and left sides, but we have 2 choices to make "inside" (for each of those $2$, as in $a_2$, we choose crossing or parallel hands), two of those $4$ schemes are:

    and

  • $a_4 = 8 + 4 = 12$, because as always, we need to have a "wall" on the right and left sides, but we have $3$ choices to make inside (crossing or parallel hands). This time, additionally we can make a "gap" in line of childern holding hands ($2$ gaps can't be placed one after another). If we place the "gap" in the middle, we get $2$ choices for the first and $2$ choices for the last place (crossing or parallel hands). Here is one of the schemes in that group:

  • $a_5 = 16 + 8 + 8 = 32$ , as always, we need to have a "wall" on the right and left sides and this time we have $4$ choices to make inside (crossing or parallel hands). We can make a "gap" on first possible place and get $2$ choices for other $3$ places (crossing or parallel hands). Alternativelly, if we place "gap" on the second possible place and get $2$ choices for for other $3$ places (crossing or parallel hands). Here is one of the schemes in that group:

To make all that more general - I think that each time we add $2$ more children (make the number of all children equal to $n$), we can choose:

  • one of $2$ schemes (crossing or parallel hands) for the newly created place, and copy all the former schemes on former places (when there were $n-1$ children)
  • one of $2$ schemes (crossing or parallel hands) for the newly created place, make a "gap" on the place that is last-but-one and copy all the former schemes on former places (when there were $n-2$ children)

Therefore I came up with a recursive equation: $a_n = 2a_{n-1} + 2a_{n-2}$. That works for the first $5$ values of $n$ that I've already calculated manually:

  • $a_1 = 0$
  • $a_2 = 2$
  • $a_3 = 2a_1 + 2a_2 = 2 \cdot 0 + 2 \cdot 2 = 4$
  • $a_4 = 2a_2 + 2a_3 = 2 \cdot 2 + 2 \cdot 4 = 12$
  • $a_5 = 2a_3 + 2a_4 = 2 \cdot 4 + 2 \cdot 12 = 32$

To calculate the general formula I did:

$$\lambda^2 - 2\lambda - 2 = 0 \iff (\lambda - (1 + \sqrt{3}))(\lambda - (1 - \sqrt{3})) = 0$$

So I get:

$$a_n = x(1 + \sqrt{3})^n + y(1 - \sqrt{3})^n$$

  • $a_1 = 0 = x(1 + \sqrt{3}) + y(1 - \sqrt{3}) \iff y = \frac{- x(1 + \sqrt{3})}{1 - \sqrt{3}}$
  • $a_2 = 2 = x(1 + \sqrt{3})^2 + y(1 - \sqrt{3})^2$

$$2 = x(1 + \sqrt{3})^2 + \frac{- x(1 + \sqrt{3})}{1 - \sqrt{3}} (1 - \sqrt{3})^2$$ $$2 = x(1 + \sqrt{3})^2 - x(1 + \sqrt{3}) (1 - \sqrt{3})$$ $$2 = x(4 + 2\sqrt{3}) + 2x$$ $$x = \frac{1}{3 + \sqrt{3}}$$

And from that: $$y = \frac{- \frac{1}{3 + \sqrt{3}} (1 + \sqrt{3})}{1 - \sqrt{3}}$$ $$y = - \frac{1 + \sqrt{3}}{(1 - \sqrt{3})(3 + \sqrt{3})}$$ $$y = \frac{1 + \sqrt{3}}{2\sqrt{3}} = \frac{\sqrt{3} + 3}{6}$$

So finally:

$$a_n = \frac{1}{3 + \sqrt{3}}(1 + \sqrt{3})^n + \frac{\sqrt{3} + 3}{6}(1 - \sqrt{3})^n$$

And that works for the first $3$ values of $a_n$ after $a_2$:

  • $a_3 = \frac{1}{3 + \sqrt{3}}(1 + \sqrt{3})^3 + \frac{\sqrt{3} + 3}{6}(1 - \sqrt{3})^3 = (...) = 4$
  • $a_4 = \frac{1}{3 + \sqrt{3}}(1 + \sqrt{3})^4 + \frac{\sqrt{3} + 3}{6}(1 - \sqrt{3})^4 = (...) = 12$
  • $a_5 = \frac{1}{3 + \sqrt{3}}(1 + \sqrt{3})^5 + \frac{\sqrt{3} + 3}{6}(1 - \sqrt{3})^5 = (...) = 32$

Is my solution correct or am I missing something?