1

My maths background is not so strong, please go slowly.
Suppose I have 3 elements, which are A, B and C.
I want to find (1) the number of operations to perform to find (2) all possible clusters that can be formed out of the 3 elements.
For this example, after some attempts on a piece of paper, I get the following:
(ABC) -> 1 operation, 1 cluster
(A) (B) (C) -> 1 operation, 3 clusters
(AB) (C) -> 1 operation, 2 clusters
(AC) (B) -> 1 operation, 2 clusters
(BC) (A) -> 1 operation, 2 clusters
Therefore, I get 5 operations and 10 clusters.

Similarly, suppose I now have 4 elements, which are A, B, C and D.
Again, I want to find (1) the number of operations to perform to find (2) all possible clusters that can be formed out of the 3 elements.
For this example, after some attempts on a piece of paper again, I get the following:
(ABCD) -> 1 operation, 1 cluster
(A) (B) (C) (D) -> 1 operation, 4 clusters
(AB) (CD) -> 1 operation, 2 clusters
(AC) (BD) -> 1 operation, 2 clusters
(AD) (BC) -> 1 operation, 2 clusters
(ABC) (D) -> 1 operation, 2 clusters
(ABD) (C) -> 1 operation, 2 clusters
(ADC) (B) -> 1 operation, 2 clusters
(BCD) (A) -> 1 operation, 2 clusters
(AB) (C) (D) -> 1 operation, 3 clusters
(AC) (B) (D) -> 1 operation, 3 clusters
(AD) (B) (C) -> 1 operation, 3 clusters
(BC) (A) (D) -> 1 operation, 3 clusters
(BD) (A) (C) -> 1 operation, 3 clusters
(CD) (A) (B) -> 1 operation, 3 clusters
Therefore, I get 15 operations and 37 clusters.
(Note: I hope I did not miss any combination, if I did, please correct it.)

I will be grateful to anyone who can describe to me the general form to compute the number of operations and clusters for any number of elements. Thanks.

george24
  • 153

1 Answers1

2

Unfortunately, the answer to your problem is complicated. For three objects $A,B,C$, you did not count the "trivial" partition $(ABC)$. Similarly, for four objects, you did not count the trivial partition $(ABCD)$. You probably have good reason not to include the trivial partition.

If we do count the trivial partition, the total number of "operations" is the $n$-th Bell number $B_n$. For $n=3$ this is $5$, and for $n=4$ it is $15$. There is no simple formula for the Bell numbers, but the linked article will supply a lot of information.

Counting the clusters brings us to the Stirling Numbers of the Second Kind (please see Wikipedia). The number of partitions of an $n$-element set into $k$ parts is the Stirling number $S(n,k)$. (There are other notations.) Counting the trivial partition, which you don't, the total number of clusters is $\sum_{k=1}^n kS(n,k)$.

André Nicolas
  • 507,029
  • I have added the trivial partition as well, your comments are welcome. Suppose I have 6 elements, can you explain to me how this can be computed instead of listing down all possible combinations. – george24 Jan 29 '16 at 06:31
  • The linked article on the Bell numbers gives some ways of computing, and lists the first $18$ or so. We have $B_6=203$. As to $\sum_{k=1}^n S(n,k)$, I have not thought about simpler a simpler formula than summing. There are nice ways to compute the Stirling numbers of the second kind, and you can find tables that go some distance. Unfortunately, there is no known "closed form" for either the Bell numbers or the Stirling numbers. – André Nicolas Jan 29 '16 at 06:48
  • Thank you André you just saved me an enormous amount of time. I followed all your explanations and it worked! I would pay you a beer if I could :) – george24 Jan 29 '16 at 06:54
  • You are welcome. – André Nicolas Jan 29 '16 at 06:58