Answer:
(a). The bride and groom may be arranged into a unit in 2! ways. This unit may now be arranged with 4 people chosen from the remaining 8 in 5! ways. Thus, the total number of ways of arranging 6 from 10 including the bride and groom is
.
(b). Choose the bride and 5 other people from among the remaining 9. This can be done in
ways. The chosen six may be arranged in 6! ways. Hence the answer is
.
(c). Choose the bride and the groom and 4 more people from the remaining 8. The selected 6 may be arranged in 6! ways. Ans:
.
(d). Choose one of bride or groom and ask the other to leave. Choose 5 more from the remaining 8 and arrange the chosen six. Ans:
.
Answer: The country code is a number between 0 and 999. This can be chosen inways. The 10-digit telephone number may be chosen in
ways, since the two N's are required to be non-zero digits. Hence, the answer is
.
Answer:
(a). Distributing 9 students among two sexes is the same as distributing Nine pigeons in Two holes.(b). If the number of students is at least three then the condition is already satisfied. If the number of males is less than three then the number of females has to be at least seven, since there are nine students in the calss.
Answer: Every subset should have either an odd or even number of elements. The odd integers less than
, are
. The even integers less than
, are
. The number of subsets with odd and even number of elements are therefore, respectively,
![]()
![]()
We have already seen that
![]()
Hence,
![]()
Since the total number of subsets is
it follows that the number of subsets with odd number of elements is equal to the number of subsets with even number of elements, namely
.
Use Pascal's identity to produce the row immediately following this row in Pascal's triangle.
Answer:
![]()
![]()
Answer:
There are 33 positive integers less than 100 which are divisible by 3. Hence the probability is.
Answer:.
Answer:.
Answer:.
Answer:.
Answer: The number of subsets of set containing n elements is the sum of number of subsets containing i elements forand there are
ways of selecting a subsets with i elements.
Answer: 4!.
Answer: The size of the sample space is the same as number of ordered ways of selecting with repetition 30 months from the 12 in a year. Imagine the following experiment: Have the months arranged in an order, say
![]()
Each person is now thrown into one of the months. For each person there are 12 choices. Since there are 30 persons in all, the total number of choices is
.
The number of ways of choosing six pairs and six triplets of people from 30 is
. Here, it is assumed that people with birthdays on the same month are indistinguishable from each other. One may check that
is the same as
![]()
We have now chosen 12 groups of people consisting of 6 pairs and 6 triplets. Let
and
be the groups of pairs of people, and
and
be the groups of triplets. These 12 groups are distinct from each other and in each group there is no ordering of people inside the group. If months are and groups are arranged in order,
![]()
then every permutation of the groups will produce a distinct matching of a month with a group. Every such matching will produce six months with 2 birthdays and six months with 3 birthdays. Hence the number of possible ways of getting six months with 2 birthdays and six with three birthdays is
times the number of ways of producing the 12 groups, which is
![]()
Hence the probability is,
![]()
Answer: Each group should then have N boys and N girls. The number of ways of doing this is, i.e. choose N boys from the 2N boys and N girls from the 2N girls. The total number of ways diving (2N + 2N) boys and girls into two groups each containing 2N individuals is
. This is the size of the sample space. Hence, the probability is,
![]()
Answer: The size of the sample space is. This is the same as the number of ways of distributing 26 cards to North and South. Let
be the probability that North and South have i aces between them for
.
Then,
, because 4 aces are taken out of the deck and given to East and West and the 26 cards of North and South are taken from the remaining 48 cards in the deck. Similarly,
![]()
Notice,
and
. Can you give a combinatorial argument for this?
Hard Problems
Answer: We know that the number of ways of ordering N objects consisting of M kinds, each kind containing say R objects, is.
By setting
and R = k we get that
is the number of ways of arranging k! objects consisting of (k-1)! kinds, each containing k objects. This should be an integer. Hence, (k!)! is divisible by
for any k.
Answer: This is the same as the total number of numbers minus the number of numbers that do not contain digit 1. The total number of numbers is 10 billion. The number of numbers that do not contain digit 1 is(because the number consisting of all zeros is excluded). Hence, the answer is
.
Answer: Take any (n-1)-digit binary sequence, say. It can always be extened to an n-digit binary sequence with even number of zeros as follows: If
has an odd number of zeros then append a zero to it at the end to get an n-digit binary sequence with an even number of zeros. If
has en even number of zeros then append a 1 to it at the end. Thus, there are exactly
n-digit binary sequences with an even number of zeros.
Answer: Every group of 5 scientists should not be able to open all the locks. Thus for each group of 5 scientists there should be at least one lock which they cannot open. Suppose,and
are any two groups of five scientists. Let
be the lock which
could not open and
be the lock which
could not open. Then
should be different from
. If
is the same as
then no group of six scientists chosen from from
will be able to open the cabinet. This will violate the requirement of the problem. Thus, distinct groups of 5-scientists should have distinct locks which they are not able to open. Hence, the number of needed locks is at least
since there are this many distinct groups of 5 scientists.
Let A be any one of the 11 scientists. For any group of 5-scientists chosen from the remaining 10 (excluding A) if A is added to the group then the six together should be able to open the cabiner. Since there are
distinct groups of 5-scientists among the 10 (excluding A) it follows that A should have with him the keys to open every one of the locks which each group of 5 could not open. Thus, A should carry at least
keys.
Answer: When a number is divided by 3 the remainder can be 0, 1 or 2. Thus all numbers in the range 1 through 300 can be partitioned into three groups. Each one of these groups will contain exactly 100 numbers. Let,
and
be these three groups.
Three number whose sum is divisible by 3 may be chosen as follows: All three from
in
ways for
or 2. Or, one number from each group; this can be done in
ways. Thus we get the answer given above.
Answer: We have three 2's, two 5's and one 7, in all six integers. Any product of one or more inegers chosen from these six is a divisor of 1, 400. There are 4 ways of chosing zero or more 2's, 3 ways of chosing zero or more 5's and 2 ways of chosing zero or more 7's. If zero 2's, zero 5's and zero 7's are chosen then the divisor is 1, otherwise the divisor is the product of the chosen numbers. Thus, the total number of divisors of 1, 400 is.
Answer: The 4 dividers will divide the 7 flags into 5 ordered groups inways. The flags in any one group are assumed to be raised on the same mast. Notice, the order in which the flags appear in a mast from top to bottom matters here.
Answer: Pascal's rule says,. If you repeatedly apply this same rule to
for
to get the formula given above.
It has the following combinatorial significance: m items can be chosen from n+1 items, either by discarding the item, say
, or by making sure, item
is included. After including item
one may chose the remaining m-1 items from the left over n-1 items by either discarding item, say
, or by making sure, item
is included. By repeating this argument successively over items
one gets the formula given above.
Answer:. Hence, if x = 1 we get
. The term by term differential of the binomial expansion of
is
![]()
We get the result by setting x to 1 in the expansion on the right side of the above equation.
Answer: The first two parts are similar to problem 16 above. See solution of problem 16: we used N objects consisting of M kinds, each king having R elements.For
set
and R = 2, and for
set
, and R = 3.
For the last part set M = R = n. Then we will have
objects consisting of n kinds, each kind having n objects. The number of ways of arranging this is
. Now notice, clearly, every arrangement,
![]()
will contain n kinds of objects in it. Think of these n kinds as n distinct colors, if you will. Let
be the order of first appearence of colors in
, i.e. color
appears first, color
is the second new color to appear in
,
is the third new color, etc. Then, one could get n! rearrangments of
by just permuting these n colors.
Now define,
is equivalent to
, if
may be obtained from
by just permuting its colors. Then each equivalence class will be of size n! and the number of equivalence classes in the set of all permutations of the
objects will be
, by the division rule. Since the number of equivalence classes should always be an integer we get the result.
Answer: One may choose n objects by choosing i of them from the set of n identical objects, and (n-i) of them from the remaining set of n distinct objects, where i may range from 0 through n. The i identical objects may be chosen only in one way. Hence the solution is.
Answer: Clearly, the probability of chosing the right key the very first time is. The probability of chosing the right key at the kth trial is the probability of not chosing the right key in the previous k-1 trials and then chosing the right one at the kth trial. Thus, every success at the kth trial will be preceded by a sequence of k-1 incorrect keys. Since the total number of incorrect keys is n-1, the total number of such sequences which can lead to success at the kth try is
. The sample space here is the number of k-permutations of n, which is
. Hence, the probability of getting a success at the kth try is
![]()
Answer: There areways of chosing 2r shoes from 2n single shoes.
(a). To assure no complete pair one should choose r, say from the let of n left shoes, and r from the complimentary set of (n-r) right shoes. The number of ways of doing this is
. Hence the probability is
.
(b). For exactly one complete pair, through a similar argument we get the probability,
, since there are n ways of picking one complete pair and
ways of picking 2(r-1) shows with no complete pairs.
Answer: Suppose there were n objects in two bags, say bags A and B, jointly containing a+b distinct objects, A containing a objects and B containing b objects. One may choose n objects from these two bags by choosing i from A and (n-i) from B, for. Hence,
.
Answer: We know that
![]()
Now set y = 1-x in the above equation. Then we get,
![]()
Clearly, the above formula will sum to 1 only if the coefficient of
is zero for all
. The coefficient of
in the above expansion is the sum of the terms shown below:,
![]()
which is the same as
. This solves the problem.