Prove-that-there-are-n-r-1-n-1-ways-of-placing-r-identical-objects-in-n-compartments-where-n-gt-r-

Question Number 3884 by Yozzii last updated on 23/Dec/15

P r o v e t h a t t h e r e a r e (\begin{matrix} n + r - 1 \\ n - 1 \end{matrix})

w a y s o f p l a c i n g r i d e n t i c a l o b j e c t s

i n n c o m p a r t m e n t s, w h e r e n > r .

Commented by RasheedSindhi last updated on 24/Dec/15

L e t r o b j e c t s a r e d e n o t e d a s

o_{0}, o_{1}, o_{2}, \dots o_{r - 1} .

F o r o_{0} t h e r e a r e n w a y s .

F o r o_{1} t h e r e a r e n - 1 w a y s .

F o r o_{2} t h e r e a r e n - 2 w a y s .

F o r o_{3} t h e r e a r e n - 3 w a y s .

⋮

F o r o_{r - 1} t h e r e a r e n - r + 1 w a y s .

T o t a l w a y s :

n (n - 1) (n - 2) \dots (n - r + 1)

=^{n} p_{r} = (\begin{matrix} n \\ r \end{matrix}) r! = \frac{n!}{r! (n - r)!} \times r!

= \frac{n!}{(n - r)!}

O r

(\begin{matrix} n + r - 1 \\ n - 1 \end{matrix}) w a y s . ? ? ?

C o n t i n u e

Commented by Yozzii last updated on 24/Dec/15

F r o m m y i n v e s t i g a t i o n o n t h i s, y o u

c a n l o o k a t h o w c a n o b t a i n t h e v a l u e

o f r v i a a d d i n g i n t e g e r s . F o r e x a m p l e

i f r = 4 a n d n i s f i x e d, w e c o u l d

d i s t r i b u t e r = 4 l i k e 1 + 1 + 1 + 1 (4 c o m p a r t m e n t s)

o r 1 + 1 + 2 o r 1 + 2 + 1 o r 2 + 1 + 1 (3 c o m p a r t m e n t s)

o r 1 + 3 o r 3 + 1 o r 2 + 2 (2 c o m p a r t m e n t s)

o r 4 (1 c o m p a r t m e n t) .

Y o u h a v e n c o m p a r t m e n t s

\Rightarrow (\begin{matrix} n \\ 4 \end{matrix}) w a y s f o r 1 + 1 + 1 + 1

\Rightarrow (\begin{matrix} n \\ 3 \end{matrix}) + (\begin{matrix} n \\ 3 \end{matrix}) + (\begin{matrix} n \\ 3 \end{matrix}) = 3 (\begin{matrix} n \\ 3 \end{matrix}) w a y s

f o r 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1

\Rightarrow 3 (\begin{matrix} n \\ 2 \end{matrix}) w a y s f o r 1 + 3, 3 + 1, 2 + 2

\Rightarrow (\begin{matrix} n \\ 1 \end{matrix}) w a y s f o r 4 .

\Rightarrow T o t a l n u m b e r o f w a y s

= (\begin{matrix} n \\ 1 \end{matrix}) + 3 (\begin{matrix} n \\ 2 \end{matrix}) + 3 (\begin{matrix} n \\ 3 \end{matrix}) + (\begin{matrix} n \\ 4 \end{matrix}) .

F o r r = 5 I d e d u c e d

(\begin{matrix} n \\ 1 \end{matrix}) + 4 (\begin{matrix} n \\ 2 \end{matrix}) + 6 (\begin{matrix} n \\ 3 \end{matrix}) + 4 (\begin{matrix} n \\ 4 \end{matrix}) + (\begin{matrix} n \\ 5 \end{matrix}) w a y s .

I s a w t h e b i n o m i a l c o e f f i c i e n t s

a r i s i n g i n t h e s e a n s w e r s s o I g u e s s e d

t h a t g e n e r a l l y,

n u m b e r o f w a y s = \underset{i = 0}{\sum^{r - 1}} {(\begin{matrix} r - 1 \\ i \end{matrix}) \times (\begin{matrix} n \\ i + 1 \end{matrix})} .

I t i s r e q u i r e d t o p r o v e t h a t

(\begin{matrix} n + r - 1 \\ n - 1 \end{matrix}) = \underset{i = 1}{\sum^{r - 1}} {(\begin{matrix} r - 1 \\ i \end{matrix}) (\begin{matrix} n \\ i + 1 \end{matrix})} .

Commented by RasheedSindhi last updated on 24/Dec/15

P e r h a p s I m i s u n d e r s t o o d y o u r

q u e s t i o n . I s u p p o s e d t o p l a c e o n e

o b j e c t p e r c o m p a r t m e n t . T h e r e

a r e n c o m p a r t m e n t s . S o f i r s t

o f r o b j e c t s c a n g o i n a n y o n e

o f n c o m p a r t m e n t s . S o t h e r e a r e

a r e n w a y s f o r f i r s t o b j e c t . A c t u a l l y

I {d i d n}^{'} t g i v e d u e i m p o r t a n c e t o

t h e w o r d^{'} i d e n t i c a l^{'}!

Commented by prakash jain last updated on 24/Dec/15

Stars and Bars

Answered by prakash jain last updated on 24/Dec/15

Taks (n + r - 1) position .

Place n - 1 markers at any of those postions .

Remaining r positions are occupied by

objects .

(n - 1) m a r k e r s d i v i d e r o b j e c t s i n n - c o m p a r t m e n t s .

S o total number of ways :^{n + r - 1} C_{n - 1} .

Examples (stars are objects bars divide them)

4 obects 6 compartments (5 bars)

★ ∣∣ ★ ∣∣∣ ★ ★

divisions 1, 0, 1, 0, 0, 2

total position 9

- - - - - - - - -

place (n - 1) bars or dividers

- ∣ ∣ - ∣ ∣ ∣ - -

r o b j e c t s a r r d i v i d e d i n t o n - c o m p a r t m e n t s .

This method is known as stars and bars .

Commented by Yozzii last updated on 24/Dec/15

I n e v e r h e a r d o f t h i s m e t h o d b e f o r e .

I w e n t a f t e r c o n s i d e r i n g t h e i d e n t i t y

{(1 + x)}^{n + r - 1} = {(1 + x)}^{n} {(1 + x)}^{r - 1}

f o r t h e c o e f f i c i e n t i n x^{n - 1}

t o p r o v e t h a t \underset{i = 0}{\sum^{r - 1}} {(\begin{matrix} r - 1 \\ i \end{matrix}) (\begin{matrix} n \\ i + 1 \end{matrix})} = (\begin{matrix} n + r - 1 \\ n - 1 \end{matrix}) .

Commented by prakash jain last updated on 24/Dec/15

I think it is truly exceptional on your

part to come up with this method on your

own .

Commented by Yozzii last updated on 24/Dec/15

T h a n k y o u v e r y m u c h f o r y o u r k i n d

w o r d s! E n c o u r a g e m e n t i s b e n e f i c i a l

w h e n i t i s y o u t h i n k {y o u}^{'} r e m a k i n g

s l o w p r o g r e s s i n i n d i v i d u a l m a t h e m a t i c a l

s t u d i e s . {Y o u}^{'} r e f u r t h e r d r i v e n t o

c o n t i n u e t r y i n g a s s u c h a p e r s o n .

Facebook Tweet Pin