Counting card hands in Discrete Math

In my counting unit, I've used determining card hands for poker every year. This year I have modified this investigation and extended its use. To start things off, I asked students to consider the situation where you are dealt two cards. Their task was to determine how many ways you could be dealt two of the same rank, for example, two kings or two tens.

This task allowed students to focus on a few key concepts without straying too far afield with too little definition. I found that students were much better able to wrestle with key issues by thinking through and representing this problem.

From here, I proceeded to what what have normally been my first card problem: how many way can a hand of four cards contain exactly two pair, that is, two cards of one rank and two cards of a different rank? I asked students to consider the two card hand and how getting two additional cards affects things. I wanted to consider what aspects should be similar or the same and what new elements now needed to be addressed.

I was pleased to see many students readily grasp the similar aspects and then focus on how to deal with the differences that arise in this problem. Several students came to a correct solution rather quickly; much quicker than I have seen solutions arise in the past. Even students who were struggling, were struggling with the aspects that matter rather than going down paths that lead to dead-ends.

With this, I moved to the next aspect, counting the number of ways that a full-house could be dealt in a five-card hand. In this case, students need to consider hands which contain three cards of one rank and two cards of a second rank. Typically, students fail to think about which rank is the three cards and which is the two. Today, very few students did not realize that the order mattered and that three kings and two tens was different from three tens and two kings. Again, solutions were coming to fruition much quicker than I have seen in the past.

Typically, I end the card problems with determining how many ways a five-card hand contains four-of-a-kind. Almost all the students quickly determined this result with many commenting on how easy this problem was. I was pleased with this as this problem usually took longer than it did today.

At this point I departed from my usual direction to address the relative rank and importance of different poker hands. I asked the class which hand should be ranked higher, a full-house or a four-of-a-kind? Based on the fact that four-of-a-kind hands have fewer opportunities of occurring, they decided it should rank higher than a full-house, which it does. I told the class we would be looking at various poker hands and their probability of occurring to rank the importance of poker hands.

This brought up a question from the class as to which poker hand is ranked the highest. Someone suggested a five-of-a-kind but quickly realized this hand was not possible. I mentioned that straight flushes are ranked the highest and a royal flush (10, J, Q, K, A of same suit) is the highest of these hands. Several students said they were curious as to how many ways a straight flush a royal flush could occur. We discussed whether to pursue this right now or later. By a narrow margin students decided they wanted a change of pace, so we pursued a different type of counting problem.

I will revisit the poker hand rankings as we move to discrete probability. This gives students an opportunity to appreciate why, say three of a kind beats two-pair or why a flush beats a straight. We can also pursue what would be the highest ranking hand if a joker is introduced into the deck. There are a lot of variations of this idea that can be pursued and is only limited by available time.

Next year, my discrete math class is being expanded to a full-year course. This will afford the time to pursue some of these investigations and allow the students to develop the poker hand rankings as to which hands should defeat which hands. I think this provides a very real-world application that connects accepted norms in the game of poker to the underlying mathematics that drives those norms.

What learning looks like in the classroom

It's been a while since I've discussed any topics. Partly it's because I am teaching the same classes and, other than tweaks here and there, I hadn't implemented anything really new and different.

The start of the school year has just rushed by. In addition, the math department at my school had some unique challenges to start of the year that are still rippling through our work. Without going into detail, we have three brand new, first-year teachers, we lost two experienced teachers within the first four weeks of school, and we still don't have both of those positions filled with anyone that even remotely resembles a permanent replacement. Couple this with upheaval in the school district (teacher and student walk-outs and protests) and it has been a start of the school-year to remember.

This past summer I was fortunate enough to have the annual Legacy of R. L. Moore - IBL Conference land in Denver. This conference focused on what inquiry-based structures are being used in college classrooms. In two days I picked up an amazing number of ideas that could be brought to the classroom.

