Combination at least 1

[Digionix]

Hey there, I'm currently struggling with this combination question:

In how many ways can a book sale display of 10 book be created if it must consist of a combination of Pearsons, Cambridges, Informas and Harvards and the display must contain at least 1 book from each publisher?


The only solution i can come up with is making the nCr for each of the publisher up until 6 which will take a long time cause i have to list all of them,

any help would be appreciated

 

[Mr. Bland]

Welcome to Free Math Help!

This question is asking for a set of 10 items, where each item is one of four types and there must be at least one item of every type in the set. It's possible to solve this kind of question through brute force, where every combination is examined, but as you stated, that would be quite inefficient. There are [MATH]4^{10}[/MATH] such combinations!

We know that 4 of the items must be specific values. We know that the remaining 6 items can be any value. Using these observations, can you devise a formula to solve the problem?

 

[Digionix]

Hmm... I think we can just count the 6 remaining items since the 4 of the items is already established.

So we can use the formula 6C4?

Please correct me if I am mistaken

 

[Romsek]

Hmm... I think we can just count the 6 remaining items since the 4 of the items is already established.

So we can use the formula 6C4?

Please correct me if I am mistaken

Pick 1 book from each publisher. Now you have fulfilled the requirement and have 6 books left to choose.
These can be anything. This is equivalent to a 6 digit base 4 number, i.e. each book you choose is tagged with the publisher ID 1-4.
There are $4^6 = 4096$ such arrangements.

 

[Digionix]

Pick 1 book from each publisher. Now you have fulfilled the requirement and have 6 books left to choose.
These can be anything. This is equivalent to a 6 digit base 4 number, i.e. each book you choose is tagged with the publisher ID 1-4.
There are $4^6 = 4096$ such arrangements.

Ah i see now, thank you so much for help guys

 

[Cubist]

Initially I brute forced the answer, so that I could check any further work...

Spoiler

818520

this assumes that book placement is important ( for example 1111111234 != 2341111111 )

I managed to get the same result manually (this might not be the fastest method)...

Let the the number of books of each type be A,B,C,D. So A=7, B=1, C=1, D=1 represents a valid combination (A+B+C+D=10)

To cut down the work, only consider the cases where A≥B≥C≥D and then work out the number of ways to permute ABC & D

A B C D | Number of combos      | Num ways to permute ABCD
=============================================================
7 1 1 1 |   10!/(7! 1! 1! 1!)   |        4! / 3!
6 2 1 1 |   10!/(6! 2!      )   |        4! / 2!
5 3 1 1 |       ?               |          ?
5 2 2 1 |       ?               |          ?
4 4 1 1 |       ?               |       4! / (2! 2!)
   ?    |       ?               |          ?
   ?    |       ?               |          ?
   ?    |       ?               |          ?
   ?    |       ?               |          ?
<no more A B C D combos possible, I leave 4 blank for you to find>

 

[pka]

In how many ways can a book sale display of 10 book be created if it must consist of a combination of Pearsons, Cambridges, Informas and Harvards and the display must contain at least 1 book from each publisher.

In combinatoric studies this is known as a multi-selection in which no cell is empty.
Model it this way: there are four cells $\displaystyle \mathop {\_\_|}\limits_C \mathop {\_\_|}\limits_H \mathop {\_\_|}\limits_I \mathop {\_\_}\limits_P$
There are $\displaystyle \dfrac{[(N+(C-1)]!}{N!(C-1)!}$ ways to place $\displaystyle N$ identical objects into $\displaystyle C$ distinct cells.
That rule may leave some cell empty so we go ahead and put one into each cell, leaving six identical balls to go into four distinct cells.

To see why this works: how many ways can we arrange the string $\displaystyle \circ\;\circ\;\circ\;\circ\;\circ\;\circ\;|\;|\;|~~?$

 

[Mr. Bland]

@Digionix come back! I have made an error: @Cubist's observations regarding the ordering of books have shed further light on the problem as stated.

Suggesting that there are [MATH]4^{10 - 4}[/MATH] ways to arrange the books fails for two reasons:

• If the order of the books does not matter, then AAAAABABCD and AABAAAABCD should be considered equivalent, but in the above formula they are not.
• If the order of the books does matter, then AAAAAAABCD and AAAAAABCDA should not be considered equivalent, but in the above formula they are.

I have verified this with brute force myself using a computer program, finding 818520 matching combinations (as Cubist did) when order matters and 84 unique combinations when order does not matter.

This is a more complicated problem than I initially assumed, and I will need to mull it over some more before I can propose a method of solving for it. For the time being, refer to the above posts for more insight into the problem.