# Couting Questions

• Mar 22nd 2008, 02:33 AM
shaoen01
Couting Questions
Hi all,

I have a couple of questions regarding counting, so it will be fantastic if you can help me out. Thanks in advance!

Qns 1:
Consider strings of length n over the set {a,b,c,d}. How many such strings contain at least one pair of adjacent characters that are the same?

By adjacent do they mean (a,b) in length n, etc? Is the combination (b,a) allowed or equivalent to (a,b)?

Qns 2:
How many integers from 1 through 999999 contain each of the digits 1,2 and 3 at least once? (Hint: For each i let $\displaystyle A_{i}$ be the set of integers from 1 through 999999 that do not contain the digit i)

The solution asked me to use the inclusion and exclusion method, so how do i know when to use this?

Qns 3:
If $\displaystyle n=p_{1}p_{2}p_{3}p_{4}p_{5}$ where $\displaystyle p_{i}$ are distinct primes, in how many ways can n be expressed as a product of 2 positive integers? (n=ab and n=ba are considered the same)
What is the answer if $\displaystyle n=p_{1}p_{2}...p_{k}$?

From the solution, they mentioned the number of ways to choose a is $\displaystyle 2^{5}$ which i understand. It is stated that "it is a duplication by a factor of 2 since $\displaystyle p_{1}p_{2}$ and $\displaystyle p_{3}p_{4}p_{5}$ both appear as subsets but they give the same factorisation". I do not understand where the duplication is, can somehow show me an example?
• Mar 22nd 2008, 11:07 AM
Soroban
Hello, shaoen01!

Quote:

3) If $\displaystyle n=p_1p_2p_3p_4p_5$ where $\displaystyle p_i$ are distinct primes,
In how many ways can n be expressed as a product of 2 positive integers?
($\displaystyle n=ab\text{ and }n=ba$ are considered the same)

What is the answer if $\displaystyle n=p_1p_2\hdots p_k$?

From the solution, they mentioned the number of ways to choose a is $\displaystyle 2^{5}$ which i understand.
It is stated that "it is a duplication by a factor of 2 since $\displaystyle p_{1}p_{2}$ and $\displaystyle p_{3}p_{4}p_{5}$ both appear
as subsets but they give the same factorisation".

I do not understand where the duplication is.
Can somehow show me an example?

Suppose $\displaystyle n \:=\:30 \:=\:2\cdot3\cdot5$

With three factors to choose from, there are: $\displaystyle 2^3 = {\bf8}$ possible subsets.

They are: .$\displaystyle \{\;\},\;\{2\},\;\{3\},\;\{5\},\;\{2,3\},\;\{3,5\} ,\;\{2,5\},\;\{2,3,5\}$

But the question is: how many two-set partitions are there?

There are four: .$\displaystyle \begin{array}{cc}\{\;\} &\{2,3,5\} \\ \{2\} & \{3,5\} \\ \{3\} & \{2,5\} \\ \{5\} & \{2,3\} \end{array}\quad \text{ The products are: }\begin{Bmatrix}1\cdot30 \\ 2\cdot15 \\ 3\cdot10 \\ 5\cdot6\end{Bmatrix}$

The partition $\displaystyle \{2\}\;\;\{3,5\}$ is the same as $\displaystyle \{3,5\}\;\;\{2\}$
. . because $\displaystyle 2\cdot15\text{ and }15\cdot2$ are the same factoring.

• Mar 22nd 2008, 03:37 PM
Plato
Quote:

Originally Posted by shaoen01
Qns 1:
Consider strings of length n over the set {a,b,c,d}. How many such strings contain at least one pair of adjacent characters that are the same?
By adjacent do they mean (a,b) in length n, etc? Is the combination (b,a) allowed or equivalent to (a,b)?