It seems odd that the conference was in June and I am just now writing about it in October. But here I am, writing about some of the things happening in my classroom. One of the topics covered during the conference was mindset. It turns out that my school decided this was to be a focus for our professional development when we returned in August. Perfect timing and blending for one of the things I wanted to implement.

I have tried to focus on specific feedback that discusses what a student did well versus making statements like "you're such a good writer" or "that was smart thinking." This coincides well with the research on mindset. One thing that I have implemented is to include a positive, mindset quote at the top of each quiz or test that I give this year. The research suggests that just seeing such a quote may increase student performance on the quiz or test.

Another session that I attended discussed how homework was handled. This is an age-old problem in math. Do you collect homework? Do you grade homework? How do you provide students with feedback on what they completed? This session took a different approach. Problem numbers were written on the board. Students were invited to show their solutions. If more than one student wanted to share their results, those students would converse and make sure they agree on what was presented. Students that were not presenting would then go to a group working on a problem to ask questions or listen to the discussion on problems they struggled with on the homework. Students presenting results receive points. Those watching and asking questions also receive points, at roughly half the level of the presenters. Almost the entire classroom becomes involved in the homework. Students are providing each other with meaningful feedback and students are graded on their work. After all problems are up on the board the homework discussion continues with students looking over all the problems and then asking questions and discussing results.

I have begun to implement this process in my classes. There is some norming that needs to take place. I have also had to remind students not presenting the problems that they should be up at the board listening and asking questions on problems with which they struggled or did not know how to complete. The classes become involved, they ask relevant questions, they argue about results, they question each other, and they make sense of the material. Plus it is easy to check off who is presenting and who is watching or asking questions. I keep weekly tallies and then add the results to my grade-book each week.

Here are a couple of shots of what this looks like:

These aren't staged shots, I just took a couple of quick pictures as the class worked this morning.

I hope to periodically post shots like these through my twitter feed using the hash tag #WhatLearningLooksLike. Join in the conversation and post what learning looks like in your classroom.

This summer I also was a first-time AP Statistics reader. Reading through over 1,000 student responses really drives home what students communicate and don't. The process of training on scoring rubrics also drives home should be communicated based upon the question's prompt. I am working with my AP class on really thinking about what a prompt asks and what needs to be done to answer the prompt.

The other big walk-away from the reading was to keep responses in context. Specify units, don't answer generically. I have told my class, if they write an answer, they need to consider adding "for example." If they read the response and they could add a "for example" then they better add it so there response is in context.

That's all for now. I'll try to not stay away so long from posting.

Have a great school year!

Khan Academy's Cryptography Unit

The Khan Academy has developed a complete unit on cryptography that fits perfectly into the discrete math class.

For my class this year, I focused on the RSA encryption pieces that fall under Khan's Modern Cryptography lessons.

These lessons provide a conceptual foundation and then make use of the core mathematics, explained in a way that makes it easy to follow the process to perform RSA encryption. After working through much of the math in class, it was a nice summation of what we were learning.

If you are teaching the mathematics of cryptography, I highly recommend these videos.

Graph Theory Unit - Revised for Spring 2014

Below is the outline of the Graph Theory Unit that I used for my discrete math course this year. Switching this unit to come immediately after the counting unit worked out tremendously. Students were engaged, there were rich mathematical discussions around the concepts, and students found the material interesting and challenging.

Presenting a theorem or definition and then allowing students to consider whether figures met the criteria described worked well. This enabled them to then construct their own representations and provided for deeper discussions on the characteristics of graphs. The idea of proving ideas really took hold during the unit. One example was during the discussion of Hamilton circuits. When asked what characteristics would indicate the existence or absence of a circuit, students discussed the presence of vertices of degree 1 or the presence of cut edges. They were able to articulate specifically why this would preclude the presence of a Hamilton circuit. They were then able to extend this idea for multiple vertices of degree 1 and provide an argument that for a Hamilton path to exist the number of vertices of degree 1 would have to be less than 3. To me, this was exciting stuff. This example is reflective of how the entire unit progressed.

