# Counting principles 3....

57) Given a collection of '2n' objects, 'n' idetical and the other 'n' all distinct, how many different subcollections of 'n' objects are there?

13) How many 8-digit sequences are there involving exactly six different digits?
Again the first solution gets all points.
LVL 5
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
There may be an easier way of doing this but here we go any way (this seems a bit messy)

The number involving more than 6 is 10*9*8*7*6*5*4 for the ordered 7 different digits which can be placed in 8 different ways (ie 8 spaces for the last digit to go into) and 10 choices for the last digit to go in

total=9*8*7*6*5*4*8*10 =10*9*8*(8*7*6*5*4)

This counts those with 7 and 8 different digits

For the number involving less than 6 (ie at least 4 the same) there 10 ways of choosing the repeated at least 4 times and 8*7*6*5/4! choices of how to arrange them in the 8 digit number. The remaing 4 positions can be filled with anything ie 10^4 possibilities

Giving  a total of 10^4*10*(8*7*6*5)/4! = 10^5*(8*7*6*5*4)/3!

So not involving exactly 6 is

10*9*8*(8*7*6*5*4) + 10^5*(8*7*6*5*4)/3!

= 10*(8*7*6*5*4)(9*8 +10^4/3!)

Since there are 8^10 possible sequences then the total with exactly 6 is

8^10 - 10*(8*7*6*5*4)(9*8 +10^4/3!)

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
Set A  different and set B identical

Any collection of n will contain m form A and n - m from B

There are  n!/n!(n-m)! ways of choosing m unordered objects from A and 1 way of chosing n-m from B

The total is is the sum over all possible m ie

sum (m=0 to n) n!/n!(n-m)!

this a well know summation and is 2^n
Author Commented:
Cwiz you rule dude. That was quick. I am trying to grasp your first explanation.Second one yeha I have the same answer.
Commented:
The sum is the sum of the binomial coefficients
Commented:
I am unhappy about the first one there must be an easier way, I will give it some more thought but the method I have used I think is right ie find those with 5 or less different and 7 or more and subtract from the total possible
Commented:
Now I feel really stupid this is it surely,

Given 6 digits then the number of 8 digit numbers is fom them is 6^8

there 8!/2!*6! ways of choosing the 6 digits giving a grand total of

6^8*8!/2!*6!

Commented:
6^8*8!/(2!*6!) to avoid ambiguity
Commented:
Since these are numnbered it appears to be homework or some kind of test.

13) M things taken N at a time

Assuming order doesn't matter

M! / (N! * (M - N)!)

If order matters then
M! / (M - N)!

57) Sum of the binomial coeficients for (a +b) ^ N or 2^N in this case

mlmcc
Commented:
this equal to sum(i=0,n,n!/(n-i)!)
Commented:
this if 2n contain n i.e total is 2n
but if the total is 3n (2n distincit and n similar)
tha naswer will be
sum sum(i=0,n,2n!/(2n-i)!)
Commented:
this come from (i have let m distincit and n non dis
so
0  - i may no choose any of n and all of m then the prem is m!/(m-n)!
1  - i may  choose 1 from  n and (n-1) of   m then the prem is m!/(m-n-1)!
2- - i may  choose 3 from  n and (n-2) of   m then the prem is m!/(m-n-2)!
.
.
.
.
n-  i may  choose n from  n and nothing of m then the prem is m!/(m-o)!=1

total is the sumetion

Commented:
57) Given a collection of '2n' objects, 'n' idetical and the other 'n' all distinct, how many different subcollections of 'n' objects are there?

57) given p have n identical objects and q have n all distinct object
there is n+1 types of collection of n objects based on the number of object in p appear, there are :
1. n collection "without" p object ,( i assume order doesnt matter ) :
n C n = 1 subcollection
2. n collection "with 1" p object, so there is n-1 place left for n objects q :
n C n-1 = n subcollections
3. n collection "with 2" p object, so there is n-2 place left for n objects q :
n C n-2 = (n*n-1)/2 subcollections
.
.
.
n-1.  n collection "with n-2" p object, so there is 2 place left for n objects q :
n C 2 = (n*n-1)/2 subcollections
n. n collection "with n-1" p object, so there is 1 place left for n objects q :
n C 1 = n subcollections
n+1. n collection "with n" p object ,( i assume order doesnt matter ) :
n C 0 = 1 subcollection

total combination : nCn+nCn-1+...+nC1+nC0 = x

x is the total coefficient of (a+b)^n = &#8721;(nC(k1,k2))(a^k1)(b^k2);k1,k2 from 0 to n

if 'order is matter' we do in permutation way.

13) How many 8-digit sequences are there involving exactly six different digits?
Again the first solution gets all points.

# if order is not matter : there are 9 digits(the other one digit assume has put in 2 empty places ), so there is left 6 places with 9 available digits :
there are 9 C 6 = 84 digit sequences
# if order matter : there is (9 P 6)*(8 C 2(the way 2 same digit placed)) =14112

am i right?

hahan
Commented:
may be it need a little moddification :)

hahan
Commented:
57) Let A is a set of distinct objects, B is a set of identical objects.
Notice that each n-subset S of AUB is uniquely defined by its ``A-part'' which is some subset of A. So the total number of n-subsets S is equal to total number of all subsets of A, which is 2^n.

8) There two cases:
1) among 8 digits one occurs three times
number of sequences is 8!/3! = 6720
2) among 8 digits two occur two times each
number of sequences is 8!/(2!2!) =  10080
Total number of sequences is 6720+10080 = 16800

###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Math / Science

From novice to tech pro — start learning today.