How many terms are there in a cyclic summation?

Question

I was wondering whether there is any formula that can calculate the number of terms in a cyclic sum:

If $i = 1, \ldots, n$, then for $\sum_{\text{cyc}}x_ix_j$, there are $\frac{n(n-1)}{2}$ terms in the summation.

For example

If $i = 4$, then there are $6$ terms, like, $x_1x_2, x_1x_3, x_1x_4, x_2x_3, x_2x_4, x_3x_4.$ which equals to $ \frac{4\times3}{2} = 6$.

However, is there any formula that can calculate the cases like,

$i = 1, \ldots, n$, $\sum_{\text{cyc}}x_ix_jx_k$

$i = 1, \ldots, n$, $\sum_{\text{cyc}}x_ix_jx_kx_l$

Answer 1

The following are just some thoughts that may help:

For your first summation, we need $i \neq j$ and that the summation cycles through in the manner you described. Notice that since we are counting terms we see that clearly terms of the form $x_{1}x_{j}$, where $j$ is such that $1 \leq j \leq i$.we count $j-1$ distinct terms. Clearly the number possibilities decreases by $1$ as the index of the first term increases by $1$. Recall that $\sum_{k=1}^nk=\frac{n(n+1)}2$ and then set $j-1 = n$ to get the desired formula. For your second summation, we can look at the problem the same way where we fix the first symbol $x_{1}$ and look at the distinct terms possible of $x_{1}x_{j}x_{k}$. By the previous work there are $\frac{j(j-1)}2$ terms of this form. Now if we fix the terms to be of the form $x_{2}x_{j}x_{k}$ we see that there are $\frac{j(j-1)}2 - 4$ if $i = 4$....

I am not sure yet of a general form for how much to subtract off. I am sure there is a combinatorial number to make your problem easy, but I do not know one.

Answer 2

You call the sums cyclic sums, but in fact they are symmetric sums. Not all textbooks distinguish clearly between the two, which is unfortunate, because the distinction is useful. I'll call them symmetric sums here. See below for an explanation of the difference.

The number of terms in the symmetric sum $$\sum_{\text{sym}}x_1x_2\cdots x_d,$$ over the products of $d$ distinct variables out of $n$, is precisely $\binom{n}{d}$. After all, each term is obtained by choosing $d$ variables from the $n$ variables, and every choice of $d$ variables yields a term in the symmetric sum.

For more general symmetric sums of the form $$\sum_{\text{sym}}x_1^{n_1}x_2^{n_2}\cdots x_d^{n_d},$$ the number of terms is a multinomial coefficient. If $d_k$ denotes the number of $k$-th powers in the product, then the number of terms is $$\binom{n}{d_0,\ldots,d_n}=\frac{n!}{d_0!d_1!\cdots d_n!}.$$ Note that $d_0+d_1+\ldots+d_n=n$.

---

The difference between symmetric and cyclic sums is clearest with an example; if $n=4$ then $$\sum_{\text{sym}}x_1x_2=\sum_{\sigma\in S_4}x_{\sigma(1)}x_{\sigma(2)}=x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4,$$ which is the sum over all permutations of the indices of $x_1x_2$. On the other hand $$\sum_{\text{cyc}}x_1x_2=\sum_{\sigma\in C_4}x_{\sigma(1)}x_{\sigma(2)}=x_1x_2+x_2x_3+x_3x_4+x_4x_1,$$ which is the sum over all cyclic shifts of the indices.