Coloring elements of $A_1, ..., A_m$ where $|A_i| = n$

49 Views Asked by At

Let $A_1, ..., A_m$ be separable $n$-elements sets. We color elements of these sets in use of $2$ colors, but we consider two coloring as the same if one we can get from other by changing order of sets and then permuting elements inside sets. Find number of different coloring.

After some trying I failed during construction of polyi approach for this task (I had a problem with describing elements of group $S_n \oplus S_m$.

My another observation is trivial but maybe helpful there: Due to conditions, we can color each set $A_i$ on $n+1$ ways (we can choose if $0,1,...,n$ balls inside sets are white, other will be blue). That approach solves:

permuting elements inside sets.

But I have no idea how to consider this statement:

if one we can get from other by changing order of sets

2

There are 2 best solutions below

0
On BEST ANSWER

Hint: consider $m \times n$ matrices with elements from $\{0,1\}$.

0
On

The only way I can think of to make sense of the coloring being closed under permutations of the sets is if all the sets are identical, $A_i = A_1,$ and then if the coloring must be consistently defined across all the sets, it would be equivalent to just define a coloring on a single set, which is boring, so I'll assume the coloring need not come from a single function $\bigcup_{i=1}^m A_i \to \{0,1\}.$ All this I say as a precursor to the answer to show why clarification is important.


Anyway, under that interpretation, you're just counting the number of non-decreasing sequences of length $m$ with elements from $\{0,1,2,\ldots,n\}.$ This is counted by "stars and bars" as $$\binom{m+n}{m}$$

On the other hand, if my interpretation I wrote above isn't what you meant, then all bets are off.