Expiring Todayâ€”Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Counting principles 3....

Posted on 2003-11-09
Medium Priority
713 Views
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.
0
Question by:b_vishwajit
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 6
• 3
• 2
• +3

LVL 31

Accepted Solution

GwynforWeb earned 800 total points
ID: 9711481
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!)

0

LVL 31

Expert Comment

ID: 9711520
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
0

LVL 5

Author Comment

ID: 9711572
Cwiz you rule dude. That was quick. I am trying to grasp your first explanation.Second one yeha I have the same answer.
0

LVL 31

Expert Comment

ID: 9711578
The sum is the sum of the binomial coefficients
0

LVL 31

Expert Comment

ID: 9711622
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
0

LVL 31

Expert Comment

ID: 9711655
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!

0

LVL 31

Expert Comment

ID: 9711665
6^8*8!/(2!*6!) to avoid ambiguity
0

LVL 101

Expert Comment

ID: 9711735
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
0

LVL 5

Expert Comment

ID: 9711868
this equal to sum(i=0,n,n!/(n-i)!)
0

LVL 5

Expert Comment

ID: 9711873
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)!)
0

LVL 5

Expert Comment

ID: 9711887
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

0

LVL 1

Assisted Solution

hahan earned 200 total points
ID: 9719757
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
0

LVL 1

Expert Comment

ID: 9719763
may be it need a little moddification :)

hahan
0

LVL 1

Expert Comment

ID: 10011231
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

0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a negaâ€¦
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201â€¦
###### Suggested Courses
Course of the Month11 days, left to enroll