Qns 2:
How many integers from 1 through 999999 contain each of the digits 1,2 and 3 at least once? (Hint: For each i let $\displaystyle A_{i}$ be the set of integers from 1 through 999999 that do not contain the digit i

I have no gotten a clear model for question #1. But I think that it is clear that you would allow neither ‘ab’ nor ‘ba’. I am pretty sure that one counts these with recursion.

Question #2 is lengthy but straightforward.
If T=999999 is the total number then we need to remove $\displaystyle \left( {A_1 \cup A_2 \cup A_3 } \right)$, that is removing any number that fails to contain a 1, 2, or 3.
You know that:
$\displaystyle \# \left( {A_1 \cup A_2 \cup A_3 } \right) =$$\displaystyle \# \left( {A_1 } \right) + \# \left( {A_2 } \right) + \# \left( {A_3 } \right) - \# \left( {A_1 \cap A_2 } \right) - \# \left( {A_1 \cap A_3 } \right) - \# \left( {A_3 \cap A_2 } \right) + \# \left( {A_1 \cap A_2 \cap A_3 } \right). I will help with one of those: \displaystyle \# \left( {A_1 \cap A_2 } \right) = 8^6 - 1. • Mar 22nd 2008, 07:26 PM shaoen01 Quote: Originally Posted by Soroban Hello, shaoen01! Suppose \displaystyle n \:=\:30 \:=\:2\cdot3\cdot5 With three factors to choose from, there are: \displaystyle 2^3 = {\bf8} possible subsets. They are: .\displaystyle \{\;\},\;\{2\},\;\{3\},\;\{5\},\;\{2,3\},\;\{3,5\} ,\;\{2,5\},\;\{2,3,5\} But the question is: how many two-set partitions are there? There are four: .\displaystyle \begin{array}{cc}\{\;\} &\{2,3,5\} \\ \{2\} & \{3,5\} \\ \{3\} & \{2,5\} \\ \{5\} & \{2,3\} \end{array}\quad \text{ The products are: }\begin{Bmatrix}1\cdot30 \\ 2\cdot15 \\ 3\cdot10 \\ 5\cdot6\end{Bmatrix} The partition \displaystyle \{2\}\;\;\{3,5\} is the same as \displaystyle \{3,5\}\;\;\{2\} . . because \displaystyle 2\cdot15\text{ and }15\cdot2 are the same factoring. Hi Soroban: Thank you for your reply. So for example, 3x10 is also equivalent to 10x3 right? So this kind of repeated value is not allowed. If i use your example, i can't seem to get the answer of \displaystyle 2^{4}=16. And must \displaystyle n=p_{1}p_{2}p_{3}p_{4}p_{5} be consecutive values? For example, 1 to 5? • Mar 22nd 2008, 07:32 PM shaoen01 Quote: Originally Posted by Plato I have no gotten a clear model for question #1. But I think that it is clear that you would allow neither ‘ab’ nor ‘ba’. I am pretty sure that one counts these with recursion. Question #2 is lengthy but straightforward. If T=999999 is the total number then we need to remove \displaystyle \left( {A_1 \cup A_2 \cup A_3 } \right), that is removing any number that fails to contain a 1, 2, or 3. You know that: \displaystyle \# \left( {A_1 \cup A_2 \cup A_3 } \right) =$$\displaystyle \# \left( {A_1 } \right) + \# \left( {A_2 } \right) + \# \left( {A_3 } \right) - \# \left( {A_1 \cap A_2 } \right) - \# \left( {A_1 \cap A_3 } \right) - \# \left( {A_3 \cap A_2 } \right) + \# \left( {A_1 \cap A_2 \cap A_3 } \right)$.

I will help with one of those: $\displaystyle \# \left( {A_1 \cap A_2 } \right) = 8^6 - 1$.

Hi Plato:

Qns 1:
Should i use the unordered and no repetition method to calculate this? Do you have any clues or hints to give me?

Qns 2:
But i am curious to know how did you get the value $\displaystyle \left( {A_1 \cap A_2 } \right) = 8^6 - 1$. I do know the inclusion/exclusion rule you written above, the thing is i do not know how to get the value like how you did.
• Mar 23rd 2008, 03:36 AM
Plato
Quote:

Originally Posted by shaoen01
I do not know how to get the value like how you did.

The set $\displaystyle A_1$ is the set of all integers 1 to 999999 that do not contain the digit 1. Because we can only use $\displaystyle \left\{ {0,2,3,4,5,6,7,8,9} \right\}$ there $\displaystyle 9^6-1$ numbers in $\displaystyle A_1$, we subtract the 1 to account for 000000000.
• Mar 23rd 2008, 05:44 AM
Soroban
Hello, shaoen01!

Plato's approach to #2 is correct . . .
I would further assume that an integer does not begin with zero.

Quote:

2) How many integers from 1 through 999999
contain each of the digits 1,2 and 3 at least once?

The solution asked me to use the inclusion-exclusion method,
so how do i know when to use this?

It is used when counting the items which are not in the set
is easier than counting the items that are in the set.

There are 999,999 integers.
How many do not contain at least {1,2,3} ?

