Lesson Upper level combinatorics problem on finding the number of arrangements along a straight line

Source code of 'Upper level combinatorics problem on finding the number of arrangements along a straight line'

This Lesson (Upper level combinatorics problem on finding the number of arrangements along a straight line) was created by by ikleyn(53107)

: View Source, Show
About ikleyn:

<H2>Upper level combinatorics problem on finding the number of arrangements along a straight line</H2>

<H3>Problem 1</H3>Find the number of ways to arrange &nbsp;4 &nbsp;green balls, &nbsp;3 &nbsp;red balls, &nbsp;and &nbsp;2 &nbsp;white balls 
in a straight line such that no two balls of the same color are adjacent to each other.

<B>Solution</B>

<pre>
Place 4 green balls along the straight line.
Make gaps between these four green balls.

You will have three gaps between the 4 green balls 
PLUS one gap on the left before these balls 
PLUS one gap on the right after these balls.

We will place 3 red balls and 2 white balls in these 3 + 2 = 5 gaps.
We MUST place some of these 3 + 2 = 5 balls in the gaps between the green balls
and we CAN place some of these 5 balls in the gaps before and/or after 4 green balls.

It is the key idea to the problem' solution.

The rest is simply an implementation of this idea and detailed consideration/outlining/listing/counting 
of all possible cases.

+----------------------------------------------------------------------------------------+
    |           Let the gaps between the 4 green balls are numbered 1, 2, 3;                 |
    |   the gap before green balls has number 0 and the gap after green balls has number 4.  |
    +----------------------------------------------------------------------------------------+

(1)  This is the case when all 3 red balls and 2 white balls are placed in 3 gaps between the 4 green balls.

We have these sub-cases

gap  #       1    2    3

balls in the gaps   RWR  R    W,  
                            R    RWR  W,
                            R    W    RWR,   
        PLUS
                            RWR  W    R,  
                            W    RWR  R,
                            W    R    RWR,   
        PLUS
                            WRW  R    R,  
                            R    WRW  R,
                            R    R    WRW.

It gives  3 + 3 + 3 = 9 possible arrangements.

We also have these other sub-cases

gap #        1    2    3

balls in the gaps   2    2    1,   where  '2'  is  (R,W)  or (W,R) independently at every '2' appearance.

2    1    2,

1    2    2.   It gives {{{2^2 + 2^2 + 2^2}}} = 12 possible arrangements.

So, case (1) gives 9 + 12 = 21 different possible arrangements.

(2)  This is the case when all 3 red and 2 white balls are placed in 5 gaps, one ball in each gap.

It gives  {{{C[5]^2}}} = {{{(5*4)/2}}} = 10 different possible arrangements for case (2).

(3)  This is the case when 2 balls of different colors are placed in the gap '0'; 
     three remaining balls of 5 = 3R + 2W balls are placed in gaps 1, 2, and 3.

It gives these arrangements

gap  #       0   1    2    3   4

balls in the gaps  RW   R    R    W,
                           RW   R    W    R,
                           RW   W    R    R,      (3 arrangements)
        PLUS
                           WR   R    R    W,
                           WR   R    W    R,
                           WR   W    R    R.      (3 arrangements).

It gives 3 + 3 = 6  different possible arrangements for case (3).

(4)  This is the case when 2 balls of different colors are placed in the gap '4'; 
     three remaining balls of 5 balls (3R + 2W) are placed in gaps 1, 2, and 3.

This case is SYMMETRIC to case (3).  It gives 6 other arrangements, symmetric to case (3).

(5)  This is the case when 1 ball R or W is placed in the gap '0'; 
     four remaining balls of 5 = 3R + 2W balls are placed in gaps 1, 2, and 3, 
     so as two balls (R and W) are placed into the same gap.

It gives these arrangements

gap  #       0   1    2    3   4

balls in the gaps   R   R    W    RW,
                            R   W    RW   R,
                            R   RW   R    W,

R   W    R    RW,
                            R   R    RW   W,
                            R   RW   W    R,

R   R    W    WR,
                            R   W    WR   R,
                            R   WR   R    W,

R   W    R    WR,
                            R   R    WR   W,
                            R   WR   W    R      (3*4 = 12 arrangements)

PLUS
                            W   R    R    RW,
                            W   R    RW   R,
                            W   RW   R    R,

W   R    R    WR,
                            W   R    WR   R,
                            W   WR   R    R.     (3*2 = 6 arrangements)

