Sagetex: Combinatorics 10/11

Comb10I've added 2 problems to the Sagetex: Combinatorics/Statistics page.

Problem Type 10: Suppose a system has 6 independent components, each of which is equally likely to work. Now suppose the system works if and only 5 components work. What is the probability the system works?

In problem type 10 the number of independent components is random. Problem Type 11 has students calculate C(n,k) and P(n,k) for random n, k.

Odds and Ends: July 9,2014

Several odds and ends:

  1. I've updated the Sage Cheat sheet for version 6.2; correcting errors, typos, and any deprecated commands. You can find it on the Python/Sage page (at the top).
  2. The OP/ED page of the NY Times has letters related to the common core article mentioned in a previous post. The letters are here.
  3. Wisconsin is gearing up for a war on common core. "If you think there was a fight over Common Core educational standards in the Capitol earlier this year, think again. Interviews with dozens of candidates show that it was just a warm-up for the war coming next year over those standards."...."WisconsinEye interviews with more than 70 candidates in Aug. 12 primary elections show that scrapping Common Core standards, or reasserting the authority of local school boards to set their own academic goals, is a top priority of Assembly Republicans. Most Democratic candidates defend Common Core."

Sagetex: Random Bipartite Graphs

RandBiSummer's here and I've had the luxury to just play around. I try to put extra math into the curriculum through either warm up problems, extra credit problems, or examples in the  curriculum that I follow. Discrete math figures prominently in the extra math. In my opinion, discrete math deserves a prominent place in the high school curriculum; it certainly deserves a bigger share of the curriculum. But in a top down system you can't add extra material to the curriculum that the average math teacher has never seen and expect it to be implemented properly.

Graph theory is ideal because it requires little mathematical background to understand and solve problems yet it also provides a way to introduce theorems (many of a basic nature that high school students can understand) along with counterexamples thereby providing a basic primer into the sort of considerations that mathematicians are looking at. In the past, geometry had been the topic for introducing proofs but it's dry as dust and now common core has ripped out much of the proof content so that your typical student can go through math and with very limited exposure to theorems/proofs/counterexamples.

Graph theory would be a way to get that back in a way that is much more interesting than the dry "2 parallel lines are cut by a transversal" proofs that have bored generation after generation. You can even connect to matrices through the adjacency matrix of a graph. Topics like recurrence relations and generating functions complement the curriculum of calculus (power series) and probability. Unfortunately, common core has de-emphasized proofs and matrices and upped the exposure to statistics, so I think it's my duty to undue the damage of the curriculum.

Which brings us back to the current post. Bipartite graphs which have the same number of vertices in each partite set provide a way of determining whether a suitable job can be found for each person so that everyone has a job (see the "Matching" section for the link above). One partite set with vertices, say, A,B,C,D have edges to the other partite set of vertices (a,b,c,d) representing jobs based on whether the person is qualified to do the job. The question becomes, Is there an assignment of jobs so that everyone has a job they're qualified to do? If yes, then there is a (perfect) matching for the graph. If no then there needs to be an explanation as to why no such assignment is possible (Hall's Marriage Theorem).

As a teacher the problem I usually face is finding lots of examples that can be used in the classroom or on a test/quiz. Sage/sagetex is the tool that works best for me. The code generates bipartite graphs so that the number of vertices in each partite set is equal and the probability of an edge being selected for the picture is 1/2.  The code is posted on the Graphics page along with sample output (the PDF shown above). The number of vertices is a random number set between 4 and 8 here: N = Integer(randint(4,8)). The probability of the edge being chosen is set here: if Integer(randint(0,1))==1:

It would be relatively simple to choose a larger number than 1, such as 9, and draw the edge if the number chosen is between 0 and 7 but don't draw the edge if the number chosen is 8 or 9. That would make the probability of the edge appearing to be 80%.

Through setting the parameters to your liking and repeatedly compiling the code you can generate many examples that you can use. If you're particularly ambitious you can add extra code spit out example that have (or fail to have) a perfect matching. Of course, Sage can help with that.

Odds and Ends: July 1, 2014

FlowChartA few minor changes:

  1. I've added the flowchart/tree diagram (PDF and tex file) to the Graphics page. When talking about linear systems I've found students slow to pick up the vocabulary of consistent/inconsistent and dependent/independent. The flow chart helps students to remember the difference.
  2. The important graph from the last post, has been posed as a problem: Find the derivative of $latex f(x)=x^2\sin(1/x^2)$ if $latex x \neq 0$ and $latex f(0)=0$ at 0. I think it would be well suited as a warm up problem at the beginning of class to motivate the subsequent discussion.
  3. The NY Times has a good article on the difficulties with Common Core.