The following comes from questions comes from a recent combinatorics paper I attended :
1.27 people are to travel by a bus which can carry 12 inside and 15 outside. In how many ways can the party be distributed between inside and outside if 5 people refuse to go outside and 6 will not go inside?
The solution given C(16,7), I have no clue how they got it ?!
2.The number of functions f from the set A = {0, 1, 2} into the set B = {1, 2, 3, 4, 5, 6, 7} such that $f(i) \le f(j) $ for $i \lt j $ and $i,j$ belongs to A is
The solution given is C(8,3). I didn't really understood this one.
3.The number of ordered pairs $(m, n) m, n $ is in {1 , 2, … , 100} such that $7^m + 7^n$ is divisible by 5 is
The solution given is 2500, but how ?
4.The coefficient of $x^{20}$in the expansion of $(1 + 3x + 3x^2 + x^3)^{20}$, is ?
How to solve this one elegantly ?
5.An eight digit number divisible by 9 is to be formed by using 8 digits out of the digits 0, 1, …, 9 without replacement. The number of ways in which this can be done is:
Now this one seems impossible for me to solve in 1 mint,or is it ? Given soln is 36(7!)
Best Answer
Five people refuse to go outside, and therefore will go inside. Six people refuse to go inside, so will go outside. That means that you still have $27 - (5+6)=16$ people to accommodate. There are 12 spots for people inside, but five are already "taken" by those who refuse to be outside. That leaves 7 seats inside to assign. So you need to choose which seven people, out of the 16 that are left, will go inside. The number of ways of doing this is precisely $\binom{16}{7}$.
Edit: I misread the question as saying that $f(i)\lt f(j)$ if $i\lt j$. That answer follows: since you require the values of the function to increase (the condition just says that $f(0)\lt f(1)\lt f(2)$), if you know the three values of $f(0)$, $f(1)$, and $f(2)$ you know which one corresponds to which ($f(0)$ is the smallest value, $f(1)$ is the middle value, and $f(2)$ is the largest value). So all you need to do in order to determine a function is to pick three values from $B$. There are $7$ possibilities, you need to pick $3$, so there are $\binom{7}{3}$ ways of doing it.
Now, it seems I misread the question. It actually says that $f(i)\leq f(j)$ if $i\lt j$. I gave the number of functions in which all inequalities are strict. There are $\binom{7}{1}$ functions in which all inequalities are actually equalities (just one value). Now, to count the number of functions in which $f(0)=f(1)\lt f(2)$, you just need to pick two values from the set $B$, which there are $\binom{7}{2}$ ways of doing; the same holds for the case in which you have $f(0)\lt f(1)=f(2)$. So the total is $\binom{7}{3}+2\binom{7}{2} + \binom{7}{1}$. Since $\binom{n}{k}+\binom{n}{k-1} = \binom{n+1}{k}$, this total is equal to $$\left(\binom{7}{3} + \binom{7}{2}\right) + \left(\binom{7}{2}+\binom{7}{1}\right) = \binom{8}{3}+\binom{8}{2} = \binom{9}{3}.$$ It seems to me, then, that the answer you give is incorrect, or perhaps you mistyped it.
(If you know the formula for combinations with repetitions, then there is a more direct way of getting this result: simply pick $3$ out of the $7$ possible images, with repetitions allowed; smallest value is $f(0)$, middle value is $f(1)$, largest values $f(3)$ (equality allowed). The total for this is $\binom{7+3-1}{3} = \binom{9}{3}$, as above).
Assume $m\leq n$; then $7^m+7^n = 7^m(1 + 7^{n-m})$. The product is divisible by $5$ if and only if $1 + 7^{n-m}$ is divisible by $5$ (since $5$ is prime and never divides a power of $7$). For $1+7^{n-m}$ to be divisible by $5$, you need $7^{n-m}$ to have a remainder of $4$ when divided by $5$. If you run over the powers of $7$ and see the remainder when divided by $5$, you will notice that they go $2$, $4$, $3$, $1$, and repeat. So basically, you need $n-m$ to be a multiple of $4$ plus $1$. That is, you need $n-m = 4k+1$. Note in particular that if the pair has $n=m$, then it does not satisfy the condition. So count how many pairs there are where the two differ by a multiple of four plus 1.
One possibility is the Multinomial theorem You would need to figure out all the ways in which you can obtain $x^{20}$ as products of powers of $x$, $x^2$, and $x^3$, and add the appropriate coefficients.Edit: But the intended answer is almost certainly the one given by Larry Denenberg.In order for the number to be divisible by $9$, the digits must add up to a multiple of $9$. The digits $0$ through $9$ add up to $45$, which is a multiple of $9$. So if you omit two of them, they must add up to $9$: thus, if you omit $0$, then you must also omit $9$; if you omit $1$, then you must also omit $8$; etc. So you only have five possible pairs of numbers that you can omit. So pick which of the five pairs you will omit. If you omit $0$ and $9$, then the remaining $8$ digits can be arranged in any order, giving $8!$ possibilities. In all other cases, you cannot place $0$ in the first position, but otherwise can place the rest in any order. That gives $7(7!)$ possible ways of ordering the numbers. Thus, you have one choice that leads to $8!$ numbers, and four choices that lead each to $7(7!)$ numbers. Adding them up gives $8!+(4\times 7)(7!) = 8(7!)+28(7!) = 36(7!)$.