A partition of $[n]$ is indecomposable if no subset of its blocks partitions $[k]$ with $k \in [n-1]$. Irreducible set partitions are defined at http://oeis.org/A055105 . Both are counted by http://oeis.org/A074664 . Is any bijection between them known?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ If I understand these correctly, indecomposable is, for each $k$, there exists a block which contains numbers both $\geq k$ and $\leq k$. Irreducible is, for each $k$, there exists a block that does not contain numbers both $\geq k$ and $\leq k$. And they are equinumerous? Interesting! $\endgroup$– Will SawinMay 8, 2014 at 17:48
-
$\begingroup$ For $n=3$, I see four irreducible partitions out of five, namely $\big\{\{1\},\{2\},\{3\}\big\}$, $\big\{\{1,2\},\{3\}\big\}$, $\big\{\{1,3\},\{2\}\big\}$, $\big\{\{1\},\{2,3\}\big\}$. But I only see two indecomposable partitions: $\big\{\{1\, 3\},\{2\}\big\}$, $\big\{\{1,2,3\}\big\}$. What am I missing? $\endgroup$– Pietro MajerMay 8, 2014 at 18:53
-
$\begingroup$ @Will: I guess you mean $>$ instead of $\ge$. $\endgroup$– Pietro MajerMay 8, 2014 at 18:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Mike Zabrocki has kindly addressed me to the following note http://www.billchen.org/publications/2011_P7_Unsplitable/2011_P7_Unsplitable.pdf where the bijection is built (here "atomic"="indecomposable" and "unsplittable"="irreducible"). Note that the correct version of the definition of splittable or reducible partition (page 3 on top) allows different lengths for the reducing partitions (a small but important detail that will be fixed in the OEIS link).