2
$\begingroup$

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?

$\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 Sawin
    May 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$ May 8, 2014 at 18:53
  • $\begingroup$ @Will: I guess you mean $>$ instead of $\ge$. $\endgroup$ May 8, 2014 at 18:57

1 Answer 1

2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.