The next unit covers number theory and cryptography. As this veers back to a more cerebral topic, the graph theory provided a good break into a more visual and hands-on topic.

Unit 2 – Graph Theory

The second unit focuses on graphs and trees. This unit includes graph representation, traversing paths, coloring graphs, tree traversal and spanning trees. Both historical problems such as the bridges of Konigsberg and current issues will be discussed in the context of graphs and trees.

1.      U3-01 intro to graphs

a.      Mail delivery problem

                                                                          i.      What’s the shortest time you found

b.      Delivery Investigations

                                                                          i.      Five paths

c.       Konigsberg Bridges

                                                                          i.      State problem and see what students think

                                                                        ii.      Show representation and discuss

d.      Define graph

                                                                          i.      Show example of same graph drawn two different ways

1.      Be sure students understand how these are representing the same graph

e.      Define loop, adjacent vertices, path, circuit, Euler path, Euler circuit

                                                                          i.      Clarify using graph to illustrate definitions

f.        Define degree of vertex, even and odd, connected, component, and cut edge

g.      Practice drawing graphs with specific characteristics

                                                                          i.      Problem 7. Draw a graph which has 6 vertices, 4 loops and 2 multiple edges.

                                                                        ii.      Problem8. Draw a graph with 5 vertices, each of degree 4, which has no loops or multiple edges.

                                                                      iii.      Problem 9. Draw a graph with 3 vertices of degree 2 and 2 vertices of degree 3.

                                                                       iv.      Problem 10. Draw a graph with 2 vertices of degree 2 and 3 vertices of degree 3.

                                                                         v.      Problem 11. Draw a graph with 1 vertex of degree 1, 2 vertices of degree 2, 3 vertices of degree 3 and 4 vertices of degree 4.

                                                                       vi.      Problem 12. Draw a graph with 8 vertices and 6 edges which contains no circuit at all.

                                                                     vii.      Problem 13. Draw a connected graph with exactly 3 edges that does not have an Euler path.

h.      Exit

                                                                          i.      What graph terms make the most sense to you? What makes these understandable to you?

                                                                        ii.      What graph terms are the most confusing to you? What are some things you can associate with each term that will help you to recognize and understand their meaning?

2.      U3-02 Graph Theorems

a.      Odd vertex theorem

                                                                          i.      State and have students discuss why

                                                                        ii.      [bring in induction here or in conjunction with some Euler theorems?]

b.      Even vertex theorem

                                                                          i.      State and have students discuss why

c.       What does Odd and Even vertex theorems imply about graphs having Euler paths and Euler circuits?

d.      First Euler path and circuit theorems

                                                                          i.      First Euler Path Theorem. If a graph has an Euler path, then

1.      it must be connected and

2.      it must have either 0 or 2 odd vertices.

                                                                        ii.      First Euler Circuit Theorem. If a graph has an Euler circuit, then

1.      it must be connected and

2.      it must have no odd vertices.

                                                                      iii.      Draw examples

e.      Theorems tell when graphs won’t have Euler path or circuit

                                                                          i.      Will all remaining connected graphs have Euler paths or circuits?

                                                                        ii.      discuss

f.        Fleury’s Theorem

                                                                          i.      Explain steps

g.      Show graph #5 from prior lesson

                                                                          i.      Does Fleury’s theorem apply?

                                                                        ii.      How can you modify the graph so that Fleury’s theorem applies?

h.      Students modify graph and traverse following rules

i.        What conclusions can you make about when a graph has an Euler path or an Euler circuit?

j.        Second Euler Path theorem and circuit theorem

                                                                          i.      Second Euler Path Theorem

1.      If a graph is connected and has exactly 2 odd vertices, then it has an Euler path.

                                                                        ii.      Second Euler Circuit Theorem

1.      If a graph is connected and has no odd vertices, then it has an Euler circuit (which is also an Euler path).

k.       Show graph #5, can’t bulldoze through neighborhood

                                                                          i.      Minimum multiple edges that can be added to apply Fleury’s theorem is called Eulerization of graph

