Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

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;
share|improve this answer
    
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 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 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 at 7:51
    
Some of those are permutations and not allowed by the constraints of the problem. –  bobbym Jul 4 at 7:53
1  
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 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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.