2
$\begingroup$

My question is closely related to this one. Suppose you have $n$ indistinguishable objects and and you want to merge them into $m$ indistinguishable objects. You may merge any number of objects into one at a given step. How many ways are there to merge them ?

I am not very familiar with combinatorics, I would really appreciate a detailed answer. Thanks!

$\endgroup$
  • $\begingroup$ Like the question you quote, I find this one, too, to be vague. Can you illustrate exactly what you mean, with, say, $n = 5, m= 2$ ? $\endgroup$ – true blue anil Oct 26 '16 at 3:57
  • $\begingroup$ Sure. For $5 \rightarrow 2$ We have the following: 1) $5\rightarrow 2 $ 2) $5 \rightarrow 3 \rightarrow 2 $ 3) $5\rightarrow 4 \rightarrow 2 $ 4) $5\rightarrow 4 \rightarrow 3 \rightarrow 2 $ So there are four possible ways of merging when going from 5 to 2 $\endgroup$ – user91411 Oct 26 '16 at 7:08
1
$\begingroup$

Anatoly has answered this, but I think it's worth expanding on how the answer is obtained. Since the objects are indistinguishable, it is impossible to say which objects get merged into which at each step. You can only say by how much the number of objects has been reduced in a given step. For a total reduction from five objects to two objects, as in your example in the comments, the number of objects needs to be reduced by three. This can be done (1) in one step, (2) by reducing first by $2$ and then by $1$, (3) by reducing first by $1$ and then by $2$, or (4) by reducing by $1$ in each of three separate steps. These correspond to the representations of $3$ as a sum of one or more non-zero integers: $$ \begin{aligned} 3&=3\\ &=1+2\\ &=2+1\\ &=1+1+1 \end{aligned} $$ These correspond to the dot patterns below. $$ \begin{aligned} &{\bullet}{\circ}{\circ}\\ &{\bullet}{\bullet}{\circ}\\ &{\bullet}{\circ}{\bullet}\\ &{\bullet}{\bullet}{\bullet} \end{aligned} $$ The rule for associating dot patterns with sums is that a new term in the sum starts with each solid dot. For a sum of $n$, there will be $n$ dots. The first dot is always solid. There are therefore $2^{n-1}$ dot patterns, and hence $2^{n-1}$ sums.

Added: There was a question in the comments about whether the set of compositions of $n$ has any sort of group structure. This answer improves on what was said in the comments. In the comments I made the unfortunate decision to define a poset and then a group using a diagram that appears in the Wikipedia article on compositions. Things would have worked much more neatly had I turned the diagram upside-down. In this answer I will do this—essentially redoing everything from scratch. The main changes are reversing the definition of less-than and reversing the identification of solid and open dots with $0$s and $1$s.

The set of compositions of $n$, ordered by refinement, is a poset. Given compositions $p$ and $q$, we say that $p<q$ if $q$ is a refinement of $p$, that is, if $q$ is obtained from $p$ by replacing one or more of the terms in $p$ by compositions of those terms. So we would say that $(1+1+3)>(2+3)$ since $(1+1+3)$ is obtained from $(2+3)$ by replacing $2$ with $1+1$. Similarly $(3+1+4+2+1+1)>(4+4+4)$ since the former is obtained from the latter by replacing the first $4$ with $3+1$ and the last $4$ with $2+1+1$. The refinement order relation is a partial but not a total order because some compositions are not comparable. For example $(1+2+1)$ is neither greater nor less than $(2+2)$.

As is usual with posets, we say that $y$ covers $x$ if $y>x$ and there is no $z$ in the poset such that $y>z>x$. The Hasse diagram of the poset is the graph in which the vertices are poset elements and edges are drawn between all $x$ and $y$ for which $y$ covers $x$. An example is shown below for the compositions of $4$. The diagram in the top left uses the standard representation of compositions; the one in the bottom left uses the dot representation; the one in the bottom right removes the first dot, which is always solid, and replaces solid and open dots in the remaining positions with $1$s and $0$s.

Hasse/Cayley diagrams for compositions

Focusing on the diagram in the bottom right, a group stucture becomes apparent. We can regard the diagram as the Cayley diagram of a group whose elements are patterns of $n-1$ bits and whose operation is exclusive or. The group has $n-1$ generators, corresponding to performing the exclusive or with the bit patterns $100\ldots0$, $010\ldots0$, $\ldots$, $000\ldots1$. The Cayley diagram is an $(n-1)$-dimensional hypercube, and the $n-1$ edge directions correspond to the generators of the group. The group is isomorphic to $$ (\mathbf{Z}/2\mathbf{Z})\times(\mathbf{Z}/2\mathbf{Z})\times\ldots\times(\mathbf{Z}/2\mathbf{Z}), $$ where there are $n-1$ factors in the direct product and $\mathbf{Z}/2\mathbf{Z}$ is the cyclic group of order $2$.

