Current Events > this combinatorics problem took me way too long to get last night. can you get i

(+) Yeah! (+)

t?

80/80

Mr. Moneybags recently decided to become more fashionable. He has 9 distinct rings which he wants to wear on the 4 fingers of his right hand. Assuming his fingers are long enough to fit all 9 rings, how many different ways can he do this (note: he wears all 9 rings at any given time, never less)?
---

i know everybody is furiously crunching away at this
---

god damn it, the first post should say never fewer*

In the word MATHEMATICS, how many "words" (i.e. arrangements using all letters) can you make such that all vowels are in relative alphabetical order (i.e. they needn't be consecutive)?
---

Assuming the ordering of the rings on each individual finger als matters, I'm thinking 12!/3!
---

Second is 11!/4!
---

DifferentialEquation posted...

Assuming the ordering of the rings on each individual finger als matters, I'm thinking 12!/3!

the ordering does matter, because each ring is distinct

but yeah that is also what i got. what was your approach? i used stars and bars to get 12C9, then multiplied that by 9! and it reduces to 12!/3!

it took awhile to figure that approach out and only after we finally found a close enough example in the book...
---

DifferentialEquation posted...

Second is 11!/4!

hrm...

we got 11!/(4!2!2!)

---

organicbamf posted...

DifferentialEquation posted...

Second is 11!/4!

hrm...

we got 11!/(4!2!2!)

You're right. I forgot to take out the 2!'s for the M's and T's.
---

For the first one, if you're arranging 9 unique rings on 4 fingers, then you're just arranging 9 unique objects with 3 non-unique separators/dividers.
---

This is one of my favorite problems from a combinatorics book (though you don't need combinatorics to solve it).

You have a regular 8x8 chessboard. You also have a bag of dominoes; a single domino is a rectangle which covers two adjacent (non kitty corner) squares on the chessboard. You take a pair of scissors and remove two squares from the board which were at opposite corners of the board (i.e. two starting rook positions which were diagonal from each other).

Is it now possible to cover the board with dominoes such that no dominoes overlap or hangover the edge of the board?
---

DifferentialEquation posted...

This is one of my favorite problems from a combinatorics book (though you don't need combinatorics to solve it).

That one's a classic, so I can't claim to have figured out the answer, but it's of course not possible with those squares removed. Reason has to do with the nature of a domino. I'll leave it at that in case someone is trying to work it out on their own.
---

DifferentialEquation posted...

This is one of my favorite problems from a combinatorics book (though you don't need combinatorics to solve it).

You have a regular 8x8 chessboard. You also have a bag of dominoes; a single domino is a rectangle which covers two adjacent (non kitty corner) squares on the chessboard. You take a pair of scissors and remove two squares from the board which were at opposite corners of the board (i.e. two starting rook positions which were diagonal from each other).

Is it now possible to cover the board with dominoes such that no dominoes overlap or hangover the edge of the board?

Yes, otherwise you wouldn't have bothered asking the question.

No, because you've removed two squares of the same colour. I'm not sure what this has to do with combinatorics in the sense of this topic though, this is really more of a graph problem.
---

DifferentialEquation posted...

This is one of my favorite problems from a combinatorics book (though you don't need combinatorics to solve it).

You have a regular 8x8 chessboard. You also have a bag of dominoes; a single domino is a rectangle which covers two adjacent (non kitty corner) squares on the chessboard. You take a pair of scissors and remove two squares from the board which were at opposite corners of the board (i.e. two starting rook positions which were diagonal from each other).

Is it now possible to cover the board with dominoes such that no dominoes overlap or hangover the edge of the board?

yeah, that is a good one

i have read the wiki on it before tho

edit: or maybe saw it on numberphile? i don't recall where now

Frostshock posted...

No, because you've removed two squares of the same colour. I'm not sure what this has to do with combinatorics in the sense of this topic though, this is really more of a graph problem.

the first half of my class was over graph theory fam

new question, as i turned in the hw and after asking my prof if my approach was correct, he said no :(

Suppose you wish to deal out a hand of 13 cards to 4 players (North, South, East, West) such that each player has exactly 4 cards of one suit and 3 cards of each remaining suit, how many ways are there to do this?

i was thinking that given a suit, i want to make sure each player gets at least 3 of that suit, so it would be (13 choose 3)*(10 choose 3)*(7 choose 3)*(4 choose 3) = (13 multi-choose 3,3,3,3)

this can be done for each suit, but the suits are disjoint, so you can say 4*(13 multi-choose 3,3,3,3). the remaining card of each suit could be distributed 4! ways. i thought this would ensure each player is dealt the 3 required, and then gets dealt a 4th of some remaining suit. so how do you approach this problem?

btw, generating functions are dope as hell
---

tag
---

Start by dealing everyone 3 cards of 3 different suits.

There are 13 ways to select a card from a suit that will not be part of this initial deal. Take one out, now there are 12c3 * 9c3 * 6c3 (and an additional trivial factor of 3c3) ways to create the four 3 card subsets that will be dealt out. And there are 4! ways these suit subsets can be distributed to the four players. AND this has to be done for each suit, so this whole monster is permuted to the power of 4.

So this first part can be done in

(13 * 12c3 * 9c3 * 6c3 * 4!)^4

Now the last bit is to take the 4 remaining cards, one from each suit, and hand them out. There are 4! ways to do this, so the final count is 4! multiplied by that monster above.

This makes sense to me but it's easy to make mistakes when counting cards.
---

according to the proposed solutions by our TA, you're off by a few orders of magnitude :\
---

organicbamf posted...

according to the proposed solutions by our TA, you're off by a few orders of magnitude :\

Is the final 4! supposed to be inside the parentheses, or is my approach entirely wrong?

This is already a pretty huge number. Fucking cards.
---

that's the proposed solution

my problem is my teacher said i was over-counting, but i'm p sure my number was much, much less than that... so i was over-counting in some areas, but not counting enough in others?

i fucking hate card problems >:(

probably why he likes bridge and mtg so much tho
---

Ah, that approach is much safer. I can see now how my method covers every case, but double (more like...1000x) counts a lot of possible hands.
---

you guys

generating functions are so fucking cool
---

This was like the one thing I could never learn in school lol XD

I'm so stupid at combinations :P
---

MutantJohn posted...

This was like the one thing I could never learn in school lol XD

I'm so stupid at combinations :P

oh, i'm terrible at them. setting up these problems is like mysticism

i literally aced the graph theory part of this class and i'm hoping that keeps my grade afloat as i drift along these lol

altho generating functions i think are fairly straight forward
---