l.        Euler path circuit ws1

m.    Euler path circuit ws2

n.      Exit

                                                                          i.      Summarize understanding of Euler paths and Euler circuits

                                                                        ii.      What questions do you have about graphs, paths, and circuits

3.      U3-03 Mail route practice

a.      Simple graph (page 12 of Clark’s graph theory)

b.      Original neighborhood problem from U3-01

c.       Park-pond graph (page 13 from Clark’s graph theory)

                                                                          i.      Mail Route Practice Handout

d.      Exit

                                                                          i.      What are things to remember when making an Eulerization of a graph or finding an Euler path or circuit?

4.      U3-A1 quiz on graphs

5.      U3-04 Paths

a.      Hamilton path -  a simple path that passes through every vertex exactly once

b.      Hamilton circuit – a simple circuit that passes through every vertex exactly once

c.       What are the similarities and differences between Euler and Hamilton paths and circuits?

d.      Examples

                                                                          i.      Questions about which could ever have path or circuit

                                                                        ii.      Have student’s conjecture about when a graph cannot have a Hamilton path and/or circuit

1.       A simple graph with one vertex of degree one cannot have a Hamilton circuit.

2.       A simple graph with 3 or more vertices of degree one cannot have a Hamilton path.

3.        A simple graph with a cut edge cannot have a Hamilton circuit.

4.       A simple graph with an Euler path has a Hamilton path.

e.      Dirac’s Theorem – a simple graph with 3 or more vertices such that the degree of every vertex equals at least half the number of vertices has a Hamilton circuit

                                                                          i.      Show previous graphs and ask if any fit the theorem’s requirements

f.        Ore’s Theorem – a graph with 3 or more vertices such that the degrees of every pair of non-adjacent vertices sum to the total number of vertices has a Hamilton circuit.

                                                                          i.      Show previous graphs and ask if any fit the theorem’s requirements

g.      For each theorem, draw a graph that meets the theorem’s requirements

h.      Practice

                                                                          i.      Use the theorems to determine if a Hamilton circuit  exists

i.        Exit

                                                                          i.      The reason I find Hamilton path and circuits easy to work with is because____________.

                                                                        ii.      The aspect of Hamilton paths and circuits I found most confusing and/or difficult was ____________ because __________.

6.      U3-05 Planar graphs (Rosen page 718 and JIBLM)

a.      Can these three houses be connected to the three utilities without any utility lines crossing?

b.      Planar graph: A graph that can be drawn in the plane without and edges crossing and maintains all the same edge connections.

c.       When attempting to determine if a graph is planar, it is often helpful to think of the edges as being made from rubber bands. Vertices may be moved around if that is helpful. Are any of the following graphs planar? (Show four graphs from JIBLM)

d.      Can this graph be drawn as planar? (Show 3-D cube.)

e.      How might you determine if a graph is planar or not?

                                                                          i.      Discuss ideas and check

f.        Look at the following graph. What is the largest subset of vertices that can be easily drawn as a planar graph.

g.      Using the idea just discussed, can the following be drawn as a planar graph? (Show original house-utility problem.)

h.      Euler’s formula

                                                                          i.      Follow jiblm investigation

                                                                        ii.      On a separate sheet of paper, draw seven different connected planar graphs. Label them G1, G2, G3, G4, G5, G6 and G7.

                                                                      iii.      Create a table for the numbers faces (f), vertices (v) and edges (e) for each graph.

                                                                       iv.      When you are finished examine your answers and look for a relationship between these values that would allow you to predict one of them if someone tells you the other two.

                                                                         v.      I have a connected planar graph with 257 vertices and 192 faces. How many edges does it have? How can you know for sure if your guess is correct?

                                                                       vi.      On a separate sheet of paper draw a connected planar graph G with exactly 9 edges. You may include in it a loop (edge connecting a vertex to itself) and a multiple edge (more than one edge between the same two vertices). Be sure that it has several different faces. Now, on another sheet,“grow” the same graph as a sequence of 10 partial connected planar graphs labled G1, G2, G3, G4, G5, G6, G7, G8, G9, G10 = G, like this.