To understand the group structure in terms of compositions, we use an alternative representation of compositions in terms of their partial sums. The partial sums of a composition $p_1+p_2+\ldots+p_k=n$ are $0$, $p_1$, $p_1+p_2$, $p_1+p_2+p_3$, $\ldots$, $n$. Since the partial sums $0$ and $n$ occur in every composition of $n$, we omit these. We now identify a composition with the set of its remaining partial sums: $$ p_1+p_2+\ldots+p_k\leftrightarrow\{p_1,p_1+p_2,\ldots, p_1+p_2+\ldots+p_{k-1}\}. $$ The Hasse diagram for the poset in terms of this representation is shown in the upper right above. This is seen to be the poset of subsets of $\{1,2,\ldots,n-1\}$, orderd by inclusion. It can also be interpreted as the Cayley diagram of a group, where the group operation is the symmetric difference of two sets, $$ A\Delta B=(B\setminus A)\cup(A\setminus B)=(B\cap A’)\cup(A\cap B’). $$ In words, if a given partial sum is either present in both of two compositions or absent in both, then it will be absent in their symmetric difference; if it is present in one and absent in the other, then it will be present in their symmetric difference. The generators of the group are the operations of taking the symmetric difference with the singleton sets $\{1\}$, $\{2\}$, $\ldots$, $\{n-1\}$.

$\endgroup$
  • $\begingroup$ Will, thanks for your explanation. Apparently these things are called compositions and I assume that $1+2$ and $2+1$ can be viewed as different elements of the composition. Does this imply some sort of non-associativity in a way ? I would also appreciate if you could point out if there is any group structure related to the compositions. $\endgroup$ – user91411 Oct 30 '16 at 0:13
  • $\begingroup$ I believe that the way the terminology is used would require you to say that $1+2$ and $2+1$ are different compositions of $3$ rather than different elements of the composition. Compositions are lists, and two lists consisting of the same terms in a different order are different compositions, which is a form of noncommutativity. Your question about group structure is interesting. I had never thought about this before, but it turns out that, yes, there is at least one way to define a group structure. I believe it is more common to view the set of compositions as a poset rather ... $\endgroup$ – Will Orrick Oct 30 '16 at 3:21
  • $\begingroup$ ...than a group. What one could regard as the Hasse diagram of the poset is shown in the Wikipedia article, but one could equally regard it as the Cayley diagram of a group. If one does this, one is led to define a binary operation between compositions such that the resulting group for the compositions of $n$ is an abelian group isomorphic to $(\mathbf{Z}/2\mathbf{Z})\times(\mathbf{Z}/2\mathbf{Z})\times\ldots\times(\mathbf{Z}/2\mathbf{Z})$ (with $n-1$ factors). Here $\mathbf{Z}/2\mathbf{Z}$ is the cyclic group of order $2$. $\endgroup$ – Will Orrick Oct 30 '16 at 3:28
  • $\begingroup$ The binary operation is easiest to understand if one uses the dots representation in my answer. Stripping off the first dot, which is always solid, one interprets solid circles as $0$s and open circles as $1$s. The binary operation is then exclusive or. In terms of the compositions themselves, the binary operation is trickier to explain. Let us refer tothe binary operation as "addition" of compositions. Write a list of all the partial sums in a composition. So $1+2$ becomes $1,3$ and $2+1$ becomes $2,3$, while $1+1+1$ becomes $1,2,3$. The binary operation between... $\endgroup$ – Will Orrick Oct 30 '16 at 3:36
  • $\begingroup$ ...compositions works as follows: if a given partial sum is either present in both compositions or absent in both, then it will be present in their sum; if it is present in one and absent in the other, then it will be absent in their sum. So $(1+2)+(2+1)=(1,3)+(2,3)=(3)$ and $(1+2+1)+(3+1)=(1,3,4)+(3,4)=(2,3,4)=(2+1+1)$. I'm not sure what exactly this is useful for. I will have to think more. $\endgroup$ – Will Orrick Oct 30 '16 at 3:43
3
$\begingroup$

The searched number is equal to the total number of ways in which the difference $n-m \,$ can be expressed as a sum of positive integers. This corresponds to the number of compositions of $n-m \,$, which is $2^{n-m-1}$.

Accordingly, the example with $n=5$ and $m=2 \,$ stated in the comments leads to $2^{5-2-1}=4 \, \,$ possible ways.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.