Sum of squares of products of subsets without neighboring elements equals $(N+1)! -1$

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?

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.)

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)!.$$