I'm going through a past exam, and this question popped up:


$3P_n = P_{n-2} + P_{n+2},\,n>2$

Where $\tilde{P}_j = \{\textrm{monomer-dimer pavings on a } 1\times j \textrm{ board}\}$ and $|\tilde{P}_{j}| = P_{j} = F_{j+1}$. My problem is: What set (call it $A$ such that $|A|=3$) do I use, such that:

$|A\times\tilde{P}_{n}| = |A||\tilde{P}_{n}| = 3P_n$? I could use [3], but a Bijection is far from obvious!

  • $\begingroup$ Is [3] a reference you forgot to copy? $\endgroup$ – Hendrik Jan Nov 8 '12 at 21:57
  • $\begingroup$ @Hendrik: No, $[n]$ is a common notation for $\{1,\dots,n\}$ in combinatorial contexts. $\endgroup$ – Brian M. Scott Nov 8 '12 at 22:48
  • $\begingroup$ You are right. Silly me. I understand $[n]$ that way, with variable $n$, but automatically read $[3]$ in a totally different way. Thanks. $\endgroup$ – Hendrik Jan Nov 8 '12 at 23:15

It seems curious to ask for a combinatorial proof of this relation, which is not obvious at all. However it follows easily from the recurrence: $$ P_{n+2}+P_{n-2}=P_{n+1}+P_n+P_{n-2}=(P_n+P_{n-1})+P_n+P_{n-2} = 3 P_n. $$ You can turn this into a bijection, but it is a bit artificial. Given a paving of either $1\times(n+2)$ or of $1\times(n-2)$, find a paving of $1\times n$ and a number $i\in\{1,2,3\}$ as follows. If the paving was of $1\times(n+2)$, and the last two squares form a sub-paving, then we get a paving of $1\times n$ by removing them, and set $i$ to the number of tiles ($1$ or $2$) used for the final two squares. We are left with the cases of a paving of $1\times(n+2)$ that ends with $(2,1)$ or any paving of $1\times(n-2)$; we set $i=3$ for those cases, and pave $1\times n$ by replacing the $(2,1)$ by $(1)$ in the former case or by adding a dimer $(2)$ in the latter case. One checks that for any given paving of $1\times n$ and $i\in\{1,2,3\}$ one uniquely reconstructs a paving of either $1\times(n+2)$ or of $1\times(n-2)$.

| cite | improve this answer | |
  • $\begingroup$ Thanks. I know what you mean about trying to form a combinatorial argument. $\endgroup$ – user8603 Nov 8 '12 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.