# counting the number of solution

How many solutions of the equation $x_0+x_1+⋯+x_k=s$ such that $0\leq x_i\leq s$, such that one solution is not the reverse of another. That is suppose $k=3$ and $s=4$ then the solution $(0,1,0,3)$ is the reverse of $(3,0,1,0)$.

-
But (0,1,0,2) is not a solution, is it? Would you explain better what you mean by reverses? –  user99680 Jul 4 '14 at 6:40
I presume it's $(0,1,0,3)$ –  gar Jul 4 '14 at 6:42
Problem reworded to fix the (0,1,0,3) –  bobbym Jul 4 '14 at 7:06

## 2 Answers

Ordinarily (ignoring the reversing condition) the answer would be $\binom{k+s}{s}$ from a stars and bars argument.

However, we now need to correct for the reversing condition. Most of the time, this operation "pairs up" a sequence with a distinct sequence. We can calculate the number that are paired with themselves as follows:

We want to find the number of solutions to the given equation for which $x_0=x_k$, and $x_1=x_{k-1}$, and so on. This is given by

• the number of solutions to $2x_0+2x_1+\cdots+2x_{\lfloor k/2 \rfloor}=s$ if $k$ is odd, or
• the number of solutions to $2x_0+2x_1+\cdots+2x_{k/2-1}+x_{k/2}=s$ if $k$ is even.

In the odd $k$ case, the number of solutions is given by $\binom{s/2+\lfloor k/2 \rfloor}{s/2}$ if $s$ is even, or $0$ if $s$ is odd, by the stars and bars method (diving by $2$ both sides). In the even $k$ case, it's a bit trickier, since $x_{k/2}$ (i.e., the middle number) can take any value $i \in \{0,1,\ldots,s\}$ for which $s-i \equiv 0 \pmod 2$. So we have $\sum_{\substack{i \in \{0,1,\ldots,s\} \\ s \equiv i \pmod 2}} \binom{s-i+k/2}{(s-i)/2}$.

So, the number of sequences that are partnered with themselves is $$c(k,s):=\begin{cases} 0 & \text{if k is odd and s is odd} \\ \binom{s/2+\lfloor k/2 \rfloor}{s/2} & \text{if k is odd and s is even} \\ \sum_{\substack{i \in \{0,1,\ldots,s\} \\ s \equiv i \pmod 2}} \binom{(s-i)/2+k/2-1}{(s-i)/2} & \text{if k is even.}\end{cases}$$

Thus the number is $$\frac{1}{2}\left(\binom{k+s}{s}-c(k,s)\right)+c(k,s)=\frac{1}{2}\binom{k+s}{s}+\frac{c(k,s)}{2}.$$

There were some bugs in earlier versions of this answer (but the overall idea didn't change). So here's some GAP code which verifies it's correct for $k,s \in \{1,2,\ldots,7\}$:

f:=function(k,s)
local n,c;
n:=Binomial(k+s,s);
if(k mod 2=1) then
if(s mod 2=1) then
c:=0;
else
c:=Binomial(s/2+Int(k/2),s/2);
fi;
else
c:=Sum(Filtered([0..s],i->(s-i) mod 2=0),i->Binomial((s-i)/2+(k/2-1),(s-i)/2));
fi;
return (n-c)/2+c;
end;;

g:=function(k,s)
return Size(Filtered(Tuples([0..s],k+1),T->Sum(T)=s and T<=Reversed(T)));
end;;

for k in [1..7] do for s in [1..7] do Print([k,s]," ",f(k,s)," ",g(k,s),"\n"); od; od;

-
Nice Answer. Looking forward to more solutions from you. Although the OP failed to say if $X_i$'s are integers. Thanks –  satish ramanathan Jul 4 '14 at 7:36
Hi Rebecca; When k = 3 and s = 3 we have only 3 solutions {{0, 0, 0, 3}, {0, 0, 1, 2}, {0, 1, 1, 1}} when I use your formula I get 10. What did I do wrong? –  bobbym Jul 4 '14 at 7:48
My code counts [[0,0,0,3],[0,0,1,2],[0,0,2,1],[0,0,3,0],[0,1,0,2],[0,1,1,1],[0,1,2,0],[0,2,0,1‌​],[1,0,0,2],[1,0,1,1]]. –  Rebecca J. Stones Jul 4 '14 at 7:51
Some of those are permutations and not allowed by the constraints of the problem. –  bobbym Jul 4 '14 at 7:53
If arbitrary permutations are forbidden then the question asks for the number of partitions of $s+k+1$ into $k+1$ parts. It's a more difficult problem (see here: math.stackexchange.com/q/240427/91818). –  Rebecca J. Stones Jul 4 '14 at 8:02

OEIS says the sequence is related to Alkane numbers, which are defined as:

\begin{align*} L(c, r) &= \frac{1}{2}\left(\binom{c+r-3}{r} + D(c, r)\right) \end{align*} where

$$D(c, r) = \left\{\begin{matrix} \dbinom{(c + r - 3)/2}{ r/2} & \text{c is odd and r is even} \\\\ 0 & \text{c is even and r is odd} \\\\ \dbinom{(c + r - 4)/2}{ r/2} & \text{both c and r are even} \\\\ \dbinom{(c + r - 4)/2}{ (r - 1)/2} & \text{both c and r are odd} \end{matrix}\right.$$

and the required answer is $$L\left(k+3,s\right)$$

For $k=3, s=4$, $$L\left(6,4\right)=19$$

This may be of interest : https://cs.uwaterloo.ca/journals/JIS/cayley.html

-