Ways to partition [n] (the power set of n)

**oldguynewstudent** · June 24th 2010, 07:51 PM

How many partitions of [n] into two blocks are there? How many partitions of [n] into n-1 blocks are there?

There are $\sum_{k=1}^{floor(\frac{n}{2})}\left({n\atop k}\right)$ partitions of [n] into two blocks (floor(n/2) is the greatest integer less than or equal to (n/2)).

There are $\left({n\atop n-2}\right)$ partitions of [n] into n-1 blocks.

Did I get this one correct?

**chiph588@** · June 24th 2010, 08:08 PM

Originally Posted by oldguynewstudent

How many partitions of [n] into two blocks are there? How many partitions of [n] into n-1 blocks are there?

There are $\sum_{k=1}^{floor(\frac{n}{2})}\left({n\atop k}\right)$ partitions of [n] into two blocks (floor(n/2) is the greatest integer less than or equal to (n/2)).

There are $\left({n\atop n-2}\right)$ partitions of [n] into n-1 blocks.

Did I get this one correct?

Stirling numbers of the second kind - Wikipedia, the free encyclopedia

(I've actually done research on this topic!)

**undefined** · June 24th 2010, 08:10 PM

Originally Posted by oldguynewstudent

How many partitions of [n] into two blocks are there? How many partitions of [n] into n-1 blocks are there?

There are $\sum_{k=1}^{floor(\frac{n}{2})}\left({n\atop k}\right)$ partitions of [n] into two blocks (floor(n/2) is the greatest integer less than or equal to (n/2)).

There are $\left({n\atop n-2}\right)$ partitions of [n] into n-1 blocks.

Did I get this one correct?

What do you mean by "power set of n"? An example of a power set is:

$A=\{1,a\}$

$\mathcal{P}(A)=\{\emptyset,\{1\},\{a\},\{1,a\}\}$

I've noticed in the past you used [n] to mean $\{1,2,\dots,n\}$ . So, what are we talking about here?

**oldguynewstudent** · June 25th 2010, 04:37 AM

Originally Posted by undefined

What do you mean by "power set of n"? An example of a power set is:

$A=\{1,a\}$

$\mathcal{P}(A)=\{\emptyset,\{1\},\{a\},\{1,a\}\}$

I've noticed in the past you used [n] to mean $\{1,2,\dots,n\}$ . So, what are we talking about here?

OOOPS, I was tired. Yes I meant the second. $\{1,2,\dots,n\}$ .

**awkward** · June 25th 2010, 02:21 PM

Originally Posted by oldguynewstudent

How many partitions of [n] into two blocks are there? How many partitions of [n] into n-1 blocks are there?

There are $\sum_{k=1}^{floor(\frac{n}{2})}\left({n\atop k}\right)$ partitions of [n] into two blocks (floor(n/2) is the greatest integer less than or equal to (n/2)).

There are $\left({n\atop n-2}\right)$ partitions of [n] into n-1 blocks.

Did I get this one correct?

I don't think you have the first one quite right. Consider what happens when n is even. How many partitions of [n] are there into sets of size n/2?

**oldguynewstudent** · June 25th 2010, 02:40 PM

Originally Posted by awkward

I don't think you have the first one quite right. Consider what happens when n is even. How many partitions of [n] are there into sets of size n/2?

Yes, I saw the post about Stirling numbers of the second kind. The formula worked for 5 but not for 6. Funny that the problem was 3 sections ahead of Stirling numbers of the second kind!

Thread: Ways to partition [n] (the power set of n)

LinkBack

Thread Tools

Display

Ways to partition [n] (the power set of n)

Similar Math Help Forum Discussions

partition help

How many ways to partition N (identical) items into at most K groups?

partition of unity

Partition

Partition help!!!

Search Tags