Question: Let $n$ be any natural number. Consider all nonempty subsets of the set $\{1,2,...,n\}$, which do not contain any neighboring elements. Prove that the sum of the squares of the products of all numbers in these subsets is $$(n + 1)! - 1.$$ For example, if $n = 3$, then such subsets of $\{1,2,3\}$ are $\{1\}$, $\{2\}$, $\{3\}$, and $\{1,3\}$, and $$1^2 + 2^2 + 3^2 + (1\cdot3)^2 = 23 = 4! -1.$$

This question can be proved by induction, as shown here: induction (sum of squares of products of elements of certain subsets of $\{1,\dots,n\}$)

This seems to me like something that is really out of the blue. So my question is, is there another way to see why this is true? Such as a combinatorial argument. In particular, does the quantity "sum of squares of products of numbers in subsets without neighboring elements" arise in some natural way?

  • 1
    $\begingroup$ You could allow the empty subset to be part of this. Then the product of its members would be interpreted as the empty product $1$. And then the sum is a clean $(n+1)!$ instead of $(n+1)!-1$. $\endgroup$ Dec 25 '19 at 7:39
  • $\begingroup$ I’d like to add that the sum from $1$ to $N$ of $nn!$ is equal to $(N+1)!-1$ as well $\endgroup$
    – Ty Jensen
    Dec 25 '19 at 8:15

Here is a combinatorial argument. It counts members of $S_{n+1}$ in two ways. One way is obviously $(n+1)!$. The other way takes some time to explain. Let's call subsets which do not contain any neighboring elements SWNs, for "subsets without neighbors". I will consider the empty subset an SWN.

Each SWN defines a collection of permutations from $S_{n+1}$ in the following way. If $S=\{x_1,x_2,\ldots,x_k\}$ is an SWN, written in descending order, then for each $i$ from $1$ to $k$, let $t_i$ be a transposition between $x_i+1$ and something smaller. And let $q_i$ be a "transposition" between $x_i$ and something less than or equal to $x_i$. Note that $q_i$ might be the identity permutation instead of a transposition.

For example, with $n=9$, you might have the SWN $\{6,4,1\}$. You could take $t_1$ to be $(74)$ and $q_1$ to be $(65)$. You could take $t_2$ to be $(54)$ and $q_2$ to be $(44)=\mathrm{id}$. You could (must) take $t_3$ to be $(21)$ and could (must) take $q_3$ to be $(11)=\mathrm{id}$.

Now make the product $t_1q_1t_2q_2\cdots t_kq_k$. In the example above, we'd have $(74)(65)(54)(44)(21)(11)$, which you could reduce to $(7564)(21)$.

For any SWN $S=\{x_1,x_2,\ldots,x_k\}$, two distinct choices of $t_1,q_1,\ldots,t_k,q_k$ make distinct permutations in $S_{n+1}$.

If $t_1q_1t_2q_2\cdots t_kq_k=t_1'q_1't_2'q_2'\cdots t_k'q_k'$, consider $t_1=((x_1+1)d)$. It maps $d$ to $x_1+1$, and $x_1+1$ never again appears in the product. So the left side maps $d$ to $x_1+1$. Meanwhile the right side has $t_1'=((x_1+1)d')$, and must map $d'$ to $x_1+1$. So $d$ must be $d'$, and then $t_1=t_1'$, and the equation reduces to $q_1t_2q_2\cdots t_kq_k=q_1't_2'q_2'\cdots t_k'q_k'$.

We can make the same argument to find $q_1=q_1'$. It doesn't change things that $q_1$ might be the identity permutation.

Now we are reduced to $t_2q_2\cdots t_kq_k=t_2'q_2'\cdots t_k'q_k'$, similar to where we started, and we conclude that we could keep reducing all the way to $\mathrm{id}=\mathrm{id}$, finding that each $t_i=t_i'$ and $q_i=q_i'$.

Therefore if we make two distinct choices of $t_1,q_1,\ldots,t_k,q_k$ from a particular SWN $S$, we arrive at distinct permutations.

