# Math Help - graph clustering, clustering numbers

1. ## graph clustering, clustering numbers

hi every body.
i want to cluster a graph with n nodes to k clusters.

for example suppose that n=10, k=3. some different clustering could be:

clustering 1:
c1={n1,n2,n3} , c2={n4,n5}, c3={n6,n7,n8,n9,n10}

clustering 2:
c1={n1,n2,n10} , c2={n4,n5}, c3={n6,n7,n8,n9,n3}

clustering 3:
c1={n1,n2} , c2={n4,n5}, c3={n6,n7,n8,n9,n3,n10}

i want to know how many different clusters is possible?

2. I found a reference quoting that there are approximately $\frac{k^n}{k!}$ ways of partitioning n data points into k clusters, assuming hard partitioning.

3. Originally Posted by zareiramin
hi every body.
i want to cluster a graph with n nodes to k clusters.

for example suppose that n=10, k=3. some different clustering could be:

clustering 1:
c1={n1,n2,n3} , c2={n4,n5}, c3={n6,n7,n8,n9,n10}

clustering 2:
c1={n1,n2,n10} , c2={n4,n5}, c3={n6,n7,n8,n9,n3}

clustering 3:
c1={n1,n2} , c2={n4,n5}, c3={n6,n7,n8,n9,n3,n10}

i want to know how many different clusters is possible?

Is a cluster allowed to be empty? If we switch c1 and c2, do we get an equivalent or a distinct clustering?

Assuming that switching c1 and c2 produces an equivalent clustering, what you are doing is equivalent to placing n distinguishable objects into k indistinguishable bins. There is more info here

http://www.johndcook.com/TwelvefoldWay.pdf

4. Originally Posted by undefined
Is a cluster allowed to be empty? If we switch c1 and c2, do we get an equivalent or a distinct clustering?

Assuming that switching c1 and c2 produces an equivalent clustering, what you are doing is equivalent to placing n distinguishable objects into k indistinguishable bins. There is more info here

http://www.johndcook.com/TwelvefoldWay.pdf

a cluster can not be empty and switching c1 and c2 leads same clustering.
I found a reference quoting that there are approximately $\frac{k^n}{k!}$ ways of partitioning n data points into k clusters, assuming hard partitioning.