Combinatorics - Arrangements of 48 Staves of a Barrel (allowing each stave to flip)

Question

How many ways are there to arrange the $48$ staves of a barrel where each stave has 2 states, upside up or upside down.

If the staves couldn't flip, then it would just be $\frac{48!}{48}=47!$
This would be arranging n people in a circle which I remember being $\frac{n!}{n}=(n-1)!$

I initially thought it would be $2*48!$ to allow staves to have an up & down side, but that's way too small and I also wasn't thinking of the circular part of the problem.

I also thought of $(2*48)!=96!$
But that seems to overcount since you only have $48$ staves and this way it allows you to put the same stave next to itself (once in its up position & once in its down position). But I know that each stave has $2$ states, that doesn't translate to $96$ things to arrange, because once you place the 1st stave, you only have $47$ left.
(And it's also ignoring the circular part.)

Answer 1

I have a specific answer to the $48$ staves problem $$ 47!*2^{47} $$ As well as a general formula which I'm pretty sure accounts for arranging in a circle $$ \frac{n!}{n}*\frac{2^n}{2} = (n-1)!*2^{n-1} $$

Explanation

---

First, imagine we are just arranging $n$ things (ignore flipping staves and the circle aspect) When $n=3$, there are $6!=6$ ways to arrange $3$ staves labeled A, B & C

A  B  C
A  C  B
B  A  C
B  C  A
C  A  B
C  B  A

Now I'll let A' be the down state & A be the up of a stave
For each of the $6$ simple arrangements, we now need to allow each stave to flip
Let's just look at the very 1st arrangement: A B C

A  B  C 
A  B' C 
A  B  C'
A  B' C'
A' B  C 
A' B' C 
A' B  C'
A' B' C'

You can do the same thing allowing flips for the 2nd arrangement: A C B

A  C  B 
A  C' B 
A  C  B'
A  C' B'
A' C  B 
A' C' B 
A' C  B'
A' C' B'

Each of the $6$ original arrangements expands to $8$ when you allow flipping
$8=2^3$ which should make sense since we have $3$ staves and each has $2$ states (up or down)

So when $n=3$, we start with $3!=6$ initial arrangements, each multiplied by $8$ to allow flipping
$\quad 3!*2^3$
$=6*8$
$=48$
But this hasn't dealt with the fact that we are arranging in a circle

Accounting for The Circular Aspect

When we simply do $n!$, it overcounts
Each arrangement creates $n$ identical patterns because you could rotate $n$ places around the circle and it would still be the same arrangement
Take the "circle" of 3 staves (really a triangle) and just look at the arrangement A B C

  A
 / \
C — B

Imagine starting at any vertex and go clockwise until you come back to the starting vertex.

A  B  C
B  C  A
C  A  B

You get $3$ "arrangements", but they're treated as identical when arranging things in a circle
So you divide by $n$ (the number of vertices where you can start)
$\frac{n!}{n}=(n-1)!$

$\frac{3!}{3}=(3-1)!$
$\quad\, =2!$
$\quad\, =2$

Without flipping, you just have $6$ arrangements & divide by $3$ to account for the circle

But here we have $48$ arrangements to begin with (not $6$) before accounting for the circle
Here are all $48$ arrangements for $3$ staves
The numbers represent arrangements that are in a group & treated as identical

 1)  A  B  C            9)  B  A  C            1)  C  A  B 
 2)  A  B' C           10)  B  A' C            5)  C  A' B 
 3)  A  B  C'          11)  B  A  C'           2)  C  A  B'
 4)  A  B' C'          12)  B  A' C'           6)  C  A' B'
 5)  A' B  C           13)  B' A  C            3)  C' A  B 
 6)  A' B' C           14)  B' A' C            7)  C' A' B 
 7)  A' B  C'          15)  B' A  C'           4)  C' A  B'
 8)  A' B' C'          16)  B' A' C'           8)  C' A' B'

 9)  A  C  B            1)  B  C  A            9)  C  B  A 
11)  A  C' B            3)  B  C' A           13)  C  B' A 
13)  A  C  B'           5)  B  C  A'          10)  C  B  A'
15)  A  C' B'           7)  B  C' A'          14)  C  B' A'
10)  A' C  B            2)  B' C  A           11)  C' B  A 
12)  A' C' B            4)  B' C' A           15)  C' B' A 
14)  A' C  B'           6)  B' C  A'          12)  C' B  A'
16)  A' C' B'           8)  B' C' A'          16)  C' B' A'

There are only $16$ distinct groups
$\frac{48}{3}=16$
So even though there's the complication of allowing staves to flip, we still just divide by the $n$ staves we have to account for the circle

Edit: As pointed out by Ross Millikan, you need to divide by $2$ to account for flipping over the barrel yielding the same arrangement

This leads to the general formula: $\frac{n!}{n}*\frac{2^n}{2} = (n-1)!*2^{n-1}$

---

Verifying with $4$ Staves

The $*2^n$ pattern extends to $4$ staves & gave me a new way of thinking of factorial
Here's $3!$ again

A  B  C
A  C  B
B  A  C
B  C  A
C  A  B
C  B  A

Now for each of the $6$ arrangements, there are $4$ places to insert a new 4th stave

1. Before the 1st stave
2. Between the 1st & 2nd stave
3. Between 2nd & 3rd stave
4. After the 4th stave

Here's $4!=24$ showing where the 4th stave (labeled X) can be inserted into the $3!=6$ arrangements

X  A  B  C
X  A  C  B
X  B  A  C
X  B  C  A
X  C  A  B
X  C  B  A

A  X  B  C
A  X  C  B
B  X  A  C
B  X  C  A
C  X  A  B
C  X  B  A

A  B  X  C
A  C  X  B
B  A  X  C
B  C  X  A
C  A  X  B
C  B  X  A

A  B  C  X
A  C  B  X
B  A  C  X
B  C  A  X
C  A  B  X
C  B  A  X

Allowing flips, lets look at the 1st arrangement: X A B C

X  A  B  C
X  A  B' C
X  A  B  C'
X  A  B' C'
X  A' B  C
X  A' B' C
X  A' B  C'

X' A' B' C'
X' A  B  C
X' A  B' C
X' A  B  C'
X' A  B' C'
X' A' B  C
X' A' B' C
X' A' B  C'
X' A' B' C'

Notice how the first $8$ rows are the same as they are for $3$ staves if you ignore the X & just look at A, B, C and their flipped ' states
Allowing the 4th stave to flip doubles the $8$ arrangements we had from $3$ staves

This time $1$ arrangement expands to $16$ arrangements allowing flips
$16=2^4$ which follows the pattern: we have $4$ staves, each with $2$ states

So $4!*2^4$
Then divide by $n$ to account for the circle and divide by 2 to ignore flipping the barrel
$\quad \frac{4!}{4}*\frac{2^4}{2}$
$=3!*2^3$

Answer 2

If the staves are distinguishable, then after arranging the "first" stave, there are $47!$ ways to arrange the others around the barrel and $2^{48}$ ways to put each stave up or down. So the final counting gives $47!\cdot 2^{48}$ (divide this number by $2$ if the barrel can be turned over).

If the staves are identical the problem is a bit more complicated equivalent to count the numbers of necklaces (or bracelets if the barrel can be turned over) with two colors (two states) and $48$ beads.

Answer 3

Your $47!$ is correct for the arrangements of the staves around the barrel. Now does the barrel have a top? If so, each stave can go up or down for a factor $2^{48}$. If the barrel doesn't have a top you need to divide by $2$ (just like you divided by $48$ before) because the first stave sets which is the top.