1
$\begingroup$

Suppose we have a vector $x=(x_0,x_1,x_2,\ldots,x_{n-1})$ with $x_i\in\{0,1,2\}$ for all $i=0,1,...,n-1$.

Define $$ x'=\sum_{i=0}^{n-1}x_i, $$ then $$ 0\leq x'\leq n\cdot 2.. $$

I would like to know how many possibilities of vectors there are, for fixed $0\leq m\leq n\cdot 2$, to have $$ x'=m. $$

I think, for example, for $x'=0$ and $x'=n\cdot 2$, we only have one possibility, namely $(0,...,0)$ and $(2,...,2)$. But maybe there is some general formula.

I don’t know whether there is some Trick.

$\endgroup$
1
$\begingroup$

I don't know why John Don didn't post this as an answer. This is a combinatorial problem, covered by generating functions (for example this one or this one and a really good reading here). So, we want $$\sum\limits_{i=0}^{n-1} x_i =m$$ $$0\leq x_i\leq 2, \forall x_i=0..n-1$$ The generating function is $$(1+x+x^2)(1+x+x^2)...(1+x+x^2)=(1+x+x^2)^n$$ and the coefficient near $x^{m}$ term is the answer. Considering multinomial theorem: $$(1+x+x^2)^n=\sum\limits_{k_1+k_2+k_3=n}\binom{n}{k_1,k_2,k_3}1^{k_1}\cdot x^{k_2}\cdot x^{2k_3}=\\ \sum\limits_{k_1+k_2+k_3=n}\frac{n!}{k_1!k_2!k_3!} x^{k_2+2k_3}$$ In other words, the answer is $$\sum\limits_{k_1+k_2+k_3=n\\k_2+2k_3=m}\frac{n!}{k_1!k_2!k_3!}$$

$\endgroup$
  • 1
    $\begingroup$ Yes ... true, thank you for pointing out! Fixing ... $\endgroup$ – rtybase Nov 26 '17 at 16:26
  • $\begingroup$ Denoting this sum by $C(n,m)$, i.e. $$C(n,m):=\sum_{k_1+k_2+k_3=n\\k_2+2k_3=m}\frac{n!}{k_1!k_2!k_3!}$$, I think that $$\frac{1}{3^n}\sum_{m=0}^{2n}C(n,m)x^{2n}=x^{2n}$$ since $\sum_{m=0}^{2n}C(n,m)=3^n$. Am I right? $\endgroup$ – John_Doe Nov 26 '17 at 18:48
  • 1
    $\begingroup$ @John_Doe I looks so, from $(1+x+x^2)^n=\sum\limits_{k_1+k_2+k_3=n}\binom{n}{k_1,k_2,k_3}1^{k_1}\cdot x^{k_2}\cdot x^{2k_3}$ just by $x=1$. $\endgroup$ – rtybase Nov 26 '17 at 19:06
1
$\begingroup$

The expression providing the result you need is $$ I_n(m)=\sum_{x_0=0}^2\cdots \sum_{x_{n-1}=0}^2 \delta_{\sum_i x_i,m}\ , $$ where $\delta_{a,b}=1$ if $a=b$ and $=0$ otherwise. Basically this is a counting device: you get a '$+1$' for every configuration $\mathbf{x}$ such that the sum of the components is equal to $m$. Using the integral representation $$ \delta_{a,b}=\int_0^{2\pi}\frac{d\xi}{2\pi}e^{\mathrm{i}\xi (a-b)} $$ you get $$ I_n(m)=\int_0^{2\pi}\frac{d\xi}{2\pi}e^{\mathrm{i}\xi m}\left(\sum_{x=0}^2 e^{-\mathrm{i}\xi x}\right)^n=\int_0^{2\pi}\frac{d\xi}{2\pi}e^{\mathrm{i}\xi m}(1+e^{-\mathrm{i}\xi}+e^{-2\mathrm{i}\xi})^n\ . $$ Expanding with the multinomial theorem, you can get a more explicit expression. Mathematica can handle this integral for specific values of $m$ and $n$. For example, for $m=38$ and $n=29$ you get $I_n(m)=774369291150$.

$\endgroup$
  • 2
    $\begingroup$ Nice solution, though I personally feel that this is a bit of an overkill; there are far simpler methods that would give a solution that could be calculated in WolframAlpha, for example. $\\$E.g. we could observe that, the 'answer' the OP seeks is the coefficient of $x^m$ in $(1 + x + x^2)^n$. Plugging into WolframAlpha then gives the solution as it does in your answer. (I haven't posted this as an answer, as I don't feel it is particularly complete or satsfactory enough to be a full answer.) $\endgroup$ – John Don Nov 23 '17 at 21:37
  • $\begingroup$ @Pierpaolo Is it possible to compute $\limsup_{n\to\infty}\frac{1}{n}\log (\frac{1}{3^n}\sum_{m=0}^{2n}I_n(m)\cdot c_m)$, where $c_m$ is some constant depending on $m$? $\endgroup$ – John_Doe Nov 24 '17 at 7:53
  • $\begingroup$ @JohnDon I have the same question to your answer. By $a(n,m)$ denote the coefficient of $x^m$ in $(1+x+x^2)^n$. Is it then possible to determine $\limsup_{n\to\infty}\frac{1}{n}\log(\frac{1}{3^n}\sum_{m=0}^{2n}a(n,m)\cdot c_m)$? $\endgroup$ – John_Doe Nov 24 '17 at 8:24
  • $\begingroup$ @JohnDon By the way: If I see it right, the coefficient of $x^m$ in $(1+x+x^2)^n$ is the multinomial coefficient $\binom{n}{n_1,n_2,n_3}$ with $n_1+n_2+n_3=n$ and $n_2+2n_3=m$. Here, $n_1$ is the number of zeros, $n_2$ the number of ones and $n_3$ the number of twos. $\endgroup$ – John_Doe Nov 24 '17 at 8:40
  • 1
    $\begingroup$ @John_Doe That observation is correct; with regards to your follow-up question, it is somewhat hard to say with no knowledge of what $c_m$ is. You say it is a constant (depending on $m$), but as it is inside a sum in which $m$ varies, this is like saying that $a(n,m)$ is just a constant that depends on $n$ and $m$. $\endgroup$ – John Don Nov 24 '17 at 10:15

Your Answer

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

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