Lesson Combinatoric problems for entities other than permutations and combinations

Source code of 'Combinatoric problems for entities other than permutations and combinations'

This Lesson (Combinatoric problems for entities other than permutations and combinations) was created by by ikleyn(52908)

: View Source, Show
About ikleyn:

<H2>Combinatoric problems for entities other than permutations and combinations</H2>

<H3>Problem 1</H3>How many four-character passwords can be formed using the characters &nbsp;A, &nbsp;B, &nbsp;C, &nbsp;1, &nbsp;2 &nbsp;if the characters can be repeated?

<B>Solution</B>

<pre>
You have 5 opportunities to place any of 5 symbols A, B, C, 1, 2 in the first (leftmost) position.

You have 5 independent opportunities to place any of 5 symbols A, B, C, 1, 2 in the next, second position.

Thus placing 5 symbols independently in two positions, you have 5*5 = 25 opportunities.

Then you have 5 independent opportunities to place any of 5 symbols A, B, C, 1, 2 in the next, third position.

Thus placing 5 symbols independently in three positions, you have 5*5*5 = 125 opportunities.

Then you have 5 independent opportunities to place any of 5 symbols A, B, C, 1, 2 in the next, fourth position.

Thus placing 5 symbols independently in four positions, you have 5*5*5* = {{{5^4}}} = 625 opportunities.

It means that in all, you may have  {{{5^4}}}  different four-character passwords under the given conditions.     <U>ANSWER</U>
</pre>

<H3>Problem 2</H3>If the test consists of &nbsp;5 &nbsp;questions, &nbsp;each of which has &nbsp;3 &nbsp;possible answers,
how many different answers to the test questions are possible, &nbsp;in all ?

<B>Solution</B>

<pre>
There are 3 possible answers to the 1-st question;

3 independent answers to the 2-nd question;

3 independent answers to the 3-rd question;

3 independent answers to the 4-th question;

and 3 independent answers to the 5-th question.

In all,   3*3*3*3*3 = {{{3^5}}} = 243 didderent answers are possible.
</pre>

<H3>Problem 3</H3>If you were given a five-question multiple choice test that has four possible answers for each question &nbsp;(a,b,c,d), 
how many ways could you answer all the questions on the test if you do not put down the same answer for two consecutive questions? ?

<B>Solution</B>

<pre>
1.  The total space T of all possible answers (including all allowed and all non-allowed) is the set of all  5-symbol words {x,y,z,u,w},

where each symbol x, y, z, u, and w can be any of 4 letters a, b, c, or d.

The cardinality (the number of elements) of this set is  {{{4^5}}}.

2.  The sub-space S of non-allowed answers are those 5-symbol words {x,y,z,u,w} that have coinciding symbols in two CONSECUTIVE positions.

You can imagine this sub-space as the union of 5-symbol words of the form

S = {x,x,y,z,w} U {y,x,x,z,w} U {y,z,x,x,w} U {y,z,w,x,x}

By gluing two coinciding symbols in one, you can see that the set S is the same (is isomorphic) to the set of all 4-symbol words {x,y,z,w},

where each symbol x, y z and w can take any of 4 values a, b, c and d.

From it, it is clear that the cardinality (the number of elements) of the sub-set S is  {{{4^4}}}.

3.  Now it is clear that the allowed  answers represent the set T \ S, and its cardinality is {{{4^5}}} - {{{4^4}}} = 768.
</pre>

<B>Answer</B>. &nbsp;&nbsp;There are &nbsp;&nbsp;{{{4^5}}} - {{{4^4}}} = 768 &nbsp;&nbsp;allowed answers.

<H3>Problem 4</H3>Each ship in a fleet is assigned a three-digit number that does not begin with a &nbsp;1&nbsp; or a &nbsp;0&nbsp; and does not contain a &nbsp;6&nbsp; or a &nbsp;9.
How many different numbers may be assigned under these conditions?

<B>Solution</B>

There are only  10-4 = 6  allowed digits at the first, most left position.

There are       10-2 = 8  allowed digits at the second position.

There are       10-2 = 8  allowed digits at the third position.

In all, there are 6*8*8 = 384 possible different numbers.
</pre>

<H3>Problem 5</H3>Four different colored flags can be hung in a row to make coded signal. 
How many signals can be made if a signal consists of the display of one or more flags?

<B>Solution</B>

<pre>
4            signals if to use 1 flag only,    plus

4*3     = 12 signals if to use 2 flags only,   plus

4*3*2   = 24 signals if to use 3 flags only,   plus

4*3*2*1 = 24 signals if to use all 4 flags.

In all, 4 + 12 + 24 + 24 = 64 signals.
</pre>

<B>Answer</B>. &nbsp;&nbsp;64 signals.

<H3>Problem 6</H3>Companies whose stocks are listed on the NASDAQ stock exchange have their company name
represented by either four or five letters &nbsp;(repetition of letters is allowed). &nbsp;What is the maximum
number of companies that can be listed on the NASDAQ?