1.       1. Start with a single vertex as G1.

2.       2. Construct each graph from the previous one doing one of the following:

3.       (a) Add a new vertex and a new edge connecting it to an old vertex.

4.       (b) Add a new edge connecting two existing vertices.

                                                                      vii.      Examine each of your graphs and complete the table.

                                                                    viii.      Do each of the following.

1.        Tell what the value of f +v−e is for a single vertex (G1).

2.        Tell how the construction 2(a) affects the value of each of f , v, e and f +v−e.

3.        Tell how the construction 2(b) affects the value of each of f , v, e and f +v−e.

                                                                       ix.      Euler’s Theorem

1.       If a connected planar  graph has f faces, v vertices, and e edges then f + v - e = ?

i.         Prove that a graph is not planar using Euler’s Theorem.

                                                                           i.      Need help on justifying lemma before can include this piece.

j.        Exit

                                                                          i.      The most interesting thing I learned about planar graphs was ____________. I found this interesting because ____________.

                                                                        ii.      One question I have about planar graphs is _________?

7.      U3-06 Isomorphisms and Complete and Self-complimentary graphs

a.      Provide an example of two drawings that represent the same graph

b.      Two drawings are isomorphic if and only if all adjacent vertex relationships are maintained. Label and demonstrate this using the example graph.

c.       What are conditions that would indicate that two graphs are not isomorphic?

                                                                          i.      Have students discuss and list ideas

1.      Have students provide counter-examples for those that are incorrect

d.      Using these ideas, determine if the following pairs of graphs are isomorphic or not (using examples from Rosen)

e.      Complete the Isomorphic Graphs Worksheet and indicate explicitly why or why not each pair of graphs is isomorphic.

                                                                          i.      For problem 6, draw in extra edges to make each vertex degree five and ask students to consider whether these are now isomorphic.

f.        A complete graph of n vertices, denoted by K_n, is a simple graph that contains exactly one edge between each pair of distinct vertices.

                                                                          i.      Draw K_n for n=1-6

g.      Counting connection

                                                                          i.      Counting edges

1.      How many edges does K₁₀ have?

2.      How many edges does K₁₀₀ have?

3.      How many edges does K_n have?

                                                                        ii.      Counting Hamilton circuits

1.      How many Hamilton circuits exist for K₁  - K₅?

2.      How many Hamilton circuits exist for K_n?

                                                                      iii.      Note: these problems spiral nicely back to counting, Pascal’s triangle, figurate numbers, finite differences, and Gaussian summation

h.      The complement of a graph G, consisting of n vertices, is a graph that also has n vertices and contains all of the edges that are not in G but are in K_n. The complement is denoted by G-bar or G^c.

                                                                           i.      Can make connections to complements in probability.

                                                                         ii.      Draw the complement  of the following graphs

1.       Use rectangle, star, and triangle

i.         If two graphs G and H are isomorphic, does this mean that G-bar and H-bar are also isomorphic? Prove or provide a counter-example?

j.        Can a graph ever be self-complementary? What would this look like?

k.       What characteristics must a graph possess in order for G to be isomorphic to G-bar?

                                                                           i.      Note: this question is posed as a preview to the number theory work, specifically modular congruences, in the next unit.  

l.         Exit

                                                                           i.      What did you find most interesting about isomorphisms, complete graphs, and complementary graphs?

                                                                         ii.      What questions do you still have about these topics?

8.      U3-07 Graph coloring (Rosen page 727) [needs to be developed – no time this year]

a.      Definitions

b.      Chromatic number

c.       Four color theorem

d.      Examples

e.      Practice

9.      U3-08 Simple graph proofs

a.      These are a series of problems presented by Dr. Patty McKenna at the annual NCTM conference in Denver, 2013. [include if time permits – may want to make some of these mid-term questions]

10.  U3-A1 Assessment on graphs