Talk:Partition of a set

Displayed TeX whithin a link

I just included some displayed TeX within in a link, thus:

The [[integer partition | partition

:<math>etc. etc.</math>

of the integer]] n ...

It seems to work: you can click on the word partition, or on the displayed TeX, or on the following phrase, and get the integer partition page. Michael Hardy 20:07, 5 Feb 2004 (UTC)

Definition correct?

Is the definition of partition entirely correct / undisputed?

specifically I wonder about the requirement that the elements of the partition needing to be non-empty.

The definition given in Potter, M. "Set theory and its philosophy", ( 2004, Oxford University Press ), on p. 130 is:

"Definition. A collection B of subsets of A is a partition of A if each element of A belongs to exactly one element of B.

According to this definition, A is a partition of itself, since it certainly is a subset of itself, and furthermore { A, {null} } is also a partition of A - since there is no restriction on the elements being null.

This does not seem to quite capture the essence of partition to me, but it does seem a commonly used definition - ie see the MathWorld definition: http://mathworld.wolfram.com/SetPartition.html

so I'm wondering whether the article should be updated to clarify this ambiguity - that there are at least two alternate definitions being used.

--Corvi42 04:15, 10 Jun 2005 (UTC)

Ok, I went ahead and added a small addendum to axiom 1 saying that it is not included in all definitions.

Also, how is it that Axiom 1 can be vacuously true for the empty set - it contradicts Axiom 1!

--Corvi42 04:27, 10 Jun 2005 (UTC)

Again, I went ahead and corrected the erroneous example of the empty set, and added a few more examples. --Corvi42 15:02, 10 Jun 2005 (UTC)

You are wrong about the empty set. The partition with 0 blocks satisfies all the axioms including Axiom 1. --Zero 16:55, 10 Jun 2005 (UTC)

The partition P is a set of sets. In a set of sets there may be at most an occurrence of \emptyset . Allowing for no occurrences makes sense; otherwise for any partition with no empty set you would have one companion partition with one empty set, and this would not provide much more interest and breadth of application to the mathematical theory.

Mennucc (talk) 10:44, 25 March 2009 (UTC)[reply]

Something which currently is incorrect in this section, is the statement "This is equivalent to ...". The second "definition" is not equivalent to the first one. The first says "A partition is a set of nonempty subsets such that...". The second says, "A set of nonempty subsets is a partition if ...". Obviously, the two statements are not equivalent. For example, the second does not say anything about the set {{}}, which may not or may be a partition, according to this "definition". And also, if one of the following properties are not satisfied, the statement does not say whether we have a partition or not. — MFH:Talk 13:17, 20 September 2011 (UTC)[reply]

PS: I just made the necessary change to correct this. — MFH:Talk 13:23, 20 September 2011 (UTC)[reply]

Where does axiom 1 come from?

Just out of curiosity - where does axiom 1 come from? So far I haven't found any definition which has this axiom other than this page and other online definitions which are obviously copies of this page. The definition in Britannica doesn't include this restriction either: set partition

The first four books I pulled from my library shelves, all define a partition as a collection of non-empty sets:

Naive Set Theory, Paul Halmos
Set Theory and Logic, Robert R. Stoll
Axiomatic Set Theory, Patrick Suppes
Set Theory, Seymour Lipschutz

Counting Partitions

I was looking for a formula for the number of partitions of an n-element set into exactly k subsets each of size n/k, where k evenly divides n. For example, say you have 12 donuts, each a different kind; how many ways are there to divide them into four sets of three donuts to give to four cops? I couldn't find the answer, but derived the following, which I think is correct. I'm suggesting a notation here, too, along the lines of the "n choose k = _nC_k" notation. It might be nice to include this formula in the Counting section:

n\ partition\ k=\ _{n}\!T_{k}={\begin{bmatrix}n\\k\end{bmatrix}}={n! \over k!(({n \over k})!)^{k}}

The numerator is the number of ways to permute the order of the n-element set members, the first denominator term is the number of ways to permute the order of the resulting k subsets, and the second denominator term is the number of ways to permute the order of the members of the k subsets. Tedtoal (talk) 00:45, 1 July 2010 (UTC)[reply]

See Multinomial theorem#Ways to put objects into sized boxes. The connection between partitions and multinomial coefficients needs presentation in this article, though it needs care. For multinomial coefficients the order of the parts is significant but for partitions it is (usually) not significant. One can't in general just adjust the count by the factorial of the number of parts, though it is valid if empty parts are forbidden as they are here. Zero^talk 05:18, 3 July 2010 (UTC)[reply]

ME & CE

I added the line about ME and CE in the introduction. I see that there has been some discussion about the basic concept of partitioning here, so if this edit violates any of the more formal aspects of the definition please feel free to revert. capitalist 09:15, 19 October 2005 (UTC)[reply]

