contando el número de la solución

Question

Cuántas soluciones de la ecuación $x_0+x_1+⋯+x_k=s$ tal que $0\leq x_i\leq s$, tal que una solución no es el reverso de otro. Que se suponga $k=3$ y $s=4$ entonces la solución de $(0,1,0,3)$ es la inversa de $(3,0,1,0)$.

Answer 1

Normalmente (ignorando los revertir la condición), la respuesta sería $\binom{k+s}{s}$ más que las estrellas y las barras de argumento.

Sin embargo, ahora tenemos que corregir para revertir la condición. La mayoría de las veces, esta operación de "pares" de una secuencia con una secuencia distinta. Podemos calcular el número que se relacionan con ellos de la siguiente manera:

Queremos saber el número de soluciones de la ecuación dada para que $x_0=x_k$, e $x_1=x_{k-1}$, y así sucesivamente. Esta está dada por

• el número de soluciones a $2x_0+2x_1+\cdots+2x_{\lfloor k/2 \rfloor}=s$ si $k$ es impar, o
• el número de soluciones a $2x_0+2x_1+\cdots+2x_{k/2-1}+x_{k/2}=s$ si $k$ es incluso.

En el extraño $k$ de los casos, el número de soluciones está dado por $\binom{s/2+\lfloor k/2 \rfloor}{s/2}$ si $s$ es incluso, o $0$ si $s$ es impar, por las estrellas y las barras de método (buceo por $2$ ambos lados). En el $k$ de los casos, es un poco más complicado, ya que $x_{k/2}$ (es decir, el número medio) puede tomar cualquier valor $i \in \{0,1,\ldots,s\}$ que $s-i \equiv 0 \pmod 2$. Así que tenemos $\sum_{\substack{i \in \{0,1,\ldots,s\} \\ s \equiv i \pmod 2}} \binom{s-i+k/2}{(s-i)/2}$.

Así, el número de secuencias que están asociados con ellos es $$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;

Answer 2

OEIS dice que la secuencia se relaciona con números de alcano, que se definen como:

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

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

y la respuesta requerida es %#% $ #%

$c$, $r$ $

Esto puede ser de interés: https://cs.uwaterloo.ca/journals/JIS/cayley.html