A student asked me the other day the following rather homework-looking question: Given a natural number , how many solutions does the equation

have for and natural numbers?

The question has a very easy answer: Simply notice that and that any like this determines a unique such that is a solution. So, there are solutions if is even (as can be any of ), and there are solutions if is odd.

I didn’t tell the student what the answer is, but I asked what he had tried so far. Among what he showed me there was a piece of paper in which somebody else had scribbled

which caught my interest, and is the reason for this posting.

I don’t think the student had seen the connection between this product of two series, let’s call it , and his question. If we denote by the number of solutions to the equation, the series is the generating function of the sequence , i.e.,

To see this, notice that the coefficient of in is precisely the number of ways we can write as a product of a term from the first series and a term from the second one, i.e., it is the number of solutions with and natural numbers to the equation or, equivalently, . That is to say, the coefficient of in is exactly .

This gives us a purely algebraic (analytic?) way of solving the question, even if there is no understanding of how to approach it from a combinatorial point of view.

Both series on the product that makes up are geometric series, so we have

that of course coincides with the formula we obtained earlier by combinatorial considerations.

The question the student had is a very simple example of a problem about integer partitions, a beautiful area of mathematics that I hope I am not misconstruing by thinking of as a branch of combinatorial number theory. The technique of generating functions is a very useful and powerful combinatorial tool that I have always found quite nice although, granted, its use is a bit of an overkill for the question at hand. At the same time, this technique provides us with a (standard) method for solving any problem of the same kind: For fixed natural numbers , find for each the number of tuples of natural numbers such that

One can then go further to study the much subtler partition function and its relatives.

(And I still don’t know the name of the student, who didn’t bother to introduce himself, and I have no idea who suggested to him to look at to begin with.)

Well, I got the partial solution finally, here is the question that I tried to solve by the equation x + 2y = n, x,y,n > 0

Let n be a positive integer. Harry’s school year has n school days. Harry has budget of exactly $n for buying exactly one snack per day at school. There are only two types of snacks available: M&M for $1. 00 per packet, or a pair of bananas at $2.00 per pair. The following restrictions must apply to Harry.

(1) Harry must spend all $n on snacks during the school year.

(2) Harry does not have to buy a snack each school day.

At the end of the school year, Harry must report how many times he bought M&M, and how many times he bought bananas. How many different reports are possible?

Anyway, thank you for your posting 🙂 It helps me to understand the solution better.

As suggested by Gerald, the notion was first introduced for groups. Given a directed system of groups, their direct limit was defined as a quotient of their direct product (which was referred to as their "weak product"). The general notion is a clear generalization, although the original reference only deals with groups. As mentioned by Cameron Zwa […]

A database of number fields, by Jürgen Klüners and Gunter Malle. (Note this is not the same as the one mentioned in this answer.) The site also provides links to similar databases.

As the other answer indicates, the yes answer to your question is known as the De Bruijn-Erdős theorem. This holds regardless of the size of the graph. The De Bruijn–Erdős theorem is a particular instance of what in combinatorics we call a compactness argument or Rado's selection principle, and its truth can be seen as a consequence of the topological c […]

Every $P_c$ has the size of the reals. For instance, suppose $\sum_n a_n=c$ and start by writing $\mathbb N=A\cup B$ where $\sum_{n\in A}a_n$ converges absolutely (to $a$, say). This is possible because $a_n\to 0$: Let $m_0

Consider a subset $\Omega$ of $\mathbb R$ of size $\aleph_1$ and ordered in type $\omega_1$. (This uses the axiom of choice.) Let $\mathcal F$ be the $\sigma$-algebra generated by the initial segments of $\Omega$ under the well-ordering (so all sets in $\mathcal F$ are countable or co-countable), with the measure that assigns $0$ to the countable sets and $1 […]

Sure. A large class of examples comes from the partition calculus. A simple result of the kind I have in mind is the following: Any infinite graph contains either a copy of the complete graph on countably many vertices or of the independent graph on countably many vertices. However, if we want to find an uncountable complete or independent graph, it is not e […]

I think that, from a modern point of view, there is a misunderstanding in the position that you suggest in your question. Really, "set theory" should be understood as an umbrella term that covers a whole hierarchy of ZFC-related theories. Perhaps one of the most significant advances in foundations is the identification of the consistency strength h […]

I'll only discuss the first question. As pointed out by Asaf, the argument is not correct, but something interesting can be said anyway. There are a couple of issues. A key problem is with the idea of an "explicitly constructed" set. Indeed, for instance, there are explicitly constructed sets of reals that are uncountable and of size continuum […]

The question seems to be: Assume that there is a Vitali set $V$. Is there an explicit bijection between $V$ and $\mathbb R$? The answer is yes, by an application of the Cantor-Schröder-Bernstein theorem: there is an explicit injection from $\mathbb R$ into $\mathbb R/\mathbb Q$ (provably in ZF, this requires some thought, or see the answers to this question) […]

If a set $X$ is well-founded (essentially, if it contains no infinite $\in$-descending chains), then indeed $\emptyset$ belongs to its transitive closure, that is, either $X=\emptyset$ or $\emptyset\in\bigcup X$ or $\emptyset\in\bigcup\bigcup X$ or... However, this does not mean that there is some $n$ such that the result of iterating the union operation $n$ […]

I’m the student asked the question 😉

Well, I got the partial solution finally, here is the question that I tried to solve by the equation x + 2y = n, x,y,n > 0

Let n be a positive integer. Harry’s school year has n school days. Harry has budget of exactly $n for buying exactly one snack per day at school. There are only two types of snacks available: M&M for $1. 00 per packet, or a pair of bananas at $2.00 per pair. The following restrictions must apply to Harry.

(1) Harry must spend all $n on snacks during the school year.

(2) Harry does not have to buy a snack each school day.

At the end of the school year, Harry must report how many times he bought M&M, and how many times he bought bananas. How many different reports are possible?

Anyway, thank you for your posting 🙂 It helps me to understand the solution better.

Hi Eliot,

I’m glad this helped. Marion mentioned to me the `M&Ms problem’ the other day, I figured this was the same question without distractions.