How to solve this combination?

Question

I have $8$ pieces and $8$ places to put them into. I want to know how to calculate the number of possible combinations. The places are like this : $[a,b],[c(d,e),f(g,h)]$

$[a,b]$ is the same as $[b,a]$ and $(d,e)$ is the same as $(e,d)$

$[c(d,e),f(g,h)]$ is the same as $[f(g,h),c(d,e)]$ but not $[f(d,e),c(g,h)]$

I apologize if it's unclear. I never read a math problem in English before so I can't express the way I want to.

I don't need the result, I just want to know how to approach this problem.

EDIT 1 : I understand. My question now is that if I had 16 positions and 16 pieces as follows $[a,b,c,d],[e(f,g),h(i,j),k(l,m),n(o,p)]$. Following the same rules, $N$ becomes $4^2*2^4 = 256$ and the result would be $16! / 256$, correct?

EDIT 2 : I made a mistake. If I have $[a,b,c,d]$ and swapping $a$, $b$, $c$ and $d$ will produce an equivalent expression, then $N$ won't be $4$ but rather $4!$. With the first edit's expression of 16 pieces we will have $N = 4! * 4! * 2^4$ and the result would be $16! / 9216 = 2270268000$

Answer 1

(Note: I'm not sure whether I understood your question correctly. Please don't hesitate to ask for clarification or point out mistakes; they might be a sign that I misunderstood the question.)

I say that $[a,b],[c(d,e),f(g,h)]$ and $[a,b],[f(g,h),c(d,e)]$ are different expressions (because they are written differently) but they are equivalent (because they are "same" as you said). An equivalence class is a set of expressions that are equivalent to each other, such that all expressions that are equivalent to one of them are included. Your question is to find the number of equivalence classes.

You have $8!$ ways to put the symbols $a,b,\dots,h$ into the expression $[X,X],[X(X,X),X(X,X)]$. This is the number of expressions, but however, some of the expressions are equivalent, so the number of inequivalent expressions you have is not $8!$.

First, we note that all equivalence classes have the same size: because no piece is special, there is no reason for one expression to have more expressions equivalent to it than another. Let us call the size of an equivalence class by $N$. Now, what is $N$?

If two expressions are equivalent, one can be obtained from the other by using some of the following operations: (Here, i denote by $X$ a position which I don't care about in the operation.)

1. Swap $A$ and $B$ in $[A,B],[X(X,X),X(X,X)]$
2. Swap $A(A,A)$ and $B(B,B)$ in $[X,X],[A(A,A),B(B,B)]$
3. Swap $A$ and $B$ in $[X,X],[X(A,B),X(X,X)]$
4. Swap $A$ and $B$ in $[X,X],[X(X,X),X(A,B)]$

Because each operation can either be completed or skipped, there are $2^4=16$ possible ways to obtain an equivalent expression starting from an expression (note: one of the possible ways is to do nothing!). Thus, each equivalence class has size $N=16$.

So, the number of equivalence classes is $8!/16 = 2520$.