<B>Solution</B>

<pre>
The number of 4-letter words written in English alphabet (26 letters) is {{{26^4}}}.

The number of 5-letter words                                          is {{{26^5}}}.

In all, the maximum number of companies that can be listed in this way is

{{{26^4}}} + {{{26^5}}} = 456976 + 11881376 = 12338352.
</pre>

<H3>Problem 7</H3>The digits &nbsp;0, 1, 2, 3, 4 &nbsp;are to be used in a four digit &nbsp;ID &nbsp;card.&nbsp; How many different cards are possible if repetitions are allowed?

If repetitions are not allowed?

<B>Solution</B>

<pre>
If repetitions are allowed, then

- you can put any of the given  5  digits to the 1-st position (5 opportunities);
    - you can put any of the given  5  digits to the 2-nd position (5 opportunities);
    - you can put any of the given  5  digits to the 3-rd position (5 opportunities);
    - you can put any of the given  5  digits to the 4-th position (5 opportunities).

In all, you have {{{5^4}}} = 625 different card ID numbers under this scenario.

If repetitions are not allowed, then another logic works:

- you can put any of the given     5 digits to the 1-st position (5 opportunities);
    - you can put any of the remained  4 digits to the 2-nd position (4 opportunities);
    - you can put any of the remained  3 digits to the 3-rd position (3 opportunities);
    - you can put any of the remained  2 digits to the 4-th position (2 opportunities).

In all, you have 5*4*3*2 = 120 different card ID numbers under this scenario.
</pre>

<H3>Problem 8</H3>A  bus starts with &nbsp;6&nbsp; people and stops at &nbsp;10&nbsp; different stops. &nbsp;How many different ways can the &nbsp;6&nbsp; people depart if 
no two passengers can depart at the same bus stop.

<B>Solution</B>

<pre>
It is the same as to ask:

In how many ways 6 different pigeons can be placed in 10 pigeonholes, under the condition
    that there are no two pigeons in one pigeonhole ?

The answer is: in   10*9*8*7*6*5 = 151200 ways.

1-st pigeon can be placed into any of          10 pigeonholes;
    2-nd pigeon can be placed into any of remained  9 pigeonholes;
    3-rd pigeon can be placed into any of remained  8 pigeonholes;
    4-th pigeon can be placed into any of remained  7 pigeonholes;
    5-th pigeon can be placed into any of remained  6 pigeonholes;
    6-th pigeon can be placed into any of remained  5 pigeonholes.
</pre>

<H3>Problem 9</H3>A  bus starts with &nbsp;6&nbsp; people and stops at &nbsp;10&nbsp; different stops. &nbsp;How many different ways can the &nbsp;6&nbsp; people depart if 
any passenger can depart at any bus stop.

<B>Solution</B>

<pre>
1-st person can go out at any of 10 bus stops - 10 opportunities.
2-nd person can go out at any of 10 bus stops - 10 independent opportunities.
3-rd person can go out at any of 10 bus stops - 10 independent opportunities.
4-th person can go out at any of 10 bus stops - 10 independent opportunities.
5-th person can go out at any of 10 bus stops - 10 independent opportunities.
6-th person can go out at any of 10 bus stops - 10 independent opportunities.

In all, there are  {{{10^6}}} different ways.

Same number of ways as how many 6-letter words do exist comprising of 10 given letters (symbols) of the alphabet, if letters repetition is allowed.
</pre>

<H3>Problem 10</H3>The inhabitants of the island of Jumble use the standard &nbsp;Kobish alphabet of &nbsp;20 letters, &nbsp;A &nbsp;through &nbsp;T. 
Each word in their language is &nbsp;4 &nbsp;letters or less, &nbsp;and for some reason, &nbsp;they insist that all words contain the letter &nbsp;A &nbsp;at least once. 
How many words are possible?

<B>Solution</B>

<pre>
1.  The number of all 4-letter words written using the alphabet of 20 symbols (from A to T)  is  {{{20^4}}}.

2.  The number of all 4-letter words written using the alphabet of 19 symbols (from B to T) is  {{{19^4}}}.

3.  The difference  {{{20^4}}} - {{{19^4}}} represents exactly the number of all words of the inhabitants of the island of Jumble.

{{{20^4}}} - {{{19^4}}} = 29679.
</pre>

<H3>Problem 11</H3>A jar contains pennies, &nbsp;nickels, &nbsp;dimes, &nbsp;and quarters.  &nbsp;Without looking or feeling, &nbsp;you take three of the coins.  
What is the number of all possible sets of three coins you might select ?

<B>Solution</B>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;The first sentence says &nbsp;"A jar contains pennies, &nbsp;nickels, &nbsp;dimes, &nbsp;and quarters."

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;It does not tell, &nbsp;how many such coins of every type are there in the jar.

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Based on the context and by &nbsp;DEFAULT, &nbsp;we should assume that the number of each kind of coins is &nbsp;LARGE &nbsp;ENOUGH.

