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)$.
-
$\begingroup$ But (0,1,0,2) is not a solution, is it? Would you explain better what you mean by reverses? $\endgroup$– user99680Jul 4, 2014 at 6:40
-
$\begingroup$ I presume it's $(0,1,0,3)$ $\endgroup$– garJul 4, 2014 at 6:42
-
$\begingroup$ Problem reworded to fix the (0,1,0,3) $\endgroup$– bobbymJul 4, 2014 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;
-
1$\begingroup$ Nice Answer. Looking forward to more solutions from you. Although the OP failed to say if $X_i$'s are integers. Thanks $\endgroup$ Jul 4, 2014 at 7:36
-
$\begingroup$ 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? $\endgroup$– bobbymJul 4, 2014 at 7:48
-
$\begingroup$ 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]]
. $\endgroup$ Jul 4, 2014 at 7:51 -
$\begingroup$ Some of those are permutations and not allowed by the constraints of the problem. $\endgroup$– bobbymJul 4, 2014 at 7:53
-
1$\begingroup$ 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). $\endgroup$ Jul 4, 2014 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