0
$\begingroup$

Hello i had new 6 questions but i cant solve this two any help will be appreciated thanks

Question 4 (15%)
A-) Give an one-line proof for $ n^r \ge C(n+r-1,r) $
[Hint: direct proof]

B-) What is the implication on the number of r-permutations and that of r-combinations with repetition? Give one-line description.

Question 6 (10%)
A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers.
Answer should be no more than 3 lines.

Improve this question
$\endgroup$
0
$\begingroup$

HINTS:

(4A) $$\binom{n+r-1}r=\underbrace{\frac{n+r-1}r\cdot\frac{n+(r-1)-1}{r-1}\cdot\ldots\cdot\frac{n+1-1}1}_{r\text{ factors}}\;;$$ how big is $\dfrac{n+k-1}k$ compared with $n$?

(4B) $\binom{n+r-1}r$ is the number of $r$-combinations with repetition, and $n^r$ is the number of $r$-permutations.

(6) Each computer is connected to $1,2,3,4$, or $5$ other computers. Use the pigeonhole principle.

Improve this answer
$\endgroup$
  • $\begingroup$ really thanks i see now i should have solved that easy things ^^ $\endgroup$ – Xyir Kozburn Dec 15 '12 at 11:53
  • $\begingroup$ @Xyir: You’re welcome. $\endgroup$ – Brian M. Scott Dec 15 '12 at 11:54
0
$\begingroup$

Q4. part A:

The number of ways of distributing $r$ distinguishable balls (distinguished by assigning labels to them) in $n$ distinguishable urns is more than the number of ways of distributing $r$ indistinguishable balls in $n$ distinguishable urns. [Because in any distinguishable ball arrangement by dropping labels from distinguishable balls we can get an indistinguishable ball arrangement]

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.