Thread: Combinatorics homework help?

I know these should be relatively simple but combinatorics has always been my Achilles heel. If you could explain these to me that would be awesome? I am really struggling to wrap my head around how you do these.

How many 5 card hands have two or more kings? How many 5 card hands contain the ace of spades, ace of clubs or both? In how many ways can 3n students be broken up into groups of 3? How many directed graphs are there with n vertices (self loops
ok)? How many tournament graphs are there with n vertices? How many acyclic tournament graphs are there with n vertices?



Thanks!

Hey kkar.

There are a lot of questions that require different approaches.

Usually in mathematics, a lot of people get in the habit of resorting to formulas to solving problem X and when they can't match problem X with formula Y they get stuck (used to happen me all the time).

So what I might ask you is how you have been taught to do these problems and what formulas you have been given.

My guess is they gave you tonnes of formulas with a few superficial examples and expect you to have complete contextual understanding in one or two lectures but i'll wait for your response.

I apologize if the same response is here 3 times (I wasn't sure if it was posting).

Well, yeah you're right. I've been given rules: the permutation formula, the combination formula, the product/addition rule, etc. None of these are precisely any of these are they, they're probably some sort of combination I'm guessing. How do i identitfy what I need to do given the vast number of ways there are to ask a combinatorics problem?

I can give you a few pointers on how to attack general problems.

Combinations are used to calculate the number of ways you can pick so many things (say r) from n objects, and you do it in such a way that you never make a repetition. Permutations allow for repetition.

Now the multiplication rule and the addition rule have direct intuitive links that are often skipped over.

The multiplication rule happens when you want to the total number of ways for the total number of possibilities when you have two variables say A and B where is A has a possibilities, B has b possibilities, then if A and B are completely independent of each other the total number of possibilities you get for each (a,b) pair is a*b.

The addition rule has an intuitive connection in that you add things that are disjoint to each other: so if you have say c possibilities and d possibilities and c and d are completely separate to each other, you add them.

These rules are actually known in probability as the Kolmogorov Axioms (for addition) and also the independence criteria for probabilities (multiplication rule): the only difference between the number of possibilities and a probability is that the probability is normalized by the total number of possible ways that something can exist. Other than this factor, probabilities and possibilities in terms of choosing so many things are exactly the same.

Now a common teaching aid that teaches probability is known as the tree diagram: In a tree diagram you have branches and each branch at each layer is disjoint from each other branch on that layer.

Now the way we use tree diagrams for multiplication and addition is that each branch represents a unique event or possibility of a particular thing happening. When we want to find the probability of getting a particular event we multiply every single node of the tree (probability) from the root node to the leaf to get the probability of that particular branch.

Each branch from the root to the final leaf is disjoint so we can find the probability of getting at least one of a group of events by adding the probabilities up.

This is a way to visualize probabilities for any situation without having to know any formula beyond the multiplication and addition rule and all of the formulas used in probability simply derive expressions that have an analog to the tree diagram.

The algebra is just that: algebra. If you have no connection to the intuition (like you get with a tree diagram) then you will get absolutely confused as to what the hell is going on.

So now we get to the final suggestion.

I would suggest to look at the tree diagrams every individual branch corresponding to a disjoint possibility (i.e. they relate to things that are separate events) and the layer of each branch as a separate variable. For example two dice have two branches.

Now the branches are just a way to organize data and like a tree, there are many ways to represent say n leaves with different branch structures. You don't have to have a tree with the same number of layers for each leaf and in complicated problems, you will have trees where some leaves have many layers and others have only a few and all of this reflects how the possibilities link with each other.

So this gives you a way to do it for probabilities and the connection between number of ways and probability is a straight-forward one: possibilities are just frequencies and probabilities are relative frequencies so if you want to convert a probability to a frequency, if you have N different possibilities in total across all events, then if you have a probability for some event then multiply that probability by N and you will get the number of possibilities.

Once these are put into perspective, you will see the picture emerge.

One final thing about the tree diagrams: different tree diagrams can represent the same thing.

For example I can have a tree diagram for rolling two dice and get a tree diagram with two layers corresponding to the two dice or I can have a tree diagram with one layer that just has the 36 possibilities in that one layer.

Whatever makes sense to in organizing the information is good, just so long as it reflects the information properly. One person might look at the two layer one and see that as intuitive and another person may want to expand every single possibility in one layer. Another one may even want to introduce a lot of extra layers to get the intuition (and some problems may benefit from adding different organizations of the same tree to gain perspective).

The point is though, that if the tree itself has the same probabilities with regards to the actual events, then no matter how organize it, you should always get the right answer by using any of these trees if the tree represents the possibilities of the problem accurately.

Originally Posted by kkar

How many 5 card hands contain the ace of spades, ace of clubs or both?

This may be you Achilles heel. But are you playing us for fools?
There are ways for a five card hand to contain neither the ace of spades nor the ace of clubs

Originally Posted by kkar

In how many ways can 3n students be broken up into groups of 3?

This is a well-known question about an un-ordered partition.
I am going to give you the answer because I realize that you have no idea how it works.
.

Hello, kkar!

Here is some help . . .

The numbr of possible 5-card hands is: .

How many 5-card hands have two or more Kings?

The opposite of "two or more Kings" is: 0 Kings or 1 King.

No Kings: .We pick 5 cards from the other 48 cards.
. . . . . . . .

One King: .We pick 1 of the 4 Kings, and 4 cards from the other 48 cards.
. . . . . . . .

There are: . ways to get 0 or 1 King.

Therefore, there are: . ways to get 2 or more Kings.

How many 5-card hands contain the or the , or both?

Plato has the best solution for this question.