For any SWN $S=\{x_1,x_2,\ldots,x_k\}$, there are $x_1^2x_2^2\ldots x_k^2$ permutations to be made in this way.

We already established distinct choices of $t_1,q_1,\ldots,t_k,q_k$ make distinct permutations. So how many options do we have to choose $t_1,q_1,\ldots,t_k,q_k$? Each $t_i$ is a transposition between $x_i+1$ and something from $\{1,2,\ldots,x_i\}$. Each $q_i$ is a "transposition between $x_i$ and something from $\{1,2,\ldots,x_i\}$. It follows that we have $x_1^2x_2^2\ldots x_k^2$ ways to choose $t_1,q_1,\ldots,t_k,q_k$.

Given two different SWNs $S$ and $T$, it's not possible for their corresponding collections of permutations to overlap.

Suppose $S=\{x_1,x_2,\ldots,x_k\}$ and $T=\{y_1,y_2,\ldots,y_\ell\}$, and we make choices of $t$s and $q$s for each such that $t_1q_1t_2q_2\cdots t_kq_k=t_1'q_1't_2'q_2'\cdots t_\ell'q_\ell'$. If $x_1>y_1$, then the left side moves $x_1+1$ while the right side does not. It follows that $x_1=y_1$.

Next we could conclude that $t_1=t_1'$ and $q_1=q_1'$ as we did in the first block of the proof. That reduces us to $t_2q_2\cdots t_kq_k=t_2'q_2'\cdots t_\ell'q_\ell'$, similar to where we started, and we conclude all the $x_i=y_i$, $t_i=t_i'$, and $q_i=q_i'$.

Every permutation from $S_{n+1}$ is somewhere among the permutations created this way from some SWN.

Suppose you have a permutation from $S_{n+1}$ written in reduced cycle notation. You could map it to from $S_{n}$ by "removing" $n+1$. For example, in $S_6$ we might have $(623)(51)$, which would map to $(51)(32)$.

Then map to $S_{n-1}$, $S_{n-2}$, etc. Continuing our example $$(623)(51)\mapsto (51)(32)\mapsto (32)\mapsto (32)\mapsto \mathrm{id}\mapsto \mathrm{id}$$ The short version is $$(623)(51)\mapsto (51)(32)\mapsto (32)\mapsto \mathrm{id}$$ Reading right to left, we can reconstitute the original permutation as a product of transpositions. Each reduction corresponds to left-multiplying by a transposition. In the above example, $$(623)(51)\stackrel{(63)\cdot}{\mapsto} (51)(32)\stackrel{(51)\cdot}{\mapsto} (32)\stackrel{(32)\cdot}{\mapsto} \mathrm{id}$$ And this tells us we started with $(63)(51)(32)$.

Now read this product of transpositions left to right. You have the highest number $N$ present in the first. If you have $N-1$ present in the second, pair these two transpositions. Otherwise, introduce a trivial "transposition" $((N-1)(N-1))$. (If I use quotes around "transposition", I am referring to a permutation $(ij)$ where $i$ may or may not equal $j$.) Repeat with the remaining transpositions. In our example, we now have $\overbrace{(63)(51)}\overbrace{(32)(22)}$.

In this manner, turn the product into a product of pairs of "transpositions" where the first is always a real transposition with its larger number being some $i$, and the second is a "transposition" with its larger number being $i-1$, and any following "transpositions" use only $i-2$ or lower. Such a product can be labeled by a SWN from $S_{n+1}$, using the larger number from the second "transposition" from each pair. In the case of our example, we would label it $\{5,2\}$.

The method described earlier for creating a permutation from the SWN $\{5,2\}$ would lead to $(63)(51)(32)(22)$ as one of its $(5\cdot2)^2$ permutations. More generally, the method described earlier for creating a permutation from this SWN would reconstitute the permutation we started with.

All of the above establishes that...

