Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.


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 ).$

share|improve this question
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. –  Philippe Nadeau 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. –  Martin Rubey May 25 '12 at 11:03
@martin: yes, I don't even know a bijection if there is only one black square. –  Johann Cigler 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? –  Will Sawin May 29 '12 at 18:48
add comment

1 Answer

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$

share|improve this answer
Sorry, I did not understand Proposition B. Can you sketch this procedure with a typical example? –  Johann Cigler May 31 '12 at 10:24
I expanded a bit. Is it better? –  Gjergji Zaimi 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). –  Johann Cigler 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). –  Gjergji Zaimi 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? –  Johann Cigler Jun 1 '12 at 10:11
show 4 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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