It gives 12 + 6 = 18  different possible arrangements for case (5).

(6)  This is the case when 1 ball R or W is placed in the gap '4'; 
     four remaining balls of 5 = 3R + 2W balls are placed in gaps 1, 2, and 3, 
     so as two balls (R and W) are placed into the same gap.

This case is SYMMETRIC to case (5).  It gives 18 other arrangements, symmetric to case (5).

(7)  From cases (1), (2), (3), (4), (5) and (6),  we have, in all,

21 + 10 + 6 + 6 + 18 + 18 = 79 different possible arrangements.

<U>ANSWER</U>.  Doing this way, I counted 79 different possible arrangements.
</pre>

<H3>Problem 2</H3>Find the number of ways of arranging one &nbsp;A, &nbsp;two &nbsp;Bs, &nbsp;three &nbsp;Cs, &nbsp;and four &nbsp;Ds, &nbsp;so that 
no two &nbsp;Bs &nbsp;are next to each other, &nbsp;no two &nbsp;Cs &nbsp;are next to each other, &nbsp;and no two &nbsp;Ds &nbsp;are next to each other.

<B>Solution</B>

Above in this lesson, &nbsp;I solved similar problem

&nbsp;&nbsp;&nbsp;&nbsp;Find the number of ways to arrange &nbsp;4 &nbsp;green balls, &nbsp;3 &nbsp;red balls, &nbsp;and &nbsp;2 &nbsp;white balls 
    &nbsp;&nbsp;&nbsp;&nbsp;in a straight line such that no two balls of the same color are adjacent to each other.

The answer to this problem was that the number of ways is &nbsp;79.

In other terms, there are &nbsp;79 &nbsp;words of the length &nbsp;2+3+4 = 9 &nbsp;letters/positions, &nbsp;consisting of two letters &nbsp;Bs,
three letters &nbsp;Cs and four letters &nbsp;Ds so that no two &nbsp;Bs &nbsp;are next to each other, &nbsp;no two &nbsp;Cs &nbsp;are next to each other, 
and no two &nbsp;Ds &nbsp;are next to each other.

Now, &nbsp;having one additional letter &nbsp;A, &nbsp;for our problem, &nbsp;we can &nbsp;(and we should) place it in any position 
of these &nbsp;79 &nbsp;words of the length &nbsp;9, &nbsp;without any constraints.

Doing it, we will obtain 10 different words of the length 10 for each of the previous words of the length 9.

Hence, &nbsp;in all, &nbsp;we will have &nbsp;10*79 = 790 &nbsp;of the words of the length &nbsp;10, consisting of one &nbsp;A, &nbsp;two Bs, &nbsp;three &nbsp;Cs, 
and four &nbsp;Ds, &nbsp;so that no two &nbsp;Bs &nbsp;are next to each other, &nbsp;no two &nbsp;Cs &nbsp;are next to each other, &nbsp;and no two &nbsp;Ds 
are next to each other.

At this point, &nbsp;the problem is solved completely, &nbsp;and the answer is

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;there are &nbsp;790 &nbsp;such words, &nbsp;or &nbsp;790 &nbsp;such arrangements,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;satisfying the problem's conditions.

My additional lessons on Combinatorics problems in this site are

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/Permutations/Upper-league-combinatorics-problem.lesson>Upper league combinatorics problem</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/Permutations/An-upper-level-problem-on-a-party-of-people-sitting-at-a-round-table.lesson>Upper level problems on a party of people sitting at a round table</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/Permutations/Upper-level-combinatorics-problem-on-subsets-of-a-finite-set.lesson>Upper level combinatorics problem on subsets of a finite set</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/Permutations/A-confusing-combinatorics-problem-on-repeating-digits.lesson>A confusing combinatorics problem on repeating digits in numbers</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/Permutations/Upper-level-combinatorics-problems-on-Inclusion-Exclusion-principle.lesson>Upper level combinatorics problems on Inclusion-Exclusion principle</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/Permutations/This-nice-problem-teaches-to-distinguish-permutations-from-combinations.lesson>This nice problem teaches to distinguish permutations from combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/Permutations/OVERVIEW-of-additional-combinatorics-problems.lesson>OVERVIEW of additional combinatorics problems</A>

Use this file/link &nbsp;<A HREF=https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-II - YOUR ONLINE TEXTBOOK</A>&nbsp; to navigate over all topics and lessons of the online textbook &nbsp;ALGEBRA-II.