Question

Consider an $n \times 1 - $rectangle where the $n$ squares are numbered $1$ to $n$. Cover this rectangle with white squares, black squares, and dominoes. To each covering of the rectangle associate the following weight: Each white square has weight 1, each black square at position $i$ and each domino at position ${(i,i + 1)}$ have weight $q^i.$ As usual the weight of a covering is the product of its components and the weight of a set of coverings is the sum of their weights. Then it is easy to verify that the weight $u(n,k)$ of all coverings with precisely $k$ dominoes is the product $u(n,k)=a(n,k)b(n,k)$ with $a(n,k)= {q^{k^2}}{n-k\brack k} $ and $b(n,k) = (1 + {q^{k + 1}})(1 + {q^{k + 2}}) \cdots (1 + {q^{n - k}}).$

Here ${n\brack k}=[1][2]\dots[n]/(([1]\dots[k])([1]\dots[n-k]))$ with $[n]=(1-q^n)/(1-q)$ denotes a $q-$binomial coefficient.

It is often claimed that there are no accidents in mathematics. Therefore my question is: Is there a simple combinatorial reason for the fact that $u(n,k)$ is the product of two terms with simple combinatorial interpretations or is it an accident after all?

Since this seems to be rather elementary I have posted this question in http://math.stackexchange.com/questions/142158/lucky-chance-or-combinatorial-cause but did not get an answer.

Edit

Some days ago Ilse Fischer has shown me a simple bijection. Associate with a tiling of an $n - $board with $k$ dominoes , $\ell $ black squares and $n - 2k - \ell $ white squares the word ${c_1}{c_2} \cdots {c_{n - k}}$ in the letters $w,b,d,$ where $d$ occurs $k$ times, $b$ occurs $\ell $ times and $w$ occurs $n - 2k - \ell $ times. Let $W({c_1}{c_2} \cdots {c_{n - k}})$ be the weight of the tiling.

First reverse in ${c_1}{c_2} \cdots {c_{n - k}}$ the order of the letters $b,d$ and obtain a word ${C_1}{C_2} \cdots {C_{n - k}}.$

Let e.g. $(n,k,\ell ) = (12,3,2)$ and ${c_1}{c_2} \cdots {c_9} = wbdwwdbwd.$ Then ${C_1}{C_2} \cdots {C_9} = wdbwwddwb.$

Then replace in ${C_1}{C_2} \cdots {C_{n - k}}$ all $b$ by $w.$ This gives a word $A$ with $k$ letters $d$ and $n - 2k$ letters $w.$ In our example we get $A = wdwwwddww.$

Then delete in ${C_1}{C_2} \cdots {C_{n - k}}$ all letters $d$ and get a word $B$ with $n - 2k$ letters $w,b.$ In our example $B = wbwwwb.$

Then $W({c_1}{c_2} \cdots {c_{n - k}}) = {q^{k\ell }}W(A)W(B).$

In our example we have $W({c_1}{c_2} \cdots {c_9}) = W(wbdwwdbwd) = {q^{2 + 3 + 7 + 9 + 11}} = {q^{32}},$ $W(A) = W(wdwwwddww) = {q^{2 + 7 + 9}} = {q^{18}},$ $W(B) = W(wbwwwb) = {q^{2 + 6}} = {q^8}.$

If $u(n,k,\ell )$ denotes the weighted enumeration of all tilings this implies $u(n,k,\ell ) = {q^{k\ell }}u(n,k,0)u(n - 2k,0,\ell ).$

Answer 1

Yes, there is a simple reason why this happens, but instead of giving the "magic" bijection, I will describe how to construct it. I will need to express this in the language of partitions, where I'm more familiar, although it shouldn't be hard to switch back to the dominoes interpretation. Below, I assume the weight of a partition of $n$ is $q^n$, and the weight of a pair of partitions is the product of their weights.

Proposition A: There is a weight preserving bijection between tilings of an $n\times 1$ rectangle with $k$ dominoes and $a$ black squares and pairs of partitions $(P,Q)$ where $P$ has $k+a$ parts each of size $\le n-2k-a$, and $Q$ has $k+a$ parts $q_1\geq q_2\geq \cdots \geq q_{k+a}=1$ and $q_{i}-q_{i+1}\in \lbrace 1,2\rbrace$, where these differences are $=2$ exactly $k$ or $k-1$ times.

Proof: Let $p_{k+a}$ denote the number of white squares before the first black square or domino, $p_{k+a-1}$ denote the number of white squares before the second black square or domino etc. We will let $P$ be the partition $p_1,p_{2},\dots$. We let $q_{k+a-i}-q_{k+a-i+1}=2$ if the $i$'th black square or domino is a domiono, and $q_{k+a-i}-q_{k+a-i+1}=1$ otherwise. It should be clear that this is a bijection. Proving that it is weight preserving is also easy and is left as an exercise.

Proposition B: The partitions $Q$ from the previous theorem are in a weight preserving bijection (up to a power of $q$ which depends only on $k$ and $a$) with partitions which have $k$ parts which are $\le a$.

Proof: Take the partition $Q$ and subtract the partition $(k+a,k+a-1,\dots,1)$, so we obtain $Q'=(q_1-k-a,q_2-k-a+1,\dots,q_{k+a}-1)$. Now let $\hat{Q}$ be the transpose partition of $Q'$. Check that $Q'$ has $k$ distinct parts which are $\in [0,k+a-1]$. Therefore we make a fourth partition $R=\hat{Q}-(k-1,\dots,1)$. Check that $R$ has $k$ parts which are $\le a$.

Now let's denote by $B(x,y)$ the set of partitions contained in an $x\times y$ rectangle (so partitions that have at most $x$ parts and each part is at most $y$). It is well known that the generating function for these is ${x+y\brack x}$.

Proposition C There is a weight preserving bijection between pairs of partitions $B(k+a,n-2k-a)\times B(k,a)$ and pairs of partitions $B(n-2k,k)\times B(n-2k-a,a)$.

Proof: Look up your favourite bijective proof of $${n-k \brack k+a}{k+a\brack a}={n-k\brack k}{n-2k\brack a}.$$ (Note that this is the part which messes things up a bit, so that the resulting final bijection won't be "obvious".)

So propositions A,B give a bijection between tilings with $k$ dominos and $a$ black squares and $B(k+a,n-2k-a)\times B(k,a)$. Applying proposition C, we get a bijection with $B(n-2k,k)\times B(n-2k-a,a)$. Finally since $B(n-2k,k)$ is in a weight preserving bijection (up to an inconsequential power of $q$) with domino tilings (no black squares) and $B(n-2k-a,a)$ is up to a power of $q$ the coefficient of $z^a$ in $(1+zq^{k+1})\cdots(1+zq^{n-k})$, we get the desired result. $\square$