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.
Calculate the number of ordered pairs (A,B) for all subsets of the set S.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


<pre>
Set S contains n distinguishable elements.


Let m be an integers number 0 <= m <= n. 

The number of different subsets B in S, consisting of m elements, is {{{C[n]^m}}}.

    Notice that in this formula, I admit B = S.  This case will be excluded later.


So, for given integer m between 1 and n, we can choose subset B in {{{C[n]^m}}} different ways.


Let B is one such selected set of m elements.

The number of all different subsets A in B is {{{2^m}}}.

    Notice that in this formula, I admit A = ∅.  This case will be excluded later.



Having this, we conclude that the number of all pairs (A,B), where A is a subset in B, is the sum of products

    {{{sum(C[n]^m*2^m, m=0,n)}}}.


This sum is REMARCABLE.  It is nothing else as  {{{3^n}}}.  
Indeed, this sum is a binomial expansion/decomposition of  {{{(1+2)^n}}},  which can be folded back

    {{{sum(C[n]^m*2^m, m=0,n)}}} = {{{(1+2)^n}}} = {{{3^n}}}.



OK.  It is the major idea and the major breakthrough. At this point, the problem is almost fully solved.  
To fully complete the solution, we only need to exclude all pairs  (A,B),  where B = S  or  A = ∅.


The number of pairs (A,S) is the same as the number of all subsets A in S: it is  {{{2^n}}}, including subset  (∅,S).


The number of pairs (∅,B) is the same as the number of subsets B in S: it is  {{{2^n}}}  again, including subset (∅,S).


So, when we exclude the prohibited pairs, we will get

    the number of all pairs under the problem's question is  {{{3^n}}} - {{{2^n}}} - {{{2^n}}} + 1 = {{{3^n}}} - {{{2*2^n}}} + 1.


I added 1 to compensate the fact that above I excluded the pair (∅,S) twice.


<U>ANSWER</U>.  The number of all pairs under the problem's question is  {{{3^n}}} - {{{2*2^n}}} + 1.
</pre>

Now the problem is solved completely.


Nice Math Olympiad level problem.