7
$\begingroup$

This question has been asked in my exam and I have stuck. The question says:

Let $S=\{1,2,3,4,5,6\}$. The number of one-one functions $f$ defined from $S$ to $P(S)$, where $P(S)$ stands for power set of $S$, such that $f(n)\subset f(m)$ wherever $n<m$, is what?

My approach to the problem:
Since $1<2<3<4<5<6$, it implies $f(1)\subset f(2)\subset f(3)\subset f(4)\subset f(5)\subset f(6)$, i.e., function's value at lower element is proper subset of function's value at higher element. This constraint can be broken into cases:

(i) $n(f(1))=0,n(f(2))=1, n(f(3))=2, n(f(4))=3,n(f(5))=4, n(f(6))=5$

(ii) $n(f(1))=0,n(f(2))=1, n(f(3))=2, n(f(4))=3,n(f(5))=4, n(f(6))=6$

(iii) $n(f(1))=0,n(f(2))=1, n(f(3))=2, n(f(4))=3,n(f(5))=5, n(f(6))=6$

(iv) $n(f(1))=0,n(f(2))=1, n(f(3))=2, n(f(4))=4,n(f(5))=5, n(f(6))=6$

(v) $n(f(1))=0,n(f(2))=1, n(f(3))=3, n(f(4))=4,n(f(5))=5, n(f(6))=6$

(vi) $n(f(1))=0,n(f(2))=2, n(f(3))=3, n(f(4))=4,n(f(5))=5, n(f(6))=6$

(vii) $n(f(1))=1,n(f(2))=2, n(f(3))=3, n(f(4))=4,n(f(5))=5, n(f(6))=6$

Since $f(n)≠f(m)\iff n≠m$ because all images have different sizes, so function is one-one already. Now, if we make a function, say, by case (iii), then one such way is:

$f(1)=\phi, f(2)=\{3\}, f(3)=\{3,6\}, f(4)=\{1,3,6\}, f(5)=\{1,2,3,5,6\}, f(6)=\{1,2,3,4,5,6\}=S$.

There are $$^6C_0*^6C_1*^6C_2*^6C_3*^6C_5*^6C_6$$ ways possible alone in case (iii). Multiply and divide by $^6C_4$, we get: $$(\prod_{r=0}^{6}{^6C_r})*(\frac{1}{^6C_4})$$
For final answer, we add all the cases: $$(\prod_{r=0}^{6}{^6C_r})(\sum_{r=0}^6\frac{1}{^6C_r})$$
But the answer provided is $3240$, along with a very confusing solution, which is different from my answer. Please help.

$\endgroup$
4
  • $\begingroup$ Thanks for reminding. I edited it. $\endgroup$ Apr 14 at 3:05
  • 1
    $\begingroup$ Cases (ii) to (vi) each has $\frac{6!}2$ functions, while cases (i) and (vii) each has $6!$ functions. $\endgroup$
    – peterwhy
    Apr 14 at 3:15
  • $\begingroup$ For $n$ elements, $n!(2+\frac{n-1}{2})$ functions will satisfy, to generalize peterwhys comment, the pattern is easy to find with small $n$ cases first. $\endgroup$ Apr 14 at 4:19
  • $\begingroup$ What is your answer? $\endgroup$
    – TonyK
    Apr 14 at 15:57

2 Answers 2

5
$\begingroup$

As $f(1)\subsetneq f(2)\subsetneq... \subsetneq f(6)$, $|f(1)| = 0$ or $1$ and $|f(6)=5$ or $6$.

Now bear with me. Imagine we have a string of seven subsets in a strict hierarchy $A_o=\emptyset \subsetneq A_1=\{a\} \subsetneq A_2=\{a,b\} \subsetneq ..... \subsetneq A_6 =\{a,b,c,d,e\}\subsetneq =\{a,b,c,d,e,f\}=S$, where $a,b,c,d,e,f$ are just a distinct ordering of the six elements of $S$.

There are of course $6!$ such ways to make such a string.

Now $f(1)\subsetneq f(2)\subsetneq... \subsetneq f(6)$ must be part of one of these strings. The only issue is that one of the sets of the string is omitted. And there are $7$ ways to choose that.

But to claim there are $7\cdot 6!$ ways would be overcounting.

