MHB What Are Non-Crossing Partitions and How Are They Defined?

  • Thread starter Thread starter alyafey22
  • Start date Start date
  • Tags Tags
    partitions
AI Thread Summary
Non-crossing partitions are defined as partitions of a set where no two blocks intersect each other, meaning that if elements a and b are in one block and elements x and y are in another, they cannot be arranged in a crossing order like a x b y. The number of non-crossing partitions is calculated using Catalan numbers, contrasting with regular partitions, which are counted by Bell numbers. Visual representations help clarify the concept, illustrating how arches drawn between elements can indicate crossing or non-crossing arrangements. The discussion highlights the need for a clear mathematical definition alongside verbal explanations. Overall, the conversation emphasizes the importance of understanding both the visual and formal aspects of non-crossing partitions.
alyafey22
Gold Member
MHB
Messages
1,556
Reaction score
2
Define a partition of a set $S$ as a collection of non-empty disjoint subsets $\in S$ whose union covers $S$. The number of them is defined using the Bell numbers.

Can we define ''Non-crossing'' partitions in words . I have seen the visualization of these partitions and the number of them is calculated using the Catalan's numbers.
 
Physics news on Phys.org
In the wiki, it says that a noncrossing partition
is a partition in which no two blocks "cross" each other, i.e., if a and b belong to one block and x and y to another, they are not arranged in the order a x b y. If one draws an arch based at a and b, and another arch based at x and y, then the two arches cross each other if the order is a x b y but not if it is a x y b or a b x y. In the latter two orders the partition { { a, b }, { x, y } } is noncrossing.
There's a nice picture illustrating noncrossing partitions.
 
Ackbach said:
In the wiki, it says that a noncrossing partition There's a nice picture illustrating noncrossing partitions.

Yes, I already saw this . But I am surprised to know that this is the only explanation! I mean it should have a mathematical definition '' can be described by words '' .
 
Is the part I quoted not in words? Is it an adequate definition? These are not rhetorical questions, but genuine.
 
Ackbach said:
Is the part I quoted not in words? Is it an adequate definition? These are not rhetorical questions, but genuine.

I actually meant something else .But now I got the general idea , thanks .
 

Thread 'Deductive proof in logic formal systems'

I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
View full post »

Similar threads

MHB Show that the set is a partition of A
Replies
1
Views
2K
Examples of Partitions: How to Divide Nonzero Integers into Infinite Sets?
Replies
5
Views
2K
A Maybe it is not necessary to define set membership?
Replies
13
Views
1K
A Number of particles in canonical ensemble
Replies
9
Views
2K
Partition Definition: What is a Partition?
Replies
1
Views
2K
Proof of Partition Property for Subset A in Universal Set U
Replies
1
Views
1K
I Stochastic Minimax partition problem card game
Replies
5
Views
2K
I Two basic results from measure theory -- on volumes of rectangles
Replies
2
Views
2K
I Ways to put n balls in m boxes such that exactly k boxes are empty?
Replies
29
Views
3K
Proof involving partitions and equivalence class
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top