How many rearrangements of w are there How many of these rea

How many rearrangements of w are there? How many of these rearrangements are palindromes (i.e., read the same forwards as backwards)? How many pairs of subsets (A, B) of {1,2,...,n} are there which satisfy A subsetof B? How many lattice paths consisting of N and E steps are there from (0,0)

Solution

Problem 4: There are n elements in total i.e. from {1,2,3,...n},

There are three cases now for each element

Case 1: An element from {1,2,...,n} doesn\'t belong to any of the sets, in this case i.e. let us suppose the element 1 doesn\'t belong to any of the set

Case 2: An element belongs to B but doesn\'t not belong to A

In this case, the specific element 1 will only belong to B and will not belong to A

Case 3: An element belongs to both A and B

In this case, both the set will contain the element

Hence number of pair of subsets = (1+1+1)^n = 3^n(since there are three choices for each elements and there are a total of n elements in the set)