[Key Techniques] Discuss Permutations II

Main post link -> http://blog.brilliant.org/2013/01/09/permutations-ii/

Samir and Mirdula each have distinct 7 books that they want to display on their shelves. Mirdula has lots of room on her shelf, however, Samir only has room to put 6 of his 7 books. Assuming that they fill up the entire shelf, who has more possible ways to arrange the books on their shelf? Why is this the case?
A waiter at a restaurant takes the drink order for a table of ten people but forgets to write down who ordered which drink. The orders are 5 cups of coffee, 3 glasses of water, 1 glass of milk, and 1 apple juice. How many different ways can the waiter deliver the drinks to the customers so that each customer gets one drink?
Consider all the ways to rearrange the letters of the word CALVIN, and arrange them in alphabetical order. In what position will CALVIN appear in? How about NIVLAC?
(*) Lisa wants to arrange 7 ornaments on her mantle. She has 2 identical cats, one mouse and 4 other different ornaments. If the mouse cannot be next to either of the cats, how many ways can they be arranged? Hint: Principle of Inclusion and Exclusion.

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

On the blog, Saurabh Dubey posted that:

1->Samir has more options because he has to select 6 books out of seven (7!) and then arrange them so total of 6!*7! whereas Mirdula only has to arrange 7 books (7!).

2->The number of ways would be 10!/(5!3!1!*1!) i.e 5040 ways.

Discuss.

Calvin Lin Staff - 8 years, 5 months ago

From Facebook:

Alexander wrote: "Consider the case where Samir only had one slot, it is obvious he has a smaller amount of ways to arrange the books than if he had more slots. The the most slots someone has the more ways they can arrange the books. From this logic Mirdula has more ways to arrange the books because she of the above logic and the fact she does not have any restrictions."

There is a possible ambiguity in the first. Do they always try to fill up the whole space?

Also, #3 is very similar to project euler problem 24 Its one of the few that can be done by hand

Harshit Kapur - 8 years, 5 months ago

That is true, I've added that they fill up the entire shelf.

Lexicographic / alphabetical ordering is a common problem. You should think about what the general solution is like, and what is a quick way to approach it.

1.Samir and Mirdula has equal number of ways to arrange the books. :) ${^7\!P_7}=7!=7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 7 \times 6 \times 5 \times 4 \times 3 \times 2 = {^7\!P_6}$ .

Soham Chanda - 8 years, 5 months ago

OMG what happened to latex?? Calvin help me!!

You have to put the latex code in < \ ( code \ ) > [with spaces removed between \ and ( ,and also \ and ) ]otherwise it will not know that you need to display the math.

I've edited the post for you, so you may click edit to see what I did.

@Calvin Lin – THANKS :)

Can you think of an explanation which shows that these 2 values are equal, without knowing the actual calculation?

Let the books of Samir be named $a,b,c,d,e,f,g$ Let one of his arrangement be $a.c.b.d.g.e$ Then he will have only one book left ie. $f$ If he had space for another book he would be able to make only one arrangement ie. $a.c.b.d.g.e.f$ which will correspond to one of Mirdula's arrangement.Similarly every arrangement of Samir's book will have a similar counterpart in Mirdula's arrangement of books.

3.CALVIN comes in 131^th place. First I saw the number of arrangements taking A in the first place.It will be 5!.Then CA,then CAI,CAL and so on

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$