I have n sets and I want calculate all the combination such that there is just an element of every set in each combination.

How can I express this in a combination forumula?

Thanks.

=================

1

What exactly is meant by a “combination”? Secondly: are the nn sets disjoint?

– drhab

2 days ago

Disjoint sets with different cardinality

– NxA

2 days ago

=================

1 Answer

1

=================

∙\bullet For sets of the same cardinality:

Let m1,m2,…,mn{m_1, m_2, …, m_n} be your nn sets of mm elements each.

We want to pick one of mm elements, for every set mim_i, where 1≤i≤n 1 \le i \le n. Then there are mm possibilities for the first set, m possibilities for the second set, and so on. We can express this as

m×m×m×⋯×m⏟n times\underbrace{ m \times m \times m \times \cdots \times m}_{\text{n times}}

or

mn m^n

Hence, there are mnm^n possible combinations satisfying the given condition.

∙\bullet For sets of different cardinality:

The approach is similar, just as stated by @drhab:

If set ii has cardinality mim_i then there are m1m_1 possibilities for the first set, m2m_2 for the second, et cetera. That results in

m1×m2×⋯×mnm_1 \times m_2 \times \cdots \times m_n possibilities.

Sorry, I commited a mistake. The sets can have different cardinality. How can I consider this?

– NxA

2 days ago

@NxA In the line of this answer: if set ii has cardinality mim_i then there are m1m_1 possibilities for the first set, m2m_2 for the second, et cetera. That results in m1×m2×⋯×mnm_1\times m_2\times\cdots\times m_n possibilities.

– drhab

2 days ago

I would add the content of @drhab’s comment into your answer (attributed, of course), because comments can be deleted without history, but answer edits are retained.

– Brian Tung

2 days ago