<pre>
If to consider different triples of coins without repetition of types inside each triple,

then we have classic COMBINATIONS, and the number of such triples is  {{{C[4]^3}}} = 4.

But repetitions inside each triple  ARE  NOT  PROHIBITED:  they are allowed.

So, we should add such triples with repetitions.

Triples with repetitions are

a)  (X, X, Y),  where  X can be any of 4 types and Y can be any of other 3 types.

In all, there are  4*3 = 12 such triples (disregarding the order inside the triples).

b)  to it, we should add 4 triples of the form (X, X, X),  where  X can be any of 4 types.

Taking everything into account, we have, in all,  4 + 12 + 4 = 20 possible different triples (disregarding the order inside the triples).

<U>ANSWER</U>.  There are 20 possible different triples, disregarding the order inside the triples.
</pre>

<H3>Problem 12</H3>How many different pairs, with repetition, can be formed with the letters &nbsp;a, &nbsp;b, &nbsp;c, &nbsp;d, &nbsp;if

&nbsp;&nbsp;&nbsp;&nbsp;(a) &nbsp;&nbsp;the pairs are ordered;

&nbsp;&nbsp;&nbsp;&nbsp;(b) &nbsp;&nbsp;the pairs are unordered.

<B>Solution</B>

From the context, &nbsp;there are enough instances of each letter &nbsp;(more concretely, &nbsp;at least two instances of each letter).

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<U>for ORDERED pairs</U>

<pre>
You have 4 letters.

If repetition is allowed, then you may have any of 4 letters in the first position and any of 4 letters in the second position.

In all, it gives 4*4 = 16 different groups of 2 letters each.
</pre>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<U>For UNORDERED pairs</U>

<pre>
For unordered pairs, the pair (a,b) is the same as (b,a).

Then there are  {{{(4*3)/2}}} = 6 pairs  with different (non-repeating) letters

PLUS  4  pairs with repeating letters (a,a), (b,b), (c,c) and (d,d).

It gives, in total, 6 + 4 = 10 such groups.
</pre>

So, &nbsp;in this problem, &nbsp;there are two way to form pairs, &nbsp;and, &nbsp;correspondingly, &nbsp;there are two different answers.

Visually, &nbsp;the model for the first case is a full &nbsp;4 x 4 &nbsp;matrix filled with ordered pairs of letters &nbsp;(16 &nbsp;ordered pairs).

For the second case, &nbsp;the model is the upper triangular part of the &nbsp;4 x 4 &nbsp;matrix with its diagonal included.

My lessons on Permutations and Combinations in this site are

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Introduction-to-Permutations.lesson>Introduction to Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/PROOF-of-the-formula-on-the-number-of-permutations.lesson>PROOF of the formula on the number of Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Problems-on-Permutations.lesson>Simple and simplest problems on permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Special-type-permutations-problems.lesson>Special type permutations problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/How-many-different-permutations-may-exist-ubder-given-restrictions.lesson>Problems on Permutations with restrictions</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Math-circle-level-problem-on-Permutations.lesson>Math circle level problem on Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Introduction-to-Combinations-.lesson>Introduction to Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/PROOF-of-the-formula-on-the-number-of-combinations.lesson>PROOF of the formula on the number of Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Problems-on-Combinations.lesson>Problems on Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Combinations-problems-with-restrictions.lesson>Problems on Combinations with restrictions</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Math-circle-level-problem-on-Combinations.lesson>Math circle level problem on Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Arranging-elements-of-sets-containing-undistinguishable-elements.lesson>Arranging elements of sets containing indistinguishable elements</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Persons-sitting-around-a-circular-table.lesson>Persons sitting around a cicular table</A>

&nbsp;&nbsp;&nbsp;&nbsp;- Combinatoric problems for entities other than permutations and combinations &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(this file)

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Fundamental-counting-principle-problems.lesson>Fundamental counting principle problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Miscellaneous-problems-on-permutations-combinations-and-other-combinatoric-entities.lesson>Miscellaneous problems on permutations, combinations and other combinatoric entities</A>

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

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

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/DERANGEMENT-problems.lesson>Derangement problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/In-how-many-ways-N-distinguishable-objects--can-be-distributed-among-n-different-boxes.lesson>In how many ways N distinguishable objects can be distributed among n different boxes ?</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Stars-and-bars-method-for-Combinatorics-problems-2.lesson>Stars and bars method for Combinatorics problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Men-and-women-standing-in-line-.lesson>Men and women standing in line</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/One-combinatorial-Geometry-problem-solved-using-the-Euler-formula.lesson>One combinatorial Geometry problem solved using the Euler formula</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Nice-recreational-problems-on-permutations.lesson>Nice recreational problems on permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/OVERVIEW-the-lessons-on-Permutations-and-Combinations.lesson>OVERVIEW of lessons on Permutations and Combinations</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.