4
$\begingroup$

I am interested in finding an analytical form of the following function $f(n)$ defined as: $$f(n):=\sum_{\{\bar{K}\}}\prod_{l<j}^{n}e^{ik_lk_j},$$ where $\{\bar{K}\}$ is the full set of binary permutations of length $n$ and $i$ denotes complex $i$. Example for $n = 3$ we get $$\{\bar{K}\} = \{\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 0\}, \{1, 0, 0\}, \{0, 1, 1\}, \{1, 0, 1\}, \{1, 1, 0\}, \{1, 1, 1\}\}.$$ Can Mathematica assist in deriving a function in terms of $n$ in a purely mathematical form? The following code defines and evaluates the function $f$ for a given $n$:

n = 3;

K[n_] := Flatten[GatherBy[Tuples[{0, 1}, n], Total], 1]
P[n_, k_] := 
  Product[If[i < j, Exp[I*K[n][[k]][[i]]*K[n][[k]][[j]]], 1], {i, 1, 
    n}, {j, 1, n}];

f[n_] := Sum[P[n, k], {k, 1, 2^n}]
f[n]
f[x]

It gives the correct result for chosen $n$, but not a clean analytical form in terms of variable $n$, which I am looking for (the result at the end as you can see is still somewhat in numerical form).

As JimB correctly showed in his answer, the analytic form can be found by identifying a pattern. But in this case I am particularly interested in a more direct approach using Mathematica's symbolic tools. I'm particularly interested in a direct symbolic way of coding the summation $\sum_{\overline{K}}(\cdot)$, this is the tricky part.

Any ideas on how to make the most of Mathematica to assist in this task? Thanks.

$\endgroup$
2
  • 1
    $\begingroup$ Using oeis.org and Mathematica results in the general form of $n+1+\sum _{k=2}^n e^{\frac{1}{2} i (k-1) k} \binom{n}{k}$ or in Mathematica code n+1+ Sum[E^((1/2)*I*(-1 + k)* k)*Binomial[n, k], {k, 2, n}]. I'll write up an answer shortly. $\endgroup$
    – JimB
    Nov 2, 2021 at 17:18
  • $\begingroup$ I will only note that Flatten[GatherBy[IntegerDigits[Range[0, 2^n - 1], 2, n], Total], 1] is equivalent to Flatten[IntegerDigits[GatherBy[Range[0, 2^n - 1], DigitCount[#, 2, 1] &], 2, n], 1]. $\endgroup$ Dec 22, 2021 at 15:54

1 Answer 1

12
$\begingroup$

If one makes a table of the first few values of $n$, then a pattern becomes evident:

Table[{n, f[n]}, {n, 3, 8}] // TableForm

Table of values of f[n]

One can see that the leading term is $n+1$. The other coefficients associated with the $e^{z i}$ are just binomial coefficients (which also could be determined by typing in 28,56,70,56,28,8,1 at oeis.org):

n = 8;
Table[Binomial[n, k], {k, 2, n}]
(* {28, 56, 70, 56, 28, 8, 1} *)

The exponents are found with

n = 8;
Table[k (k - 1)/2, {k, 2, n}]
(* {1, 3, 6, 10, 15, 21, 28} *)

Putting these two sequences together we have

Sum[E^(I k (k - 1 )/2)*Binomial[n, k], {k, 0, n}]

or

$$\sum _{k=0}^n \binom{n}{k} e^{\frac{1}{2} i k (k-1)}$$

Addition

The OP has more than reasonably asked for a solution that really involves Mathematica functionality. I still don't know how to do that. But here is an alternative to searching for patterns (as done above).

The function P[n,k] can be rewritten as

P[n_, k_] := Exp[I Sum[K[n][[k]][[i]]*K[n][[k]][[j]], {j, 2, n}, {i, 1, j - 1}]]

Note that the sum

Sum[K[n][[k]][[i]]*K[n][[k]][[j]], {j, 2, n}, {i, 1, j - 1}]

is the number of ways to choose 2 1's from the $k$-th arrangement (as the product K[n][[k]][[i]]*K[n][[k]][[j]] will only be 1 if both terms are 1 and 0 otherwise. If there are $x$ 1's in the $k$-th arrangement, then the number of ways to choose 2 1's is $x(x-1)/2$.

Also, there are ${n}\choose{x}$ arrangements with $x$ 1's with $x=0,1,\ldots,n$. So the general formula will be

$$\sum_{x=0}^n {{n}\choose{x}} e^{i x(x-1)/2}$$

$\endgroup$
5
  • $\begingroup$ Great comprehensive response, thanks. $\endgroup$
    – John Doe
    Nov 3, 2021 at 14:26
  • $\begingroup$ Would you agree that the form of the summation ($\sum_{\overline{K}}\cdot$) of the function $f(n)$ makes the function unsuitable (or at least very tricky) for any type of direct symbolic evaluation (or simplification) using Mathematica? $\endgroup$
    – John Doe
    Dec 21, 2021 at 8:44
  • 2
    $\begingroup$ I don't agree. I just happened to go the brute-force approach and looked for patterns. There are probably "more symbolic" ways to re-write your code. For example, the If statement in your definition of P[n_,k_] could be removed by using P[n_, k_] := Product[Exp[I*K[n][[k]][[i]]*K[n][[k]][[j]]], {i, 1, n - 1}, {j, i + 1, n}];. Probably K[n_] might also be modified that would allow for a path to the symbolic result. While I've used Mathematica since version 1, I'm still not very good at it. If you could hook others here, then a more direct path could be found. $\endgroup$
    – JimB
    Dec 21, 2021 at 17:57
  • 1
    $\begingroup$ I think you could "unaccept" my answer and make it explicit that you'd like to find a more direct solution to a symbolic result. I'd like to see that answer, too. $\endgroup$
    – JimB
    Dec 21, 2021 at 17:59
  • $\begingroup$ Okay thanks, I have done so. $\endgroup$
    – John Doe
    Dec 21, 2021 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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