If you have as string with $A_k \subsetneq A_{k+1} = A_k\cup \{w\}\subsetneq A_{k+2}=A_k\cup\{w,v\}$ and you choose to omit $A_{k+1}$ so you jump from $A_k$ the $A_{k+2}=A_k\cup\{w,v\}$ that'd be the same result as if have and had $A_k\cup \{v\}$ as the intermediate set and you omitted that.

But this double counting does not occur if the omitted set is $\emptyset$ or $S$.

So the answer is $2\times 6! + 5\times \frac {6!}2= 6!(2+\frac 52)$.

....

We can test this easily with a smaller case $S=\{1,2,3\}$ and there being $3!(2 + \frac 22)$ functions.

If $f(1)\ne \emptyset$ for the six permutations $123,132,213,231,312,321$ we have the six functions:

$1\to \{1\};2\to \{1,2\};3\to\{1,2,3\}=S$
$1\to \{1\};2\to \{1,3\};3\to\{1,3,2\}=S$
$1\to \{2\};2\to\{2,1\};3\to\{1,3,2\}=S$
$1\to \{2\};2\to \{2,3\};3\to \{2,3,1\}=S$
$1\to\{3\};2\to \{3,1\};3\to \{3,1,2\}=S$
$1\to\{3\};2\to \{3,2\};3\to \{3,2,1\}=S$

If $f(3)\ne S$ then those same six permutations give us the following 6 functions

$1\to\emptyset;2\to\{1\};3\to\{1,2\}$
$1\to\emptyset;2\to\{1\};3\to\{1,3\}$
$1\to\emptyset;2\to\{2\};3\to\{2,1\}$
$1\to\emptyset;2\to\{2\};3\to \{2,3\}$
$1\to\emptyset;2\to\{3\};3\to \{3,1\}$
$1\to\emptyset;2\to\{3\};3\to \{3,2\}$.

If $f(1)=\emptyset; f(3)=S$ and $|f(2)|=2$ (that is we omit the singleton sets) then the three pairs of permutations $(123,213),(132,312),(231,321)$ give us the following $3$ functions

$1\to\emptyset; 2\to \{1,2\}; 3\to S$
$1\to \emptyset; 2\to \{1,3\}; 3\to S$
$1\to \emptyset; 2\to \{2,3\}; 3\to S$.

If $f(1)=\emptyset; f(3)=S$ and $|f(2)|=1$ (that is we omit the duo sets) then the three pairs of permutations $(123,132),(213,231),(312,321)$ yield the three functions:

$1\to\emptyset; 2\to \{1\}; 3\to S$
$1\to \emptyset; 2\to \{2\}; 3\to S$
$1\to \emptyset; 2\to \{3\}; 3\to S$.

That is $2\times 3! + (3+1-2)\times \frac {3!}2$ functions.

$\endgroup$
4
$\begingroup$

The mappings must be ordered by set inclusion within the power set of $n$ elements. Since $P(n)$ includes the null set, there are $n+1$ sizes of sets that the elements can map to, implying each mapping must skip a single size.

If we skip either size $0$ or $n$, we have $n!$ possible set inclusive orderings.

If we skip any intermediate size in the power set in the ordering, we have $n!/2$ set inclusive orderings.

Below, for $n=5$, the possible ways to create an ordering are listed for each possible skipped size in the ordering. The parentheses are indicating that the first of the two terms in parentheses is the level skipped, I elaborate on the calculation for those terms below.

Skip $0$: $5 \times 4 \times 3 \times 2 \times 1$

Skip $1$: $(5 \times 4) \times 3 \times 2 \times 1$

Skip $2$: $5 \times (4 \times 3) \times 2 \times 1$

Skip $3$: $5 \times 4 \times (3 \times 2) \times 1$

Skip $4$: $5 \times 4 \times 3 \times (2 \times 1)$

Skip $5$: $1 \times 5 \times 4 \times 3 \times 2$

In the Skip $1$ row, the first mapping is to the empty set, we skip sets with one element, and the next mapping is to a $2$-element set. There are $(5 \times 4)$ $2$-element sets, but within these we do not care about the order, so we divide by $2$. Hence for each row other than the first and last, we have $n!/2$ mappings.

This leads to the general formula for $n$ elements of $n!(2+\frac{n-1}{2})$. For $n=5$ this is $720$, for $n=6$ it is $3240$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .