document.write( "Question 1208190: Let S={1,2,3,4,…,n}, and let A and B be two subsets of S such that A ≠ ∅, B ≠ S, and A ⊆ B.
\n" ); document.write( "Calculate the number of ordered pairs (A,B) for all subsets of the set S \n" ); document.write( "

Algebra.Com's Answer #846439 by ikleyn(52803) $\"\"$ $\"About$

You can put this solution on YOUR website!
.
\n" ); document.write( "Let S={1,2,3,4,…,n}, and let A and B be two subsets of S such that A ≠ ∅, B ≠ S, and A ⊆ B.
\n" ); document.write( "Calculate the number of ordered pairs (A,B) for all subsets of the set S.
\n" ); document.write( "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "Set S contains n distinguishable elements.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Let m be an integers number 0 <= m <= n. \r\n" );
document.write( "\r\n" );
document.write( "The number of different subsets B in S, consisting of m elements, is .\r\n" );
document.write( "\r\n" );
document.write( "    Notice that in this formula, I admit B = S.  This case will be excluded later.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, for given integer m between 1 and n, we can choose subset B in  different ways.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Let B is one such selected set of m elements.\r\n" );
document.write( "\r\n" );
document.write( "The number of all different subsets A in B is .\r\n" );
document.write( "\r\n" );
document.write( "    Notice that in this formula, I admit A = ∅.  This case will be excluded later.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Having this, we conclude that the number of all pairs (A,B), where A is a subset in B, is the sum of products\r\n" );
document.write( "\r\n" );
document.write( "    .\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "This sum is REMARCABLE.  It is nothing else as  .  \r\n" );
document.write( "Indeed, this sum is a binomial expansion/decomposition of  ,  which can be folded back\r\n" );
document.write( "\r\n" );
document.write( "     =  = .\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "OK.  It is the major idea and the major breakthrough. At this point, the problem is almost fully solved.  \r\n" );
document.write( "To fully complete the solution, we only need to exclude all pairs  (A,B),  where B = S  or  A = ∅.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The number of pairs (A,S) is the same as the number of all subsets A in S: it is  , including subset  (∅,S).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The number of pairs (∅,B) is the same as the number of subsets B in S: it is    again, including subset (∅,S).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, when we exclude the prohibited pairs, we will get\r\n" );
document.write( "\r\n" );
document.write( "    the number of all pairs under the problem's question is   -  -  + 1 =  -  + 1.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "I added 1 to compensate the fact that above I excluded the pair (∅,S) twice.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "ANSWER.  The number of all pairs under the problem's question is   -  + 1.\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "Now the problem is solved completely.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Nice Math Olympiad level problem.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );