# Lucky chance or combinatorial cause?

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}=\dots[n]/((\dots[k])\(\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 https://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 ).$

• Hmmm $a(n,k)$ is the total weight of configurations without black squares, as you probably noticed. But I see no easy way of extending this to the enumeration with black squares (although I don't believe in accidents); it is an interesting problem in any case. May 10 '12 at 11:50
• would you be happy with a weight preserving bijection from pairs (C without black squares, M a subset of {k+1,...,n-k}) to configurations with precisely |M| black squares? Note that your formula holds also with $b(n,k) = (1+zq^{k+1})\dots(1+zq^{n-k})$, whence the exponent of $z$ counts the number of black squares. May 25 '12 at 11:03
• @martin: yes, I don't even know a bijection if there is only one black square. May 25 '12 at 14:54
• If $|M|=n-k$ then presumably your bijection has to flip the configuration of dominoes upside down, then fill with black squares. If $|M|=0$ then presumably your bijection has to preserve the configuration. Is it possible to interpolate between these two? May 29 '12 at 18:48

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$

• Sorry, I did not understand Proposition B. Can you sketch this procedure with a typical example? May 31 '12 at 10:24
• I expanded a bit. Is it better? May 31 '12 at 18:33
• Excuse me, but I still have some difficulties. I am not familiar with partitions where some parts may be 0 and how in this case the transpose is defined. Both P and Q´ can have 0-parts but B(x,y) refers to partitions with positive parts. (BTW there seems to be a typo in the definition of Q). Jun 1 '12 at 8:34
• By transpose partition I mean just consider the rows as columns. See this page for an example mathworld.wolfram.com/ConjugatePartition.html B(x,y) does not necessarily need all parts positive (if it helps think of the partition as a lattice path joining two opposite corners of a rectangle, it's weight being the area above the path). Jun 1 '12 at 9:09
• Perhaps I have misunderstood some things. Consider e.g. the tiling bdwwdd . Here P=(2,2,0,0), Q=(6,4,2,1) and Q´=(2,1,0,0). What is meant by the transpose of Q´? What is R? Jun 1 '12 at 10:11