3
$\begingroup$

I have a conjecture, that the following holds for arbitrary integers $n$, $k$ such that $0\leq k \leq n$:

$$\sum_{a=0}^{n} \sum_{b=\max[0,a-(n-k)]}^{\min[k,a]} \sum_{c=\max[0,a-(n-k)]}^{\min[k,a]} a (n-a)!a!{k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c}=2^{n-1}nk!(n-k)!$$

So far, I haven't been able to find a counter-example or to prove it. I checked for many values of $n$ and $k$ numerically and I found that it is true for $n\leq 200$.

$\endgroup$
  • $\begingroup$ Sometimes these problems can be solved by counting the same thing two different ways. For example, from a set of $n$ objects, choose one object for a one-element subset. For the remaining $n-1$ objects, choose a subset. Then, label the elements of the $n$-element set and permute the first $k$ objects, then separately permute the final $n-k$ objects. That is what the final result gives you. Now, look at what you are summing up. Can you construct things that look like this some other way? Possibly adding up smaller sets of things? It looks like Inclusion/Exclusion to me. $\endgroup$ – InterstellarProbe Jul 10 at 15:19
  • $\begingroup$ Thanks for your comment. However, it is not quite clear for me how can I account for the alternating -1 factor for example. But I will try to come up with something. $\endgroup$ – BorisTheBlade007 Jul 11 at 8:32
  • $\begingroup$ The alternating -1 factor is precisely why I suggested Inclusion/Exclusion $\endgroup$ – InterstellarProbe Jul 11 at 13:37
1
$\begingroup$

Not an answer:

First, we can simplify the sums as follows: $$ \sum_{a=0}^{n} \sum_{b=\max[0,a-(n-k)]}^{\min[k,a]} \sum_{c=\max[0,a-(n-k)]}^{\min[k,a]} a (n-a)!a!{k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} \\= \\ \sum_{a=0}^{n} \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} a (n-a)!a!{k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} \\=\\ \sum_{a=0}^{n}a (n-a)!a! \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} {k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} \\=\\ n!\sum_{a=0}^{n}a {\binom n a}^{-1} \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} {k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} $$ Now let's look at the inner sums (I'm representing them as generating functions, that's why I add the variable $x$. Later on, we can evaluate the generating function at $x=1$): $$ \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} {k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} x^b x^c \\=\\ \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} \left((-1)^b {k\choose{b}} {n-k\choose{a-b}} x^b\right) \left((-1)^{c}{k\choose{c}}{n-k\choose{a-c}} x^c \right) \\=\\ \left(\sum_{b=0}^{\infty} (-1)^b {k\choose{b}} {n-k\choose{a-b}} x^b\right) \left(\sum_{c=0}^{\infty} (-1)^{c}{k\choose{c}}{n-k\choose{a-c}} x^c \right) \\=\\ \left(\sum_{b=0}^{\infty} (-1)^b {k\choose{b}} {n-k\choose{a-b}} x^b\right)^2 $$ We replace the inner sums by the easier formula: $$ n!\sum_{a=0}^{n}a {\binom n a}^{-1} \left(\sum_{b=0}^{\infty} (-1)^b {k\choose{b}} {n-k\choose{a-b}} x^b\right)^2 $$

This sum however is, up to the factor $a$, equal to the sum in this question.

As the formulas and the result are similar the chances are that one can use the idea of the answer in the linked question to arrive at a result, or alternatively transform the sum.

$\endgroup$
  • $\begingroup$ I think I proved it using the post that you linked. Should I write it down in my original post? Also I found a possibly copy-paste error in the answer from that post, how can I correct that? I suggested an edit but it gets rejected. Probably I shouldn't write this as a comment but I don't know how to do a correction if they reject my edit. $\endgroup$ – BorisTheBlade007 Jul 14 at 21:08
  • $\begingroup$ If they reject it, suggest the edit as a comment. If they're wrong, they'll approve and edit it themselves, otherwise a misunderstanding is cleared up. If you can use parts of my answer, write your answer and say it expands upon mine idea $\endgroup$ – Sudix Jul 14 at 21:23
  • $\begingroup$ The problem is that due to fact that I am a new user I cannot just add comments anywhere. Anyway I will write it down. Thanks. $\endgroup$ – BorisTheBlade007 Jul 14 at 21:25
1
$\begingroup$

Thanks to Sudix I found this answer that helped me find out the solution, which I will repeat here for the sake of completeness (I corrected one mistake in the expression for $a_{m,k}$).

So, first let us re-label the summation indices in the conjecture to coincide with the notation of the cited answer that we will use ($k\rightarrow m$, $a\rightarrow k$, $b\rightarrow r$ and note what Sudix also pointed out, that the the sums are summing the same thing, therefore it is squared):

$$\sum_{k=0}^{n} k {n\choose{m}}{n\choose{k}}^{-1} \left(\sum_{r=\max[0,k+m-n]}^{\min[m,k]} (-1)^{r} {m\choose{r}}{n-m\choose{k-r}}\right)^2=2^{n-1}n$$

