Combinatorial proof of the identity relating Hurwitz numbers

64 Views Asked by At

Let define $H^{m}((n);\mu)$ count the number of tuples $(\alpha,\tau_1,\ldots,\tau_r ,\beta)$ in symmetric group $S_n$ where $\alpha$ is fixed cycle of type $(n)$ and $\beta$ cycle of type $\mu$ and

1) r = len($\mu$)-1 where len() imply length of partition.

2) $$\alpha \tau_1\ldots \tau_r =\beta$$

3) $\tau_i$ are transposition written as $(a_i , b_i)$ such that $$ b_1\leq b_2\leq\ldots \leq b_r. $$

Similarly, let's define $H^{sm}((n);\mu)$ to be the number of tuples $(\alpha,\tau_1,\ldots,\tau_r ,\beta)$ satisfying all the above condition except $3)$ which is replaced by

3') $\tau_i$ are transposition written as $(a_i , b_i)$ such that $$ b_1< b_2<\ldots <b_r. $$

Let us list few numbers $$H^{m}((2),2)=1,\, H^m ((2),(1,1))=1,\, H^m((3),(1,1,1))=2,\, H^m ((3),(2,1))=3,\, H^m ((4),(1,1,1,1))=5,\, H^m ((4),(2,1,1))=10 $$

$$H^{sm}((2),(1,1))=0,\, H^{sm}((2),(2))=1, H((3),(1,1,1))=1,\, H^{sm}((3),(1,1,1))=1,\, H^{sm}((3),(2,1))=3,\, H^{sm}((4),(2,1,1))=6 $$

Let us define two more objects which are the weighted sum of the numbers $H^{m}((n),\nu)$ and $H^{sm}((n),\mu)$ which will form main part of our questions.

$$H^{m}((n);x)=\sum_{\nu\vdash n}H^{m}((n);\nu)x^{-len(\nu)}. $$

$$H^{sm}((n);x)=\sum_{\nu\vdash n}H^{sm}((n);\nu)x^{-len(\nu)}. $$

We have proved the following equation

$$x^{n+1} H^{m}((n+1);x)= (x+1)^{n+1} H^{sm}((n);x+1) (*)$$

I made some following progress about the proof of () but still did not complete it. So if we expand both side of the equation () we get the following equation to be proven which is more combinatorial like.

Let $r$ be an fixed integer which vary from $0\ldots n$ $$\sum_{len(\nu)=r}H^m (n+1,\nu)=\sum_{\mu\vdash n }H^{sm}(n,\mu)\binom{n-len(\mu)}{n-(len(\nu)-1)} $$ Now we can give a map from LHS that is a tuples of montonic transposition of length $(len(\nu)-1)$ which when product with a fixed cycle of lenth $n+1$ gives a cylce of type $\nu$. For example

n=3

$$H^m (4,1^4) $$ tuples are given by $(12)(23)(34)$, $(23)(13)(34)$ etc

Now we want to form the strictly monotonic tuples out of it in $S_n$ so naturally, we delete all the tuples containing $(n+1)$ and given a series of tuples and given a tuples

$$(a_1,b_1) (a_2,b_2)\ldots(a_k,b_k)(a_{k+1},b_{k+1})\ldots(a_m,b_m)$$ we delete $(a_k,b_k)$ until its striclty monotonic.

For example

Now we want to make strictly monotonic tuples in $H^{sm} (3,1^3) $, $H^{sm} (3,(2,1))$, $H^{sm} (3,3)$ that is we take the tuple $(12)(23)(34)$ and delete $(34)$ we get strictly monotonic. For the tuple $(23)(13)(34)$ we delte $(34)$ and $(23)$ we get strictly monotonic.

I have checked for many cases of $n$ it holds true. it give a bijection Can't prove it in general so any help appreciated.