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$
  • $\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 '14 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 Majer May 8 '14 at 18:53
  • $\begingroup$ @Will: I guess you mean $>$ instead of $\ge$. $\endgroup$ – Pietro Majer May 8 '14 at 18:57
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, privacy policy and cookie policy

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