The problem is equivalent to counting the number of ways $T(n)$ of creating a sum $a_02^{b_0}+a_12^{b_1}+...+ a_{n-1}2^{b_{n-1}}$, where $a_i\in\{-1,+1\}$, and $b_0,b_1,b_2,...,b_{n-1}$ is a permutation of $0,1,2,...n-1$; such that it satisfies the property $\sum_{0\le j\le i}{a_j2^{b_j}} \ge 0$, for every $0\le i\le n-1$ Notice that the signed sum of different powers of $2$ is always different than zero. Then we can extract the term $\pm2^0$, and divide the remaining terms by $2$, and we will have a solution for the problem with $n-1$. (this is for $n>1$) Also the term $-2^0$ cannot be at the begining, but otherwise, $\pm2^0$ can be anywhere. Then we get a recuerrence $T(n) =$ $[color=\#FF0000](2n-1)[/color]$$T(n-1)$ for every $n>1$ We can easily see that $T(1) = 1$. Then $T(n) =$ (2n-1)!! Edit: Sorry for the typos, I corrected them already

m.candales wrote: We can easily see that $T(1) = 1$. Then $T(n) = (2n+1)!$ But the number of ways to place $n$ weights without a condition is $2^n(n!)$, and $2^n(n!)$ is less than $(2n+1)!$.

I have edited my post. The solution is $T(n) = (2n+1)!!$ which is the product of the odd numbers from $1$ to $2n+1$

You overshot your indices. The recurrence is $T(n) = (2n-1)T(n-1)$ for $n > 1$, with $T(1) = 1$, so $T(n) = (2n-1)!!$.

Very nice problem, I would never think about such recurrence.

Solution : Let $a_n$ be the number which we have to find. Let $2^k$ be last placed weight. Number of ways that right pan is never heavier than left pan placing by $\{ 2^0 , 2^1 , \dots , 2^{n-1} \} \backslash \{2^k\}$ is $a_{n-1} , k=0\dots n-2$ (It's not hard to see). For $k<n-1$ placing $2^k$ has 2 two choices ($2^{n-1}$ is placed left pan). For $k=n-1$ , there is $a_{n-1}$ ways to do it , obviously. So we've recurrence relation $a_n=2(n-1)a_{n-1}+a_{n-1}=(2n-1)a_{n-1}$ and $a_1=1$ , which implies $a_{n}=(2n-1)!!$

My solution: It makes no difference counting the ways in which this can be done for e.g. the weights $1,2,4,8$ or the weights $1,2,8,32$. In general I can say that for each set $A \subset \{2^0,2^1,\dots 2^{n-1}\}$ with $|A|=k$ we get the same number $a_k$. Let $2^{n-1}$ be placed at the $i$-th step. Then there are $a_{i-1}{n-1 \choose i-1}$ possiblie ways for the $i-1$ weights that have been placed before. In the last steps we can place the weights in any order on any pan, which gives $2^{n-i}(n-i)!$ ways. Now we can find the recurrence $a_0=1$ and $a_n = \sum _{i=1}^n a_{i-1}{n-1 \choose i-1} 2^{n-i}(n-i)!=2(n-1)a_{n-1}+ a_{n-1}$. So we get the recurrence $a_0=1$ and $a_n=(2n-1)a_{n-1}$.

Trivial solution: Let's try to put somewhere the lightest weight. If it is chosen on the first move, it should be placed on left side. Otherwise it doesn't matter, and there are 2*(n-1) ways. In total, there are 2*n-1 ways for the lightest weight and it doesn't affect any others. Therefore: T(n) = (2*n-1)*T(n-1).

Eh why was this problem chosen... it's pretty obvious that the smallest weight doesn't affect anything except for -1 at start.

Not quite precise; the set of weights $1,4,6,8$ only allows for $98 = 14 \cdot 7 < 1\cdot 3 \cdot 5 \cdot 7 = 35$ ways to be placed, so there is more than just considering the smallest weight. As very often, it pays to prove a slightly more general statement. Notice the set of (positive) $n$ weights $W = (w_0 < w_1 < \cdots < w_{n-1}) = (2^0 < 2^1 < \cdots < 2^{n-1})$ has the property that $w_k > \sum_{j=0}^{k-1}$ for all $1\leq k \leq n-1$. This makes that each weight whose turn comes to be placed must be placed on the left pan if it is larger than all other placed before, while otherwise can be placed on either pan. This is the only relevant property of the given set of weights, and so allows for a smoother induction towards a recurrence relation for the required $x_n$ value. The last weight in a full series of $n$ placings will bear some index $k$, as the other weights from $W \setminus \{w_k\}$ would have been placed in $x_{n-1}$ number of ways, no matter the value of $k$. Now, if $k=n-1$ that means $w_k$ must be placed on the left pan, while otherwise can be placed on either pan (since $w_{n-1}$ has been already placed - on the left pan). This amounts to $1 + 2(n-1) = 2n-1$ ways, so $x_n = (2n-1)x_{n-1}$. Together with $x_1 = 1$ (or even $x_0 = 1$, for the obvious empty count) this leads to $x_n = (2n-1)!!$.

Right of course, if our weights were something like 3,4,5 clearly 3 would affect things (you can have 3+4-5). Actually it's tempting to think about the larger weights because they dominate everything (sum of smaller powers of two is irrelevant), so you could think about doing case analysis based on where the largest weight is placed. However this can lead to a long solution such as kurt's.

As I said, the relevant property is $w_k > \sum_{j=0}^{k-1}$ for all $1\leq k \leq n-1$. This makes that each weight whose turn comes to be placed must be placed on the left pan if it is larger than all other placed before, while otherwise can be placed on either pan. And of course, the values of the weights being integer is an irrelevant fact.

m.candales wrote: I have edited my post. The solution is $T(n) = (2n+1)!!$ which is the product of the odd numbers from $1$ to $2n+1$ $T(n+1)$ = $Put1stWeightAtLast * PutTheOtherWeights$+ $Put2ndWeightAtLast * PutTheOtherWeights$ + ... + $Put(n+1)thWeightAtLast *PutTheOtherWeight$ The method of putting $ 2^0,2^1,...,2^{n-1}$ in the balance equals to that of $2^0,2^1,...2^{k-1},2^{k+1},2^{k+2},...,2^n$. the ways of putting 1st after all others are putting at left or at right, Put1stWeightAtLast is 2, so to PutkthWeightAtLast for k<(n+1). There is only one way for putting the (n+1)th weight at last, it is putting it at left. Put(n+1)thWeightAtLast is 1. $T(n+1) = (T(n)*2)*n + T(n) $

Can the following be a solution? Please Check... We separate the numbers 2^0, 2^1,...,2^n-1 like this: 2^1, 2^3, 2^5, 2^7,..., 2^2n-1 and 2^0, 2^2, 2^4, 2^6,..., 2^2n-2. With that way we create a bijection: 2^1 to 2^0, 2^2 to 2^1,..., 2^2n-1 to 2^2n-2. ( the elements can be 1-1 joined due to the Cantor's diagonal argument ) Then, we observe that: 2^1 > 2^0. 2^3 > 2^2 + 2^1 + 2^0. 2^5 > 2^4 + 2^3 + 2^2 + 2^1 + 2^0. ... 2^2n-1 > 2^2n-2 + 2^2n-3 + ... + 2^0. The RHS of all above inequalities has ''cardinality'' 1,3,5,...,2n-1 respectively. ''( I mean the number of the terms )'' Hence, by the multiplication law we have 1*3*5*...*(2n-1) = ( 2n-1 ) !!, our goal.

Here is a solution using Induction. Let the number of ways be $\Phi(n)$. The answer is $\Phi(n)=1.3.5....(2n-1)$. Checking by hand, it is trivially true for $n=1,3$. Now think to set $n+1$ weights. Now while considering their setup, note that since $2^n>2^{n-1}+.......+2+1$ we must set the weight $2^n$ in left. In this case we have the previous $\Phi(n)$ ways associated. For $k<n,2^k$ can be set in left or right. And we may choose one of the $n$ weights in one side. So the number of ways will be multiplied by $2n$ with $\Phi(n)$ since for any choice of a weight we have $\Phi(n)$ ways. Thus $\Phi(n+1)=2n\Phi(n)+\Phi(n)=(2n+1)\Phi(n)=1.3.....(2n+1)$ Thus our induction is complete.

Brute force! Let f(n) denote the number of ways. Place the heaviest object in the the kth position, where k lies between 1 and n inclusive. Now for the first k-1 positions, we can choose k-1 weights out of the remaining n-1 and order them and choose left or right in f(k-1) ways. This is the key observation. For the last n-k places, we have (n-k)!*2^n-k ways. Summing over all k between 1 and n inclusive, we get a rather ugly summation;. However, replacing n by n+1, we get a relation between f(n+1) and f(n), namely f(n+1) = (2n+1)*f(n), with initial condition f(1) = 1. Now we proceed with a trivial induction.

If $a_n$ is number of ways with the restriction, and $b_n$ is the number of ways without any restriction.. $2n! = a_n b_n$

Every one can post in here open problem for this problem 4! Thanks

The answer is $\prod_{i=1}^{n}2i-1$. Call a position good if the condition is satisfied; We use a recursive/inductive approach: Let a_n be the number of ways to place them, with $a_1=1$. Now, we look at the number of ways to place the 1; if it's placed first, there's one way, but otherwise, in any position if the 1 hasn't been placed the scales must differ by 2, so in this way, we can place the 1 anywhere since it won't influence the goodness. Therefore there are $2(n-1)+1$ ways to decide where/when we place the 1. So to place the remaining $n-1$ weights is the same as the answer to this problem when we have $n-1$ weights, since everything is just scaled by a factor of 2; in particular, $a_n = (2(n-1) + 1)a_{n-1}$, upon which solving yields the answer. $\blacksquare$

We prove by induction that the answer is $(2n-1)!!$. We assume that the number is $2k-1$ for $k$. Note that $2^0$ can be placed in $2k+1$ positions, the $-1$ because it can't be placed at the beginning and to the right. Then, the rest of the tiles can be placed with $(2k-1)!!$ because the $2^0$ doesn't affect any of the other tiles. Thus, we have $(2k+1)!!$, proving by induction.

The number of ways is $\boxed{(2n - 1)!!}$, where $x!!$ denotes the double factorial. Let $f(n)$ denote the number of valid arrangements satisfying the initial problem. If we consider the $n - 1$ weights $2^1, 2^2, \ldots 2^{n - 2}, 2^{n - 1}$ and divide each by $2$, we obtain the case for $f(n - 1)$. Now we may place the stone weighing $2^0$ into $2n$ places, however it cannot be placed on the right scale on the first move. Therefore there must be precisely $2n - 1$ valid places where $2^0$ may be placed, whence we obtain the recurrence relation $f(n) = (2n - 1)f(n - 1)$. Claim: $f(n) = (2n - 1)!!$. Proof: We prove this claim by induction. Indeed the base case is trivial, as $f(1) = 1$. Now assume for all $k < n$ that this claim holds. Then \[f(n) = (2n - 1)f(n - 1) = (2n - 1)(2n - 3)!! = (2n - 1)!!,\]and the induction is complete. $\blacksquare$

The purpose of this note is to show the power of generating functions while solving recurrences. We assume that the reader has arrived at the recurrence $a_0=1$ and \begin{align} a_{n+1} = \sum _{i=0}^{n} {n \choose i} a_{n-i} \cdot 2^i \cdot i! \end{align}by considering the largest weight. Now consider the exponential power series generating function of $a_m$, i.e. $F(x) = \sum_{m \ge 0} a_m \frac{x^m}{m!}$. We recognize the right hand side of $(1)$ as the coefficient of $x^n$ in $F(x)G(x)$ where $G(x) = \sum_{m \ge 0} b_m \frac{x^m}{m!}$ for $b_m = 2^m \cdot m!$. So, \begin{align*} G(x) = \sum_{m \ge 0} 2^m \cdot m! \cdot \frac{x^m}{m!} = \sum_{m \ge 0} (2x)^m = \frac{1}{1-2x} \end{align*} Thus, $F'(x) = F(x)G(x)$, which implies that \begin{align*} \frac{F'(x)}{F(x)} = \frac{1}{1-2x} \\ \ln F(x) - \ln(F(0)) = \frac{\ln(1-2x)}{-2} \end{align*}therefore, $\boxed{F(x) = \frac{1}{\sqrt{1-2x}}}$. Recall that $\sum_{n \ge 0} \binom{2n}{n} x^n = \frac{1}{\sqrt{1-4x}}$, so we get that $$F(x) = \frac{1}{\sqrt{1-2x}} = \sum_{n \ge 0} \binom{2n}{n} \left( \frac x2 \right)^n,$$and therefore $\boxed{a_n = \binom{2n}{n} \cdot \frac{n!}{2^n} = (2n-1)!!}$.

Wow, very cool problem. The wording in my solution might be a bit unclear Define the "masses" of the weights such that the weight that weighs $2^0$ has a mass of 1 and the weight that weighs $2^{n-1}$ has a mass of $n$ (weight $k$ will refer to the weight with mass $k$). Note that for a given sequence for placing the weights, if a weight has a greater mass than a weight further down the sequence, the second weight can be placed on either side of the balance. Define $f(x)$ to be the number of ways to place $x$ weights on the scale. Say for a given sequence, weight $k$ is placed first. There are $k-1$ weights that weigh less, and $n-k$ that weigh more. For the $k-1$ weighing less, they can be placed in $2^{k-1} \times (k-1)!$ ways. The remaining $n-k$ weights can be ordered with the $k-1$ other weights in a total of ${n-1}\choose{k-1}$ ways. Finally, the $n-1$ weights can be placed in $f(n-1)$ ways. We therefore have $$f(n) = \sum_{k=1}^{n} {2^{k-1} \times (k-1)! \times {{n-1}\choose{k-1}} \times f(n-1)}$$This gives the number of ways to place the weights when weight $k$ is placed first as: $$\frac{(n-1)!(2n-2k)!}{2^{n-2k+1}\times(n-k)!^2}$$ We claim $f(n) = \frac{(2n)!}{2^n\times n!}$, or the product of the first $n$ odd numbers. We can show this result using induction. Clearly, this holds for $n = 1$. Notice that when weight $1$ is placed first, there are $f(n-1)$ ways to place the remaining weights. Additionally, when there are $n+1$ weights, and weight $k+1$ is placed first, we have: $$\frac{n!(2n-2k)!}{2^{n-2k}\times(n-k)!^2}$$ways of doing so. This is $2n$ times the case with $n$ weights and weight $k$ placed first. Therefore, we have $f(n+1) = f(n) + 2nf(n) = (2n+1)f(n)$, completing the induction.

overcomplicated Let $X_n$ denote the number of ways to place the weights $2^0, 2^1, \ldots, 2^{n-1}$ on the balance. I claim that the follow recursion holds true: $$X_n = \sum^n _{k = 1} \left(\dbinom{n-1}{k-1} X_{k-1} (n-k)! \cdot 2^{n-k}\right).$$To prove this, perform casework on when the $2^{n-1}$ weight is placed on the balance. The base case $X_1 = 1$ is trivial to see. Suppose the weight is placed $k^{\text{th}}$ (in other words, $k-1$ weights are placed before the $2^{n-1}$ weight). First, we choose the $k-1$ weights to be placed before the $2^{n-1}$ weight. There are obviously $\tbinom{n-1}{k-1}$ ways to do this. Now, notice that there are $X_{k-1}$ ways to place these $k-1$ weights onto the balance. After the $2^{n-1}$ weight is placed, the left side of the balance will remain heavier than the right side no matter what. Thus, there are simply $(n-k)!$ ways to determine the order of the remaining weights and $2^{n-k}$ ways to determine each weight's side on the balance. Putting it all together, there are$$\dbinom{n-1}{k-1}X_{k-1} (n-k)!\cdot 2^{n-k}$$ways to place the weights if the largest weight is placed $k^{\text{th}}$. This gives us the desired recursion. Now, I will show that $X_n = (2n-1)!!$ with induction. The base case, $X_1 = 1$, is trivial. Our recursion tells us that\begin{align*} X_{n+1} &= \sum^{n+1} _{k = 1} \dbinom{n}{k-1} X_{k-1} (n-k+1)! \cdot 2^{n-k+1}\\ &= \sum^{n} _{k = 1} \left(\dbinom{n}{k-1} X_{k-1} (n-k+1)! \cdot 2^{n-k+1}\right) + \dbinom {n}{n} X_n 0!\cdot 2^0\\ &=\sum^{n} _{k = 1} \left(\dbinom{n}{k-1} X_{k-1} (n-k+1)! \cdot 2^{n-k+1}\right) + X_n \end{align*}Writing $\tbinom{n}{k-1}$ as $\frac{n!}{(k-1)!(n-k+1)!}$, we have \begin{align*} X_{n+1} &=\sum^{n} _{k = 1} \left(\frac{n!}{(k-1)!(n-k+1)!} X_{k-1} (n-k+1)! \cdot 2^{n-k+1}\right) + X_n\\ &=\sum^{n} _{k = 1} \left(\frac{n!}{(k-1)!(n-k)!} X_{k-1} (n-k)! \cdot 2^{n-k+1}\right) + X_n\\ &=\sum^{n} _{k = 1} \left(2n\cdot\frac{(n-1)!}{(k-1)!(n-k)!} X_{k-1} (n-k)! \cdot 2^{n-k}\right) + X_n\\ &=2n\sum^{n} _{k = 1} \left(\frac{(n-1)!}{(k-1)!(n-k)!} X_{k-1} (n-k)! \cdot 2^{n-k}\right) + X_n\\ &=2n\sum^{n} _{k = 1} \left(\dbinom{n-1}{k-1} X_{k-1} (n-k)! \cdot 2^{n-k}\right) + X_n\\ &=2n\cdot X_n + X_n\\ &=(2n+1)\cdot X_n\\ \end{align*}However, from the inductive hypothesis, we know that $X_n = (2n-1)!!$, so $X_{n+1} = (2n+1)!!$, as desired. This completes our induction, so $X_n = (2n-1)!!$. $\blacksquare$

We will show that $\boxed{(2n - 1)!!}$ is our answer. $\newline$ Claim: Let $x_n$ be the number of ways to place the weights. Then $x_{n} = (2n - 1)x_{n-1}$. Proof: Notice that the placement of the smallest weight doesn't impact the scale, unless it is placed on the right pan, on the first turn(in which case, the right pan is heavier than the left pan.) So, there are $(2n - 1)$ ways to place the smallest weight, and $x_{n-1}$ ways to place the other weights(by scaling by a factor of $\frac{1}{2})$. Hence, there are $(2n - 1)x_{n-1}$ ways to place the weights. $\newline$ We can rewrite $(2n - 1)x_{n-1}$ as \[\prod_{k=0}^{n-1} 2k + 1 = (2n = 1)!!\]so we are done.

Let $N(n)$ denote the number of ways to place $n$ weights of the given form satisfying all the desired conditions. We make the following observation. Note that for the smallest weight, it doesn't matter where it is placed unless it is placed on the left pan on the first move. This is because the sum of $L-R$ is clearly even, and if it is positive (as we require) then it is at least 2. Thus, adding one will still ensure this difference stays positive. Thus, it can be placed in $2n-1$ ways. Further, once the smallest number is placed, the number of ways to place the others is simply $N(n-1)$ since these weights $2^1,2^2,\dots,2^n$ are simply the previous weights $2^0,2^1,\dots,2^{n-1}$ scaled up by 2. Thus, \[N(n)=(2n-1)N(n-1)\]Clearly, $N(1)=1$ (just place the only weight on the left pan). Thus, by a simple induction we obtain that \[N(n)=(2n-1)!!\]for all positive integers $n$.

For a set of nonnegative integers $a_1 < a_2 < \dots a_n$, define $f(a_1, a_2, \dots, a_n)$ as the number of ways to place weights weighing $2^{a_1}, 2^{a_2}, \dots, 2^{a_n}$ on the scale subject to the conditions of the problem. Observe that $2^{a_1} + 2^{a_2} + \dots + 2^{a_{n - 1}} < 2^{a_n}$, hence the moment we place the weight weighing $2^{a_n}$ on the left pan it does not matter how we place the rest. From here, it is not hard to find the recursion $$f(a_1, a_2, \dots, a_n) = \sum_{X} f(X) \cdot \left(n - 1 - |X| \right)! \cdot 2^{n - 1 - |X|}$$where $X$ runs through all subsets of $\{a_1, a_2, \dots a_{n - 1} \}.$ The latter subset corresponds to the weights we place on the pan before the weight weighing $2^{a_n}$. Claim 1: For a nonnegative integer $n$, for all sets $|X| = n$, $f(X)$ has a common value. To prove, we use strong induction on $n$. The case of $n = 0$ is vacuously true (Common value is $1$), and for $n = 1$ we have $f(a_1) = 1$ no matter what $a_1$ is. Now assume the claim is true for integers $1 \le n \le k$. It is not hard to see that using the recursion derived earlier, all sets $|X| = k + 1$ yield a common value for $f(X)$. To finish, suppose $t(n)$ is the common value of all $f(X)$ where $|X| = n$. We have $t(n) = \sum_{k = 0}^{n - 1} \binom{n - 1}{k} \cdot \left(n - 1 - k \right)! \cdot 2^{n - 1 - k} \cdot t(k).$ From here we can extract the general form $t(n) = \boxed{(2n - 1)!!}$.

We claim the answer is $\boxed{(2n-1)!!}$, which we prove inductively. The base case is trivial, and casework on the first element tells us our answer is \begin{align*} a_n &= \sum_{k=0}^n \left(\frac{n!}{(n-k)!} \cdot 2^k \cdot a_{n-1-k}\right) \\ &= (2n-3)!! + 2n \sum_{k=0}^{n-1} \left(\frac{(n-1)!}{((n-1)-k)!} \cdot 2^{k-1} \cdot (2(n-1)-2k-1)!!\right) \\ &= (2n-3)!! + a_{n-1} \\ &= (2n-1)!!. \quad \blacksquare \end{align*}

We claim the answer is $\boxed{(2n-1)!!}$. Note that instead of comparing the sum of weights on each side, it is equivalent to compare the largest weight on each side. Let $a_n$ denote the number in question. If $1$ is placed first, there are $a_{n-1}$ ways to place the rest of the weights. Otherwise $1$ can be placed at $n-1$ different steps, and it has $2$ choices at each of these steps. The rest of the weights can be placed in $a_{n-1}$ ways. Thus $a_n=(2n-1)a_{n-1}$ and the conclusion immediately follows. $\square$

Note: assume that $(-1)!!=1$ Let there be $k$ items before the $2^{n+1}$ is placed The number of ways is ${n-1 \choose k}*f(k)$ before the $2^{n-1}$ because choose $k$ items and then to do the $k$ items is $f(k)$ ways. Then multiply by $1$ for the $2^{n-1}$. Then multiply by $(n-1-k)!*2^{n-1-k}$ because for the rest of the items anything can happen. So it is the sum of ${n-1 \choose k}*f(k)*(n-1-k)!*2^{n-1-k}=(n-1)!*2^{n-1}*\frac{f(k)}{k!2^k}=(2n-2)!!*\frac{f(k)}{(2k)!!}$ for all values of $k$. Use induction to prove that $f(n)=\boxed{(2n-1)!!}$ for positive $n$ and $1$ for $n=0$ Base case: $f(0)=1, f(1)=1$ induction: Assume it works for all $k$ from $0$ to $n$. $f(n)=(2n-1)!!=(2n-2)!!*\sum_{k=0}^{n-1} (\frac{(2k-1)!!}{(2k)!!})$ $f(n+1)=2n(2n-2)!!*(\sum_{k=0}^{n-1} (\frac{(2k-1)!!}{(2k)!!})+\frac{(2n-1)!!}{(2n)!!}) = 2n((2n-1)!!+\frac{(2n-1)!!}{2n})=(2n+1)(2n-1)!!=(2n+1)!!$

Consider the grid with $2$ columns and $n$ rows. The rows represent the order we out the weights on (with the weights on the top row getting placed first) and the two columns representing whether we put it on the left or right pan. Consider placing the weights on the grid one by one from lightest to heaviest. Since we are going lightest to heaviest, we can't put the current weight on the first open row in the right column. Once we've placed $k$ weights, we've taken up $k$ rows (and thus $2k$ spots) and an extra $1$ spot due to the above paragraph. Thus, multiplying gives an answer of \[\prod_{i = 0}^{n-1} (2n-2i-1) = \boxed{(2n-1)!!}\]where we used a double factorial.

Let the answer for $n$ weights be $f(n)$. I claim $f(n) = (2n - 1)!!$. Observe we are just being asked to find the number of ways of putting the weights on the balance such that the maximum weight placed is always on the left side (since the place where the maximum weight is placed is always heavier, since $2^{n} > 2^{n } - 1 > 2^{n - 1} + \cdots + 1$). Claim: $f(n) = \sum_{i = 0}^{n - 1} 2^{n - 1 - i} \frac{(n - 1)! }{(n - 1 - i)!} f(i)$. Proof: Place the heaviest weight in the $i + 1$th position. Then there are $\frac{(n - 1)!}{(n - 1 - i)!}$ to select and permute the elements after it, $2^{n -1 - i}$ ways to assign them to the balance. For the weights before, we have a working configuration if and only if the maximum weight placed is always on the left side, so the number of ways to assign that is $f(i)$. Combining the terms over all $i$ gives the desired summation. Now observe $f(0) = f(1) = 1$, we now prove inductively that $f(n) = (2n - 1)!!$ for $n > 1$. Observe that $f$ is uniquely determined by this recursion, so we show that this solution indeed works. Note that $(1)!! = 2^{0} \frac{0!}{0!} (-1)!! = \sum_{i = 0}^{1 -1} 2^{1- i - 1} \frac{(0!)}{(0 - i)!} (-1)!!$, so we use this as a base case to inductively prove $(2n -1)!! = \sum_{i = 0}^{n - 1} 2^{n - 1 - i} \frac{(n - 1)! }{(n - 1 - i)!} (2i - 1)!! $. For the inductive step, just multiply both sides by $2n$ and add $(2n - 1)!!$. The left side becomes $(2n + 1)!!$, the right side becomes $2^{0} \frac{n!}{n!} (2n -1)!! + \sum_{i = 0}^{n - 1} 2^{n - i} \frac{n!}{(n - 1 -i)!} (2i - 1)!! = \sum_{i = 0}^{n} 2^{n - i} \frac{n!}{(n - i)!} f(i)$ as desired.

Let the answer be $P(n)$ for $n$ weights. At some point with $n$ weights, note that we can ignore the $2^0$ weight because it does not affect anything, except at the first step. This is because after taking at least $2$ steps the positive difference between the two sides will be at least $2,$ and thus $1$ cannot change the sign of this difference. Therefore if $2^0$ is placed on the first step, it can only be placed on the left pan. Otherwise, it can be placed on any of the two pans, thus there are $2(n-1)+1=2n-1$ placed to put it. Therefore, $P(n)=(2n-1)P(n-1).$ Since $P(1)=1,$ we can easily obtain that $$P(n)=(2n-1)!!,$$which is the answer.