1
$\begingroup$

I have checked the following combinatorial identity for several cases and it seems to work. I would like to know if this is known or if there is a counter-example. Note, i is a given constant.

$$(i+d)\sum_{k\geq d} a_k\binom{k-d}{i} = \sum_{l=1}^{d} n_l \sum_{k\geq d} b_{k,l}\binom{k-d}{i}$$

$$a_k=| \{ (i_1,..,i_d) \in [n_1]\times...\times[n_d]:\sum_{j=1}^d i_j=k \}|$$

$$b_{k,l}=|\{(i_1,..i_{l-1},n_l,i_{i+1},..,i_d) \in [n_1]\times...\times[n_d]:\sum_{j=1}^d i_j=k\}|$$

I have been thinking about the left as some weighting on the compositions that come from cutting the space by a hyperplane. The right looks like some kind of weighted projection summation.

$\endgroup$
  • $\begingroup$ I don't understand the $i_l$ on the right hand side of the formula defining $b_{k,l}$. $\endgroup$ – darij grinberg Jul 21 '11 at 17:46
  • $\begingroup$ The $i_l$ would be $n_l$ in the $b_{k,l}$ case. $\endgroup$ – Sturgeon Jul 21 '11 at 18:38
1
$\begingroup$

So, given numbers $d, n_1,\dots,n_d\in \mathbb N$, we define the polynomial $$P(x)=\frac{1}{x^d}\prod_{i=1}^d (x+x^2+\cdots+x^{n_i})$$ so that ` $$\sum_{k\geq 0}a_k\frac{(k-d)!}{(k-d-i)!}=\frac{d^{i}}{dx^{i}}P(x)\bigg| _{x=1}$$ Similarly we have $$\sum_{k\geq 0}b_{k-n _l,l}\frac{(k-d)!}{(k-d-i)!}=\frac{d^{i}}{dx^{i}}\left(\frac{x^{n_l}P(x)}{x+x^2+\cdots+x^{n_l}}\right)\Bigg| _{x=1}$$ So if we denote $$Q(x)=\sum_{l=1}^d \frac{n_lx^{n_l}}{x+x^2+\cdots+x^{n_l}}$$ your identity becomes equivalent to $$(d+i)\frac{d^{i}}{dx^{i}}P(x)\bigg| _{x=1}=\frac{d^{i}}{dx^{i}}P(x)Q(x)\bigg| _{x=1}$$ Now simply notice the following logarithmic derivative $\frac{P'(x)}{P(x)}=\frac{Q(x)-d}{x-1}$ which implies $$\frac{d^{i}}{dx^{i}}P(x)Q(x)\bigg| _{x=1}=\frac{d^{i}}{dx^{i}}P'(x)(x-1)+dP(x)\bigg| _{x=1}$$ $$=d\frac{d^i}{dx^i}P(x)\bigg| _{x=1}+i\frac{d^{i-1}}{dx^{i-1}}P'(x)\bigg| _{x=1}=(d+i)\frac{d^i}{dx^i}P(x)\bigg| _{x=1}$$ which is what we wanted to prove.

$\endgroup$
0
$\begingroup$

I believe this can be proved combinatorially. Consider we are working in the $[n_1]\times ... \times [n_d]$ box. Consider attaching a variable to each coordinate. Then consider picking an $S=i_1*x_1,...,i_d*x_d$. Then pick a set $X$ consisting of monomials s.t. the coefficient on the monomials is less than the coefficients given in $S$, $S$ is a subset of $X$, and $|X|=i+d$. Then pick a particular element of $X$ as special. This is the left hand side. $$$$ Then consider picking a special monomial in this set. Say this is in the variable $x_l$ Then pick $S_*=i_1*x_1,..,i_{l-1}*x_{l-1},i_{l+1}*x_{l+1},..,i_d*x_d$. Note this leaves the coefficient on $x_l$ unbounded. Then pick the set $X$ s.t. the coefficients on monomials in $X$ are bounded by $S_* $'s monomial coefficients, $S_* $ and the special monomial are in $X$, and $|X|=i+d$. This is the right hand side. $$$$ Both of these count unique sets $X$ with a special monomial, hence they are equal.

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