Discussion:
Counting partition patterns of a set
Aldar C-F. Chan
2005-08-07 22:09:15 UTC
Raw Message
I have got the following problem. Does anybody know the
common methods used to solve this kind of problems? Or
where should I look up from?

Suppose I have a set X and partition it in different ways, say
P_1, P_2, ..., P_i,..., P_m. That is, each P_i is a distinct
partition of X. For any randomly selected subset of X, say
A \subset X, if I want to make sure X\A is equal to some
union of Y_i's where each Y_i is an element of the union of
P_1, ..., P_m. What is the minimum possible m for this to be
fulfilled? And how such a collection of partition patterns can
be found?

Thanks.
William Elliot
2005-08-09 04:39:14 UTC
Raw Message
Post by Aldar C-F. Chan
I have got the following problem. Does anybody know the
common methods used to solve this kind of problems? Or
where should I look up from?
Suppose I have a set X and partition it in different ways, say
P_1, P_2, ..., P_i,..., P_m. That is, each P_i is a distinct
partition of X. For any randomly selected subset of X, say
A \subset X, if I want to make sure X\A is equal to some
union of Y_i's where each Y_i is an element of the union of
P_1, ..., P_m. What is the minimum possible m for this to be
fulfilled? And how such a collection of partition patterns can
be found?
m = 1. P_1 { {x} | x in X }

Futhermore, unless for all x in X, some i with {x} in P_i,
there will be some subsets of X that can't be expressed
as a union of elements from the P_i's.