Improving readability

I've just completed various changes that I think make this article clearer. The only one I think the slightest bit controversial was deleting the material about the Faà di Bruno formula. I reduced it to an entry in See Also for two reasons. First, it was a verbatim repeat from the other article, and second, I couldn't figure out for the life of me what it was even trying to mean (OK, maybe I'm dense...) I'd suggest somebody who does get it ought to clarify the passage in the other article.—PaulTanenbaum (talk) 06:02, 20 March 2009 (UTC)[reply]

So "exhaustive" is redundant in "exhaustive partition"?

A partition covers the entire set, so it is exhaustive. If that is the case, we should not waste words and possibly create confusion by using the term "exhaustive partition".192.139.122.42 (talk) 20:54, 23 October 2012 (UTC)[reply]

Within the framework of set theory, I have never encountered the phrase ‘exhaustive partition’, and the article does not contain that phrase, as far as I can see. It only mentions the word ‘exhaustive’ in the lead section, where it is part of the definition: “More formally, these "cells" are both collectively exhaustive and mutually exclusive with respect to the set being partitioned.” — Tobias Bergemann (talk) 11:35, 24 October 2012 (UTC)[reply]

I think by "exhaustive partition" they may be referring to a power set, which is a set containing all possible subsets of the universal set.71.84.57.140 (talk) 02:23, 16 August 2013 (UTC)[reply]

Take a look at the use of the term in section 0.1.6 on page 7 of "Tensor Analysis on Manifolds" by Bishop and Goldberg. "For every equivalent relationship there is an exhaustive partition of P into disjoint subsets, the equivalence classes of E, for ..."

Noncrossing partition

Definition of noncrossing in this article is different from that in Noncrossing partition, in a way that they are not describing the same thing. Doyoon1995 (talk) 07:50, 15 July 2015 (UTC)[reply]

Fixed. -- Darij (talk) 02:02, 2 October 2017 (UTC)[reply]

Some clarity regarding empty set versus empty subset

The partition concept itself is somewhat confusing because it deals with sets on three or four levels:

The overall set of elements being considered: X
The set of elements in a subset of X: S1, S2, ... Si
The set of subsets making up a partition: P1, P2 etc. where perhaps P1 contains S1 and S4
The set of all possible partitions: PAll, containing P1, P2...Pn

This article could really benefit from additional distinction between these (levels of) sets.

For example, in the figure "The 52 partitions of a set with 5 elements" it would be helpful to point out certain important subtleties and resolve certain discrepancies:

1. The subsets are indicated by the colored blobs. So for example, in row 10 each partition is a set containing two subsets, where the subsets contain two or three elements. But...

In other rows where some dots are uncolored, are the uncolored dots considered to be an additional subset? That would be needed to fulfill the requirement $\bigcup _{A\in P}A=X$ . However, if that was the case, then, for example, the partitions in row 2 are the same as those in row 10. So is the figure incorrect?

2. The single partitions show in rows 1 and row 12: Are these actually the same partition? Or is row one actually depicting the partition having a single subset which is empty? But then what about $\bigcup _{A\in P}A=X$ ?

And on that score, it would be helpful to explicitly point out which of the following is allowed:

a. A partition having a single empty subset. Perhaps allowed only in the case where X is empty, since otherwise the partition wouldn't cover X?

b. A partition that has no subsets: Again, is this allowed only for empty X? Or never? Or?

c. What does $\emptyset \notin P$ actually mean? P is not allowed to be empty? Or P has no subsets that are empty? I think it's the latter, but then the later statement "The empty set has exactly one partition, namely the empty set" seems to violate that.

Hopefully someone with authoritative knowledge can clarify. Gwideman (talk) 15:54, 27 February 2016 (UTC)[reply]

Re c: It means that empty subsets are not allowed as components of the partition. The partition of the empty set has no components, so it meets this requirement. —David Eppstein (talk) 17:06, 27 February 2016 (UTC)[reply]

Ah, OK, so a partition having no (sub)sets is fine for an empty set X, but a partition having a single empty (sub)set is not. But I'm still puzzled about what the "52 partitions" figure is trying to depict with its first partition at the top. Maybe in this figure uncolored dots are supposed to represent subsets with single members? So the top partition contains five single-element subsets? Gwideman (talk) 17:45, 27 February 2016 (UTC)[reply]

Yes, in this image, when one of the dots is not surrounded by a colored region, then it is in a set by itself. —David Eppstein (talk) 18:15, 27 February 2016 (UTC)[reply]

Thanks, that key not-so-obvious point makes things fall into place. I've noted that in the caption. — Preceding unsigned comment added by Gwideman (talk • contribs) 19:31, 27 February 2016 (UTC)[reply]

Examples should be clarified

In the Examples section, it is written that "The set { 1, 2, 3 } has these five partitions:

{ {1}, {2}, {3} }, sometimes written 1|2|3.
{ {1, 2}, {3} }, or 12|3.
[…]

According to the Definition section above the Examples, however, if $A,B\in P$ and $A\neq B$ then $A\cap B=\emptyset$ . In this case, { {1}, {2}, {3} } $\neq$ { {1, 2}, {3} } and $A\cap B=$ {3}, which seems to be contradicting the definition.--Sae1962 (talk) 10:23, 10 February 2017 (UTC)[reply]

Two different items correspond to two different partitions. You cannot check the definition of a partition simultaneously on two different partitions. I have edited the article for clarification. D.Lazard (talk) 11:06, 10 February 2017 (UTC)[reply]

colors in chapters of the Tale of Genji

What does the red and green coloring mean in the image of the "chapters of the Tale of Genji"? Thanks in advacne. --Backinstadiums (talk) 09:12, 14 March 2018 (UTC)[reply]

This is explained in the file containing the image (click on the image). I have summarized the explanation in the caption. D.Lazard (talk) 09:28, 14 March 2018 (UTC)[reply]

@D.Lazard: could you please elaborate a bit what is represented? --Backinstadiums (talk) 18:56, 22 October 2018 (UTC)[reply]

A conjecture on partitions of $\{1,2,\cdots ,n\}$

For $p,q$ two partitions of $\{1,2,\cdots ,n\}$ , write $q\leq p$ if $p$ is finer than $q$ (or $q$ is coarser than $p$ ), meaning that each element of $p$ is a union of elements of $q$ .

Conjecture. For every partition $q$ of $\{1,2,\cdots ,n\}$ , we have

$\sum _{q\leq p}(-1)^{n-k}(p_{1}-1)!\cdots (p_{k}-1)!={\begin{cases}1,&{\text{if }}q=\{\{1\},\cdots ,\{n\}\};\\0,&{\text{otherwise}},\end{cases}}$

where each $p$ is a partition of $\{1,2,\cdots ,n\}$ into sets of size $p_{1},\cdots ,p_{k}$ .

Eg. For $n=5$ :

The partition $\{\{1,2\},\{3\},\{4\},\{5\}\}$ is coarser than itself and $\{\{1\},\cdots ,\{n\}\}$ , and the sum is indeed equal to 0;

The partition $\{\{1,2,3\},\{4\},\{5\}\}$ is coarser than itself, $\{\{1\},\cdots ,\{5\}\}$ , and 3 partitions like $\{\{1,2\},\{3\},\{4\},\{5\}\}$ , so the sum is $(-1)^{2}\times 2!+3(-1)^{1}\times 1+(-1)^{0}\times 1=0$ ;

The partition $\{\{1,2\},\{3,4\},\{5\}\}$ is coarser than itself, $\{\{1\},\cdots ,\{5\}\}$ , and 2 partitions like $\{\{1,2\},\{3\},\{4\},\{5\}\}$ , so the sum is $(-1)^{2}\times 1+2(-1)^{1}\times 1+(-1)^{0}\times 1=0$ ;

The partition $\{\{1,2,3\},\{4,5\}\}$ is coarser than itself, $\{\{1\},\cdots ,\{5\}\}$ , 3 partitions like $\{\{1,2\},\{3\},\{4,5\}\}$ , $\{\{1\},\{2\},\{3\},\{4,5\}\}$ , $\{\{1,2,3\},\{4\},\{5\}\}$ , and 3 partitions like $\{\{1,2\},\{3\},\{4\},\{5\}\}$ , so the sum is $(-1)^{3}\times 2!+3(-1)^{2}\times 1+(-1)^{2}\times 2!+4(-1)^{1}\times 1+(-1)^{0}\times 1=0$ ;

The partition $\{\{1,2,3,4\},\{5\}\}$ is coarser than anything containing $\{5\}$ , so there are 1 parititon of size 4+1, 4 of size 3+1+1, 3 of size 2+2+1, 6 of size 2+1+1+1, and 1 of size 1+1+1+1+1, so the sum is $(-1)^{3}\times 3!+4(-1)^{2}\times 2!+3(-1)^{2}\times 1+6(-1)^{1}\times 1+(-1)^{0}\times 1=0$ ;

And finally, the trivial partition is coarser than everything, so there are 1 partition of size 5, 5 of size 4+1, 10 of size 3+2, 15 of size 2+2+1, 10 of size 3+1+1, 10 of size 2+1+1+1, and 1 of size 1+1+1+1+1, so the sum is $(-1)^{4}\times 4!+5(-1)^{3}\times 3!+10(-1)^{3}\times 2!+15(-1)^{2}\times 1+10(-1)^{2}\times 2!+10(-1)^{1}\times 1+(-1)^{0}\times 1=0$ . 129.104.241.69 (talk) 22:37, 19 December 2024 (UTC)[reply]