The credit for this proof goes to Dan Carmon.

Let $V$ be the space of homogeneous polynomial of degree $n$ in 2 variable $x$ and $y$ and let $T$ be the linear map defined as: $T(p)(x,y)=p(x+y,x-y)$.

Now note that: $T^{2}(p)(x,y)=T(p)(x+y,x-y)=p((x+y)+(x-y)),(x+y)-(x-y))=p(2x,2y)=2^{n}p(x,y)$

Let $A$ be the matrix representation of the linear transformation $T$ with the base $\left \{ x^{n},x^{n-1}y,...,xy^{n-1},y^{n} \right.\left. \right \}$

$\sum_{k=0}^{n}a_{m,k}x^{n-k}y^{k}=T(x^{n-m}y^{m})=(x-y)^{m}(x+y)^{n-m}\\=\sum_{k=0}^{n}\sum_{r=max(0,k+m-n)}^{min(m,k)}(-1)^{r}\binom{m}{r}\binom{n-m}{k-r}x^{n-k}y^{k}$

We are getting closer to end because now we know that $a_{m,k}=\sum_{r=max(0,k+m-n)}^{min(m,k)}(-1)^{r}\binom{m}{r}\binom{n-m}{k-r}$

and with sum (some) manipulation $\binom{m}{r}\binom{n-m}{k-r}\binom{n}{m}=\frac{m!(n-m)!n!}{r!(m-r)!(k-r)!(n-m-k+r)!(m-n)!m!}\\=\frac{n!}{r!(m-r)!(k-r)!(n-m-k+r)!}=\frac{n!(n-k)!k!}{r!(m-r)!(k-r)!(n-m-k+r)!k!(n-k)!}=\binom{k}{r}\binom{n-k}{m-r}\binom{n}{k}$

So $\binom{n}{m}a_{m,k}=\binom{n}{k}a_{k,m}$

The identity we seek to prove is equivalent to $\sum_{k=0}^{n}\frac{\binom{n}{m}a_{m,k}^{2}}{\binom{n}{k}}=2^{n}$

but the last identity yield:

$\sum_{k=0}^{n}\frac{\binom{n}{m}a_{m,k}^{2}}{\binom{n}{k}}=\sum_{k=0}^{n}a_{m,k}a_{k,m}=\left [ A^{2} \right ]_{m,m}=\left [ 2^{n} I\right ] _{m,m}=2^{n} $

$\blacksquare$

Note, that with the expression for $a_{m,k}$ we can rewrite what we have to prove:

$$\sum_{k=0}^{n} k {n\choose{m}}{n\choose{k}}^{-1} a_{m,k}^2=2^{n-1}n\tag{1}\label{1}$$

It is important to note that everything that has been said in the proof before stays valid. Therefore, using that $\binom{n}{m}a_{m,k}=\binom{n}{k}a_{k,m}$ we can write that $$\sum_{k=0}^{n} k {n\choose{m}}{n\choose{k}}^{-1} a_{m,k}^2=\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}\tag{2}\label{2}$$

Let us note, that

$$a_{m,k}a_{k,m}=a_{m,n-k}a_{n-k,m}\tag{3}\label{3}$$ (see proof below)

Consider the following identity (we are summing the very same thing going through the same indices just from the other direction) $$\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}=\sum_{k=0}^{n}(n-k) \,a_{m,n-k}a_{n-k,m}\tag{4}\label{4}$$

Using \eqref{3} we have that

$$\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}=\sum_{k=0}^{n}(n-k) \,a_{m,k}a_{k,m}\tag{5}\label{5}$$ $$2\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}=n\sum_{k=0}^{n} \,a_{m,k}a_{k,m}\tag{6}\label{6}$$ We know from the proof that $\sum_{k=0}^{n} \,a_{m,k}a_{k,m}=2^n$. Therefore, we have that $$\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}=n2^{n-1}$$ which is exactly what we wanted (see \eqref{2}).

Now let us prove \eqref{3}.

$$a_{m,k}=\sum_{r=max(0,k+m-n)}^{min(m,k)}(-1)^{r}\binom{m}{r}\binom{n-m}{k-r}\tag{7}\label{7}$$ $$a_{m,n-k}=\sum_{r=max(0,m-k)}^{min(m,n-k)}(-1)^{r}\binom{m}{r}\binom{n-m}{n-k-r}=\sum_{r=max(0,m-k)}^{min(m,n-k)}(-1)^{r}\binom{m}{m-r}\binom{n-m}{k+r-m}$$

Now if we introduce $s=m-r$ and we take care of the limits we get \eqref{7} and an extra $(-1)^m$ factor, that is $a_{m,k}=(-1)^m a_{m,n-k}$. It is easy to check that also $a_{k,m}=(-1)^m a_{n-k,m}$. Therefore, $$a_{m,k}a_{k,m}=(-1)^{2m} a_{m,n-k}a_{n-k,m}=a_{m,n-k}a_{n-k,m}$$.

Thank you for all your help! A nice combinatorical solution as InterstellarProbe suggested would still be desirable though.

$\endgroup$

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.