0

Divide the 14 elements {A, B, C, C, C, C, D, D, D, D, E, E, E, E} into 7 groups (one group all have two elements), and I want to find out how many kinds of methods there are without repetition.

I already know a mathematical way to solve the problem:

$$ \begin{array}{c} set=\{a,b,c,d,e\} \\ G=\prod \frac {1}{1-set(i)*set(j)} \\=\frac{1}{\left(1-a^2\right) \left(1-b^2\right) \left(1-c^2\right) \left(1-d^2\right) \left(1-e^2\right) (1-a b) (1-a c) (1-a d) (1-a e) (1-b c) (1-b d) (1-b e) (1-c d) (1-c e) (1-d e)} \end{array} $$

Then we expand the generating function g at the point $\{0,0,0,0,0\}$ into a multivariate Taylor series.

Where the index of $a$ is 1, the index of $b$ is 1, the index of $c$ is 4, the index of $d$ is 4, and the index of $e$ is 4, the coefficient of this term 96 is the desired result.

set = {a, b, c, d, e};
f = Times @@ 
  DeleteDuplicates[
   Flatten[Table[1/(1 - set[[i]]*set[[j]]), {i, 1, 5}, {j, 1, 5}]]]
SeriesCoefficient[f, {a, 0, 1}, {b, 0, 1}, {c, 0, 4}, {d, 0, 4}, {e, 
  0, 4}]

But I don't understand why its generating function is in this form. I hope you can give a detailed explanation and other related examples.

There may be some grammatical errors in the above problems. Please correct them.

Please correct GrammarMistakes
  • 399
  • 3
  • 16

1 Answers1

2

The non-rigorous intuition for what's going is:

Let $S=\{AA,AB,AC,...,DD,DE,EE\}$ be the set of 15 different 2-element groups, and call a multiset of elements of $S$ (such as a particular division of the given 14 elements into 2-element groups) an "arrangement". We can completely describe an arrangement by saying how many of each element of $S$ it has. E.g. $(AC,BC,CC,DD,DD,EE,EE)$ has 0 ABs, 1 AC, 0ACs, ..., 2 DDs, 0 DEs, 2 EEs.

Now imagine expanding the product $$\left((aa)^0+(aa)^1+(aa)^2+(aa)^3+\dots\right)\left((ab)^0+(ab)^1+(ab)^2+(ab)^3+\dots\right)\cdots\left((ee)^0+(ee)^1+(ee)^2+(ee)^3+\dots\right)$$ by just "multiplying it out" into a big sum. Each term of the result will correspond to choosing exactly one term from each of the 15 factors. This is the same as specifying an arrangement by choosing how many of each kind of group it has, and the term we end up with consists of the elements that the corresponding arrangement uses. For example, the arrangement $(AC,AC,BC,DD)$ corresponds to the term $(aa)^0(ab)^0(ac)^2(ad)^0(ae)^0(bb)^0(bc)^1(bd)^0(be)^0\cdots(dd)^1(de)^0(ee)^0=a^2bc^3d^2$.

If we then "combine like terms" of our big sum, we're effectively counting arrangements according to which multiset of underlying elements they use. In particular, the coefficient on $abc^4d^4e^4$ is the number of arrangements that use exactly the 14 elements in question.

The $G$ in your question is exactly the product above, after applying the geometric series formula $x^0+x^1+x^2+\ldots=\frac1{1-x}$ to each factor.

Karl
  • 11,446