There is a way to partition $S_{n+1}$ into subsets, where each subset can be labeled by an SWN from $\{1,\ldots,n\}$, and the size of each subset in the partition is the square of the product of the members of the SWN. And since $S_{n+1}$ of course has $(n+1)!$ elements, this brings us to the OP's goal: $$\sum_{S\in\mathrm{SWN}_n}\left(\prod_{x\in S}x\right)^2=(n+1)!$$

In the history of this answer, you will see ultimately the same result, but established according to how I really thought about it, instead of this relatively streamlined explanation.

Decorative Version

$n+1$ people are seated in a row on one side of a long table, each having come with a personalized gift.

The MC chooses some subset of these people, taking care not to choose a subset that includes people sitting right next to each other.

The person among the chosen who is closest to the left end of the table (from our perspective, facing these people) must choose someone sitting to their left. They stand up, walk over to them, exchange gifts, and sit back down. Then the person seated to that persons immediate left may or may not do the same. That is, they may do nothing, or they may choose someone sitting to their left, stand up, walk over to them, exchange gifts, and sit back down. Then repeat with the next leftmost "chosen" person, and so on.

How many "gift exchanges" could be accomplished in this way? (The answer is $(n+1)!$, because this is just another way of describing the complete set of permutations on $n+1$ objects.)

  • $\begingroup$ Really nice answer! Cray how you managed to relate $\Pi x_i^2$ to permutations. Typo for defn of $q_i$, it should be a transposition between $x_i$ instead of $x_i + 1$ right?. Also, in showing the map from SWN to $S_{n+1}$, the example given is says that $(63)(623)(51) = (51)(32)$ but i think you meant to type $(62)$ instead of $(63)$. $\endgroup$
    – eatfood
    Dec 28 '19 at 3:00
  • $\begingroup$ @ eatfood Thanks! For a second there I misread your catch about $q_i$ to be about $x_i$. But fixed it now. For the $(63)(623)=(32)$, that is what I mean. But maybe I am reading permutations left to right as I multiply them, and you are reading right to left. Accounting for that conventional difference shouldn't change things in an important way though. $\endgroup$ Dec 28 '19 at 6:07

Let's say that $S \subset \{1, \dots, n\}$ is sparse if it doesn't contain any neighboring elements. Note that $S$ is sparse if and only if $S$ and $S-1$ are disjoint, where $S-1 = \{a-1 \mid a \in S\}$ (excluding $0$ if necessary). I'll consider $\varnothing$ to be a sparse subset with $\prod_{a \in \varnothing} a^2 = 1$, so that now we want to show that $\sum_S \prod_{a \in S} a^2 = (n+1)!$, where the sum is taken over all sparse $S \subset \{1, \dots, n\}$. Then for a sparse $S$ we have

$$\prod_{a \in S} a^2 = \prod_{a \in S} a ((a-1) + 1) = \prod_{a \in S} a \prod_{b \in S-1} (b+1) = \prod_{a \in S} a \sum_{T' \subset S-1} \prod_{b \in T'} b = \sum_{T' \subset S-1} \prod_{a \in S \cup T'} a.$$

Proposition. For a set $T \subset \{1, \dots, n\}$, we can uniquely write $T = S \cup T'$ for $S$ sparse and $T' \subset S-1$.

Proof: For $a \in T$, let $$\ell(a) = \max \{k \geq 0 \mid \{a, a+1, \dots, a + k\} \subset T\}.$$ I'll show that the above holds iff $S = \{a \in T \mid \ell(a) \text{ is even}\}$. First suppose $S$ is this set. Then for $a \in S$, if $a-1 \in T$, $\ell(a-1) = \ell(a) + 1$ is odd, and otherwise $a-1 \not \in T$, so either way $a-1 \not \in S$, hence $S$ is sparse. Furthermore $T \setminus S$ consists of those points $a$ with $\ell(a)$ odd, each of which must then have $a+1 \in S$, so $T' := T \setminus S \subset S-1$. Conversely, suppose $T = S \cup T'$ for $S$ sparse and $T' \subset S-1$. Then a brief induction on $\ell(a)$ shows that $a \in S$ iff $\ell(a)$ is even: when $\ell(a) = 0$, $a \in S$, and when $\ell(a) = 1$, $a \in T'$. For $\ell(a) \geq 2$, either $a \in S$, in which case $a+1 \in T'$ by sparsity of $S$, so $\ell(a+1) = \ell(a) - 1$ is odd, hence $\ell(a)$ is even, or in the other case $a \in T'$, so $a+1 \in S$, $\ell(a+1) = \ell(a) - 1$ is even, hence $\ell(a)$ is odd. Thus $S = \{a \in T \mid \ell(a) \text{ is even}\}$.

