# Why does undergraduate discrete math require calculus?

Often undergraduate discrete math classes in the US have a calculus prerequisite.

Here is the description of the discrete math course from my undergrad:

A general introduction to basic mathematical terminology and the techniques of abstract mathematics in the context of discrete mathematics. Topics introduced are mathematical reasoning, Boolean connectives, deduction, mathematical induction, sets, functions and relations, algorithms, graphs, combinatorial reasoning.

Is passing calculus merely a signal that a student is ready for discrete math?

Why isn't discrete math offered to freshmen — or high school students — who often lack a calculus background?

-
Last year I tutored a kid in the computer science department "discrete mathematics" course, alternate to the mathematics department one. The lectures went through incredible gyrations to avoid calculus arguments that really would have simplified everything. So my response is that the course you want is really hard, and in that situation students do better with things stretched out. –  Will Jagy Jun 4 '10 at 19:03
Community wiki? –  Steven Gubkin Jun 5 '10 at 12:58
I don't know how it's done in US, but here in Germany the first calculus course contains some mathematical basics such as induction, the Peano axiom, the notions of sequences and functions... they actually belong into Discrete Mathematics, but Discrete Mathematics rather prefers to use them then to introduce them. Of course, real calculus is not needed in Discrete Mathematics until much later (and usually, all applications of calculus in Discrete Maths require even more linear algebra than calculus). –  darij grinberg Jun 5 '10 at 16:17
I have a big issue with this question, and that is the unspoken assumption that there is such a thing as "undergraduate discrete math". (I'm not blaming the OP, btw, everyone does it!) The subject is so vast that an UG math course could (and sometimes will) contain anything, including very calculus-oriented topics. Asymptotic notations, generating functions, I would want 2 solid semesters of calc in students before broaching these subjects. The distinction between discrete and calc is arbitrary to begin with, or at least does not appear in applications, hence the "Concrete Math" appellation. –  Thierry Zell Sep 7 '10 at 16:57
show 1 more comment

A significant portion (my observation was about 20-30% at Berkeley, which means it must approach 100% at some schools) of first year students in the US do not understand multiplication. They do understand how to calculate $38 \times 6$, but they don't intuitively understand that if you have $m$ rows of trees and $n$ trees in each row, you have $m\times n$ trees. These students had elementary school teachers who learned mathematics purely by rote, and therefore teach mathematics purely by rote. Because the students are very intelligent and good at pattern matching and at memorizing large numbers of distinct arcane rules (instead of the few unifying concepts they were never taught because their teachers were never taught them either), they have done well at multiple-choice tests.

These students are going to struggle in any calculus course or any discrete math course. However, it is easier to have them all in one place so that one instructor can try to help all of them simultaneously. For historical reasons, this place has been the calculus course.

-
Excellent diagnosis! I might add that struggles in calculus and ODE courses are often due to poor algebra preparation, whereas struggles in discrete mathematics and abstract algebra are due to complete lack of experience with abstract concepts and abstract reasoning. So it makes sense to start with calculus. –  Victor Protsak Jun 4 '10 at 21:39
The diagnosis is correct, but do they really acquire the necessary skills in the calculus course? –  Deane Yang Jun 4 '10 at 22:14
@Deane: Frequently they don't, but the cynic in me says that instructors or programs which don't notice and try to solve this problem the right way are just as happy to have this problem solved the wrong way, which is to say that the student struggles for reasons unclear to him or her and is discouraged from taking further mathematics. (Given constraints on resources, solving the problem the right way for most students frequently isn't a viable option.) –  Alexander Woo Jun 4 '10 at 22:47
@Deane & Alexander: Paraphrasing a well-known quip, you can't help all the people all the time. I think it makes sense to require people aiming for a math or science degree to take a college level calculus course first; if they decide that science is not their thing, after all, I see nothing wrong with that. I also think that there should be a different track for liberal arts majors who may never take calculus, with a discrete mathematics course that does not emphasize sets and structures; many schools do have such a course to satisfy the quantitative reasoning requirement. –  Victor Protsak Jun 4 '10 at 23:15
(At the risk of starting a discussion) I agree that most students do not understand multiplication of integers, and hardly any at all understand multiplication of fractions. Why are we (mathematicians as a community) not giving elementary school concept tests to our incoming freshmen, and teaching them to their level of understanding? Why do we make them memorize pages of calculus formulas when they do not understand the basics of arithmetic? So we don't have to deal with them for more than a year? That is incredibly sad. –  Steven Gubkin Jun 5 '10 at 12:57

Perhaps it's done to ensure a certain level of mathematical maturity. For example, here is what one author writes in the preface to his discrete mathematics text:

This book has been written for a sophomore-level course in Discrete Mathematics. [. . .] Students are assumed to have completed a semester of college-level calculus. This assumption is primarily about the level of the mathematical maturity of the readers. The material in a calculus course will not often be used in the text.

(Eric Gossett, Discrete Mathematics with Proof, 2nd ed., John Wiley and Sons, 2009)

-

In the context of very bright high school students with strong mathematics backgrounds, it is typical to teach discrete math to students without requiring calculus as a prerequisite. In particular, this is the norm both at the Ross program (where 2nd year students often had a combinatorics class) and at Mathcamp (where many discrete math classes are often taught without calculus as a prerequisite). Both summer programs avoid teaching calculus because it messes up highschool students who are going to be stuck taking calculus whether they already know it or not.

In particular, it's quite possible to teach formal differentiation and integration of power series in order to do generating functions without discussing traditional differentation or limits. In fact, the Ross problem sets had a problem set developing the basics of calculus for polynomials (linearity, Leibniz rule, etc.) without ever discussing limits. I'd already learned calculus at that point, but not all the students had. And the students who didn't know calculus didn't have too much of a difficulty with that problem set. It's certainly easier than proving that the group of units modulo p is cyclic.

So the reason for requiring such a prerequisite for a college course is not that it's actually a logical prerequisite, but instead for sociological reasons along the lines of Alex's answer.

-
I learned formal differentiation in grade 4 and didn't learn (let alone understand) limits until grade 7 or later, so of course it's possible. But I don't see where differentiation is used in an essential way in an introductory discrete math course. For generating functions (and that's already combinatorics), generalized Newton binomial is usually sufficient. –  Victor Protsak Jun 5 '10 at 7:19
To back up Noah's claim, I have taught topology and abstract algebra at Mathcamp without calculus as a prerequisite with no problem. –  Alfonso Gracia-Saz Jun 7 '10 at 0:55
On the other hand, the average student at ROSS/Mathcamp is very different from the average first-year student at around 98% of US universities, and very different from the average math major at above 90% of US universities. (Both of those are conservative estimates - I don't mean to insult either program.) –  drvitek Aug 31 '10 at 18:20

I see three reasons.

Generating functions is an example of tools used in discrete mathematics. Calculus definitely helps working with them.

Binomial coefficients arise frequently in discrete math. Many formulas about these coefficients can be handled by calculus.

Also, even if you are interested only on what happens for finite sets of size n, probably you will want to let n goes to infinity at some point, and then continuous laws, integrals and the like will appear naturally.

Still I think that it is possible to teach a beginner course in discrete mathematics which does not rely on calculus.

-
"Many formulas about these coefficients can be handled by calculus." You probably mean: Many formulas about these coefficients are standardly handled in a calculus course. –  darij grinberg Jun 5 '10 at 16:21
As for the third reason, there is absolutely no necessarity why asymptotics must be included in a discrete maths course. While exact results are usually important for asymptotics, there is almost no flow in the opposite direction. –  darij grinberg Jun 5 '10 at 16:22

Sometimes it's difficult even to write an answer to a discrete math problem without an integral or two.

Example. The number of integer lattice points that satisfy the conditions $$-n\leq x,y,z\leq n,\quad -s\leq x+y+z\leq s$$ for some $n$, $s\in\mathbb N$, is equal to $$\frac{1}{2\pi}\int\limits_{-\pi}^{\pi}\left(\frac{\sin \frac{2n+1}{2}t}{\sin\frac {t}{2}}\right)^3\frac{\sin \frac{2s+1}{2}t}{\sin \frac{t}{2}} dt.$$

-
Well that's not the sort of discrete math problem you're taught in an intro class –  DoubleJay Jun 4 '10 at 19:16
Why not? This is a problem from Chapter 1 of the Pólya-Szegö problems' book. I learned it myself in an undergrad course. –  Andrey Rekalo Jun 4 '10 at 19:38
Uhm... isn't your example rather a property of this integral than a formula for the number of lattice points? I mean, the number of all integer lattice points satisfying -n <= x,y,z <= n and -s <= x+y+z <= s can be easily computed using high school methods and a bit of case distinction... –  darij grinberg Jun 5 '10 at 16:20
Well, the lattice points can be counted using a generating function. But I don't know how to write the answer in a compact and elementary form. I'd appreciate if you give any details of what you have in mind. –  Andrey Rekalo Jun 5 '10 at 16:39
It would be a term with a case distinction, so I prefer not to, but I just want to say that the integral formula is not necessarily the most natural way to write it down... –  darij grinberg Jun 8 '10 at 13:58

Where I work, the first-semester science students are offered two mathematics courses: One-variable calculus and introductory discrete mathematics. Obviously the emphasis in the latter course cannot be on solving counting problems in terms of elementary functions, since calculus is the main tool for handling these. The course contains combinatorics, graph theory and number theory up to congruences. Calculus is not a prerequisite.

-
That's not a fair assessment at all. Trying to convince a pure humanities student (or even a biologist) that they are going to need to know how to integrate is difficult - because chances are, although they might be balancing their checkbook or examining their investments at some point, frankly they probably WON'T be using their first semester calculus.The applicable math will generally be RE-taught in whatever bio classes require it in as much form as they'll tend to use it, and for the rest of them who never see it comes up again it confirms... –  Gwyn Whieldon Jun 5 '10 at 6:35
...for them that math classes are a series of irrelevant hoops thrown at them by people extorting them for money. If the goal of forcing students to take a math class is to give them (hopefully) both critical reasoning skills and potentially useful math, it doesn't seem that his school is sacrificing their "education." It's frustrating lying to (many) students about how "they'll use calculus in their further studies" when you know that the vast majority of them will not - and will just leave with the confirmed belief that "math is hard and isn't for them." –  Gwyn Whieldon Jun 5 '10 at 6:38
Well, if I say where I work, I might as well not have a pseudonym at all. The introductory discrete math course is offered because of demand from the computer science department. The CS students are required to take calculus, but not in their first year. The CS students are also required to take an introductory probability and statistics course, and calculus is a prerequisite for that. Basically, we have to adapt our earliest courses to the needs of other departments. We also have a less demanding, cookbook calculus course, for students outside the hard sciences, like biology. –  engelbrekt Jun 5 '10 at 6:56
Our standard calculus course is oriented towards rigorous proofs, so it is unrealistic to expect all students to be well enough prepared for it in the first semester. We start from the completeness property of $\mathbb{R}$ and prove the major theorems, such as the Extreme Value Theorem, the Intermediate Value Theorem, the Riemann integrability of monotone functions, the Riemann integrability of continuous functions, and the Fundamental Theorem of Calculus. By the way, the place where I work is not that big, and we cannot have many tailor-made calculus courses, like in the USA. –  engelbrekt Jun 5 '10 at 7:06
I could guess it wasn't in the USA from your description of "our standard calculus course":) –  Victor Protsak Jun 5 '10 at 7:23

In the context of college students, I agree with Alexander Woo's explanation. By the way, the best and the brightest often place out of calculus (that's the case at Yale, and I imagine it's not that much different at Berkeley), so the percentages of weak students at best schools aren't as dire as you might think.

Concerning the last question,

"Why isn't discrete mathematics offered to high school students without calculus background?"

Not only is that possible, but it had been the norm in the past within the "New Math" curriculum, when everyone had to learn about sets and functions in high school. This ended in a PR disaster and a huge backlash against mathematics, because generations of students were lost and got turned off by mathematics for life; some of them later became politicians who decide on our funding. Consequently, it was abandoned. (Apparently, calculus in HS was introduced as a part of the same package and survived.)

I'd be interested to know if there are any high school – college partnerships that offer discrete mathematics to H.S. students with strong analytical skills, and how do they handle the prerequisites question.

-
My percentage guestimate comes out of TAing an introductory CS course which was almost impossible to place out of. They are really that dire. It is easier to get through calculus without noticing this problem. Considering most high school math teachers never learned anything about sets and functions, it isn't surprising that all the students were lost. –  Alexander Woo Jun 4 '10 at 22:38
That's more statistically reliable, then, but who is required to take it? Everyone or just math/CS students + those others, including liberal arts majors, who elect it (out of several options) in order to fulfill the math/quantitative reasoning requirement? –  Victor Protsak Jun 4 '10 at 23:20
Only people intending to be CS majors were required to take it. This was in 2003 if I remember correctly. –  Alexander Woo Jun 5 '10 at 20:35

When I was at Buffalo 30 years ago, Tony Ralston advocated teaching discrete math instead of calculus to 1st year students. I taught it out of some notes he had prepared, and thought the students found it harder than calculus. It was easier to relate calculus topics to things they already knew about than it was to do that for the topics in his notes.

I'm pretty sure those notes became a textbook, so you can probably get a copy and see one man's idea of what should/could be taught to students before calculus.

-

Although calculus is not frequently used in discrete mathematics it is nice to know that the students have had at least some exposure to sets and functions. I am teaching discrete this summer and find myself saying "you have seen this in calculus" when talking about several fundamental concepts.

When doing proofs in a calculus course I usually try to point out the fundamental concepts from the course that are needed and in a discrete course the actual process of how do do a proof is studied more closely. Again it is nice to know that at least the students have seen proofs before and we can build on this exposure.

-
It may shock you, but most students don't even see proofs in calculus, and of those who do, very few retain anything. –  Victor Protsak Jun 4 '10 at 21:35
It does not shock me really. What I meant was that even if they see a sketch of a proof they at least have some exposure to the process. –  hypercube Jun 5 '10 at 19:58