Anyway, I knew a lot of things carried the name Bernoulli (Bernoulli principle, Bernoulli numbers, Bernoulli's equation, Bernoulli distribution...they ran a damn franchise), but I didn't know until researching today's problem that it wasn't just one really prolific guy, but rather a family affair. That made me feel a bit better about things.

This all relates because today's problem apparently was a favorite of Nicolaus Bernoulli (1695-1720), who I take it was the looker of the family:

So this lovely family invented a lot of tricky math stuff that helped us understand the world better, but made my sophomore year GPA suffer a bit more than was strictly necessary. So now dear reader, I will let them loose on you:

A correspondent writes seven letter and addresses seven envelopes, one for each letter. In how many ways can all of the letters be placed in wrong envelopes?

I should know the answer to this one...or to be able to figure it out.

ReplyDeleteBut I can't think of it right now.

Letters: A B C D E F G

ReplyDeleteEnvelopes 1 2 3 4 5 6 7

A can be put incorrectly in 2-7, so there's 6 options there.

B can be put in 1, 3-7 (i.e. 6 options), if A was put in 2, Otherwise, there are 5 options

If A or B was put in 3, C can go in 5 places. Otherwise, 4 places

If A, B or C was put in 4, D can go in 4 places, otherwise 3

If A,B,C or D were put in 5, E can go in 3 places, otherwise 2

If any of A-E were put in 6, F can go in 2 places, otherwise 1

G can go in 1 place

I am running short on time, but I would guess 6x5x4x3x2 + 6+5+4+3+2 -> 740 different combinations

I don't think it's that clean. I'm figuring 7! minus a whole bunch of werd stuff is going to show up somewhere, and that will be much larger.

ReplyDeleteFor one letter there are 0 wrong arrangements. For 2 letters, one wrong arrangement. For 3 letters, 2 wrongs. For 4 letters, 9 possible wrong arrangements. I started working 5 by hand, and the number is over 40, but my head hurts and I may have missed something.

So what's got 5!(120) minus stuff, or 4! (24) plus stuff, and comes out to something around 45? Dunno. It must be a series, so I can't intuit it in from there. I'm letting this spin for qwhile.

I tried this, and maybe the sequence is instructive:

ReplyDelete6 cases for the first, 5 for the second, 4 .. Wait a bit--suppose the first and second just swapped? Start from the beginning.

1 letter, always right, =0

2 letters, one way to goober it up

3 letters, 2 ways

4 letters: ah. 3*2=6 ways of cycling the 4 around, but then 3 ways of doing 2+2. (=9)

So partitioning is the way to go. A partition of 1 always maps the letter into the right envelope, so there's no answers with partition 1.

7 can be

a "cycle" of 7: with 1 case, which has 6*5*4*3*2 permutations

a "cycle" of 5 plus a "cycle" of 2: with 7*6/2 cases and 4*3*2 permutations

a "cycle" of 4 plus a "cycle" of 3: where I'm going to cheat and include the 2+2 in the 4, with 7*6*5/6 cases and (2 {for the 3} * 9 {for the 4}) permutations

That gives me 720+504+630=1854

A program to count the permutations also gives 1854.

ReplyDeleteAnd the prize goes to James!

ReplyDeleteIn case you're curious, the equation for this is

n!((1/(2!)-1/(3!)+1/(4!)-1/(5!)+1/(6!)-1/(7!))

Well, sometime after I admitted inability to think my way through it (at that moment), I hit a search engine.

DeleteAnd found that formula. Plus a recursive one that I like better.

But I figured I would wait, and see if anyone else got close.

This was definitely a challenging puzzle, but now I think that I should have been able to solve it without a search engine...

I would never have gotten there.

ReplyDelete