Let $\displaystyle n(i')$ = number of integers that do not contain an $\displaystyle i.$

We want:
$\displaystyle n(1' \,\cup \,2' \,\cup \,3') \;=\;n(1') \,+\, n(2') \,+ \,n(3') \,-\, n(1' \,\cap \,2') \,- \,n(2' \,\cap \,3') \,- \,n(1' \,\cap \,3') \,+$ $\displaystyle n(1' \cap 2' \cap 3')$

Consider $\displaystyle n(1')$

1-digit numbers: 8 choices . (It must not be 0 or 1.)
2-digit numbers: $\displaystyle 8\cdot9$ choices.
3-digit numbers: $\displaystyle 8\cdot9^2$ choices.
4-digit numbers: $\displaystyle 8\cdot9^3$ choices.
5-digit numbers: $\displaystyle 8\cdot9^4$ choices.
6-digit numbers: $\displaystyle 8\cdot9^5$ choices.

There are: .$\displaystyle 8(1 + 9 + 9^2 + \hdots + 9^5) \;=\;8\,\frac{9^5-1}{9-1} \;=\;59,048$ such numbers.

The same reasoning holds for $\displaystyle n(2')\text{ and }n(3')$

. . Hence: .$\displaystyle n(1') \:=\:n(2') \:=\:n(3') \:=\:59,048$

Consider $\displaystyle n(1' \cap 2')$

1-digit numbers: 7 choices. .(It must not be 0, 1, or 2.)
2-digit numbers: $\displaystyle 7\cdot8$ choices.
3-digit numbers: $\displaystyle 7\cdot8^2$ choices.
4-digit numbers: $\displaystyle 7\cdot8^3$ choices.
5-digit numbers: $\displaystyle 7\cdot8^4$ choices.
6-digit numbers: $\displaystyle 7\cdot8^5$ choices.

There are: .$\displaystyle 7(1 + 8 + 8^2 +\hdots+8^5) \:=\:7\,\frac{8^5-1}{8-1} \:=\:32,767$ such numbers.

The same reasoning holds for $\displaystyle n(2'\cap3')\text{ and }n(1'\cap3')$

. . Hence: .$\displaystyle n(1'\cap2') \:=\:n(2' \cap 3') \:=\:n(1' \cap 3') \:=\:32,767$

Consider $\displaystyle n(1' \cap 2' \cap 3')$

1-digit numbers: 6 choices. .(It must not be 0, 1, 2, or 3.)
2-digit numbers: $\displaystyle 6\cdot7$ choices.
3-digit numbers: $\displaystyle 6\cdot7^2$ choices.
4-digit numbers: $\displaystyle 6\cdot7^3$ choices.
5-digit numbers: $\displaystyle 6\cdot7^4$ choices.
6-digit numbers: $\displaystyle 6\cdot7^5$ choices.

There are: .$\displaystyle 6(1 + 7 + 7^2 + \hdots + 7^5) \:=\:6\,\frac{7^5-1}{7-1} \:=\:16,806$ such numbers.

. . Hence: .$\displaystyle n(1' \cap 2' \cap 3') \:=\:16,806$

Then: .$\displaystyle n(1' \cup 2' \cup 3') \:=\:3(59,048) - 3(32,767) + 16,806 \:=\:95,649$

Therefore: .$\displaystyle n(1 \cap 2\cap 3) \;=\;999,999 - 95,649 \;=\;\boxed{904,350}$

But check my work and my reasoning . . . please!
.
• Mar 23rd 2008, 06:01 AM
Plato
Quote:

Originally Posted by Soroban
I would further assume that an integer does not begin with zero. But check my work and my reasoning . . . please!

But in the case "assume that an integer does not begin with zero", how would account for 234?
That contains no 1's but has the form 000234.
• Mar 23rd 2008, 12:10 PM
Opalg
Quote:

Originally Posted by shaoen01
Qns 1:
Consider strings of length n over the set {a,b,c,d}. How many such strings contain at least one pair of adjacent characters that are the same?

If that interpretation of the question is correct, then the answer is quite easy. There are $\displaystyle 4^n$ possible strings altogether, but $\displaystyle 4\times3^{n-1}$ of these are not allowed. (For a string not to be allowed, its first letter can be any one of the four, but each subsequent letter must be different from its predecessor, so there are only three choices for it.) Thus the number of allowable strings is $\displaystyle 4(4^{n-1} - 3^{n-1})$.
There are: .$\displaystyle 8(1 + 9 + 9^2 + \hdots + 9^5) \;=\;8\,\frac{9^5-1}{9-1} \;=\;59,048$ such numbers.
Bit of slippage here, I think! It should be $\displaystyle 8\,\frac{9^{\textstyle\mathbf6}-1}{9-1} \;=\;531440$ (and similarly for the other two summations).