1
$\begingroup$

$Theorem$.

Let $2n,\: dm\in \mathbb{N}$

Let $S$ be the set of all non-negative integer solutions to

$x_1+x_2+...+x_{2n}=dm$ such that $x_{2k-1} \leq x_{2k},\; \forall 1 \leq k \leq n$.

Then $|S|=\sum _{p=0}^{\lfloor\frac{dm}{2}\rfloor}\left(\binom{2p+n-1}{n-1}\cdot \binom{\lfloor{\frac{dm}{2}}\rfloor-p+n-1}{n-1}\:\right)\:$

$Example.$

$2n=6 , dm=20$

Then there are $9009$ non-negative integer solutions to

$x_1+x_2+...+x_6=20$

Such that $x_1 \leq x_2\:\ , x_3 \leq x_4\: , x_5 \leq x_6$

$Proof.$

$x_{2k-1} \leq x_{2k},\; \forall 1 \leq k \leq n$

$\implies \forall 1 \leq k \leq n,\; x_{2k}=x_{2k-1}+\alpha_k:\:\alpha_k\in \mathbb{N}\cup{\{0\}}\:$and $0\le \sum _{k=1}^n\left(\alpha _k\right)\le dm$ $\implies \sum _{i=1}^{2n}\left(x_i\right)=dm\: \implies \sum _{k=1}^n\left(2x_{2k-1}+\alpha _k\right)=dm$ $\implies2\sum _{k=1}^n\left(x_{2k-1}\right)+\sum _{k=1}^n\left(\alpha _k\right)\:dm\\$ $\implies \sum _{k=1}^n\left(x_{2k-1}\right)=\frac{\left(dm-\sum \:_{k=1}^n\left(\alpha \:_k\right)\:\:\right)}{2}\:\:\:(1)$

Now,

$\forall 0\leq i \leq dm$

Let $A_i$ be the set of all non-negative integer solutions to

$\sum \:_{k=1}^n\left(\alpha \:_k\right)=i$

Let $X_i$ be the set of all non-negative integer solutions to

$\sum _{k=1}^n\left(x_{2k-1}\right)=dm-i$

Notice that $\forall a\in A_i$ for a fixed $i$ there are $|X_i|$ solutions.

On the other hand, there are $|A_i|=\binom{i+n-1}{i} solutions$ in $A_i$

Therefore

$|S|=\:\sum _{i=0}^{dm}\left(\left|A_i\right|\left|X_i\right|\right)\:=\sum _{i=0}^{dm}\left(\binom{i+n-1}{i}\binom{dm-i+n-1}{dm-i}\right)\: $

Now,

from $(1)$ and because we are interesting in non-negative integers solutions,

we can conclude that

$\left(dm-\sum \:_{k=1}^n\left(\alpha \:_k\right)\:\:\right)\nmid 2\:$ $\implies X_i=\emptyset \implies |X_i|=0 \:\:(2)$

Now , from $(2)$ we get that

$\frac{dm}{2}\mid2\implies \sum _{i=0}^{dm}\left(\binom{i+n-1}{i}\binom{dm-i+n-1}{dm-i}\right)=\sum _{p=0}^{\frac{dm}{2}}\left(\binom{2p+n-1}{2p}\binom{\frac{dm}{2}-p+n-1}{\frac{dm}{2}-p}\right)$

Otherwise

$\sum _{i=0}^{dm}\left(\binom{i+n-1}{i}\binom{dm-i+n-1}{dm-i}\right)=\sum _{p=0}^{\frac{dm}{2}-\frac{1}{2}}\left(\binom{2p+n-1}{2p}\binom{(\frac{dm}{2}-\frac{1}{2})-p+n-1}{(\frac{dm}{2}-\frac{1}{2})-p}\right)=$

$\sum _{p=0}^{\lfloor\frac{dm}{2}\rfloor}\left(\binom{2p+n-1}{2p}\binom{\lfloor\frac{dm}{2}\rfloor-i+n-1}{\lfloor\frac{dm}{2}\rfloor-i}\right)\:\:\:$

And since $\frac{dm}{2}\mid2\implies\frac{dm}{2}=\lfloor\frac{dm}{2}\rfloor$

We get in any case that

$ \sum _{i=0}^{dm}\left(\binom{i+n-1}{i}\binom{dm-i+n-1}{dm-i}\right)= \sum _{p=0}^{\lfloor\frac{dm}{2}\rfloor}\left(\binom{2p+n-1}{2p}\binom{\lfloor\frac{dm}{2}\rfloor-i+n-1}{\lfloor\frac{dm}{2}\rfloor-i}\right)=$

$\sum _{p=0}^{\lfloor\frac{dm}{2}\rfloor}\left(\binom{2p+n-1}{n-1}\cdot \binom{\lfloor\frac{dm}{2}\rfloor-p+n-1}{n-1}\:\right)\:$

$\\ $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.