Letting $s(T)$ be the unique $S$ described above, we have that the sets $T$ with $s(T) = S$ are exactly those with $T = S \cup T'$ for $T' \subset S-1$. Then using the above, we have $$\prod_{a \in S} a^2 = \sum_{s(T) = S} \prod_{a \in T} a$$ so it follows that $$\sum_{S \text{ sparse}} \prod_{a \in S} a^2 = \sum_{S \text{ sparse}} \sum_{s(T) = S} \prod_{a \in T} a = \sum_{T \subset \{1, \dots, n\}} \prod_{a \in T} a = \prod_{a \in \{1, \dots, n\}} (a + 1) = (n+1)!.$$


This is a little bit sketchy.
Consider the easier problem of finding the sum of the squares of the products of all elements for each subset of $\{1,2,3,...,n\}$ (so I am dropping the neighboring condition).
The answer is $$(1+1^2)(1+2^2)(1+3^2)...(1+n^2)$$ This product can be written as a sum where each term is obtained by choosing $1$ or $j^2$ for each $(1+j^2)$ and then muliplying everything.
In fact, each term obtained this way is the square of the products of all elements of a particular subset.
For example, if we pick $1^2$ in $(1+1^2)$, $5^2$ in $(1+5^2)$, $11^2$ in $(1+11^2)$ and $1$ in all other terms of the product we get the square of the products of all elements of $\{1,5,11\}$.

Now I try to adapt this approach to the actual problem.
Consider the following sum:

$$\left(1+\frac{n^2}{n}\right)\left(1+\frac{(n-1)^2}{n-1}\right)\left(1+\frac{(n-2)^2}{n-2}\right)...\left(1+\frac{2^2}{2}\right)(1+1^2) \tag{1}$$

We start from the term $\left(1+\frac{n^2}{n}\right)$. We can decide to not include $n$ in our subset, hence we pick $1$ in the term $\left(1+\frac{n^2}{n}\right)$ and the next term we are going to consider is $\left(1+\frac{(n-1)^2}{n-1}\right)$.
Or, we can include $n$, hence we pick $\frac{n^2}{n}$ in the term $\left(1+\frac{n^2}{n}\right)$. In this case, we are multypling by $n^2$ (for the same reason as before) and we are dividing by $n$; notice that the term $\left(1+\frac{(n-1)^2}{n-1}\right)$ is exactly equal to $n$, so by dividing by $n$ we are cancelling $\left(1+\frac{(n-1)^2}{n-1}\right)$; hence, the next term we are going to consider next is $\left(1+\frac{(n-2)^2}{n-2}\right)$.

The idea is that if we include $n$ in our subset we cannot include $n-1$ (beacuse otherwise we would have two neighboring elements); cancelling the term $\left(1+\frac{(n-1)^2}{n-1}\right)$ is the same as not picking $n-1$.

We then repeat and the final result should be the square of the product of all elements for a subset of $\{1,2,3,...,n\}$ with no neighboring elements.

For example, consider the subset $\{13,5,3\}$; this corresponds to the term: $$\frac{13^2}{13}\left(1+\frac{12^2}{12}\right)\frac{5^2}{5}\left(1+\frac{4^2}{4}\right)\frac{3^2}{3}\left(1+\frac{2^2}{2}\right)$$ $$=\frac{13^2}{13}(13)\frac{5^2}{5}\left(5\right)\frac{3^2}{3}\left(3\right)$$ $$=13*5*3$$

Notice that (1) is equal to $(n+1)!$ so this should be the value of the required sum.


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.