# What's a replacement for "married couples" in combinatorics problems?

Many counting problems start with the assumption that we have a certain number of men and women or a certain number of couples, with the assumption (often unstated) being that that gender is binary (only men or women) and couples are only heterosexual. (See for example this or this problem or think for example of Hall's Marriage Lemma.) Can anyone suggest a good replacement for the concept of couples in these sorts of math problems that better reflects the societal norms of the latest generation of students?

As an example, I'll routinely replace "men and women" with "undergrads" and "grad students" or something similar depending on the class make up. I'm currently racking my brain for two distinct sets of objects S1 and S2, where we might naturally think of pairing objects in S1 to objects in S2, and where there is one most natural pairing (i.e. replacing men and women, where we compare any heterogeneous couple to pairing men and their wives). Anything I've thought of makes for a ridiculously long word problem. Any suggestions appreciated.

What's a replacement for "married couples" in combinatorics problems?

Please, do not provided answers that say there is no need to do so. This is beyond the scope of this question.

• Comments are not for extended discussion; this conversation has been moved to chat.
– quid
Mar 8, 2018 at 17:59
• I removed all comments. I first tried to preserve some, but which one's I'd select to stay would likely create more controversy. Whoever is interested in the discussion can visit the room linked to above.
– quid
Mar 8, 2018 at 18:05
• Customer vs. product? Mar 8, 2018 at 23:08
• I removed a re-post of a comment that was moved to chat. I have nothing against the comment itself (indeed it had made the shortlist of those I considered leaving around), but if I allow one repost, I'll have to allow the next too, and I am sure y'all can see where this would be going. Please do not repost comments. (Otherwise I'll lock the comment thread.)
– quid
Mar 9, 2018 at 9:19

I've been using "pets" and "owners" (as in: possible pet-shelter adoptees) in recent years.

• I like this one. The sets are disjoint and the objects are still clearly distinct. (I suppose one has to specify owners have one pet, but that's not so bad.) I'll wait to accept an answer for a bit because I think it's nice to have several options, but thanks! Mar 2, 2018 at 23:43
• But the relationship is clearly inverted when you compare dogs and cats... Mar 3, 2018 at 23:47
• @Mathprof, a variant on this which clearly forces pairing would be horses and riders. Mar 4, 2018 at 20:55
• This a great political solution, although the number of owners with multiple pets is probably higher than the number of gay marriages right now, so technically this is MORE ambiguous. Mar 6, 2018 at 17:17
• our class used "wands" and "wizards". The wizard prefers certain wands, and, as we know, "the wand chooses the wizard"!
– bob
Mar 11, 2018 at 22:40

In the stable marriage problem, you can introduce the problem as it is. But then you ask your students how things change if you assume there are not only heterosexual but also gay and lesbian people (assuming that a heterosexual person will never marry a person of the same gender, and a gay or lesbian person will never marry a person of the opposite gender). It's actually an interesting problem that requires a completely different solution.

Add bisexual people, and your student's heads will explode - hopefully not because of the bisexuality, but because suddenly the problem gets a lot lot harder. On the positive side, people being transgender doesn't affect the problem at all.

• +1 for the inclusive answer that allows us to keep posing the same problems when needed to teach combinatorics.
– Pere
Mar 3, 2018 at 19:09
• You really propose to open this can of worms in a math class? Mar 5, 2018 at 22:19
• @RobertHarvey, it's a math problem. And actually an extremely interesting one. I dare you to solve it. (This has nothing to do with your social views at all, just standard graph theory and combinatorics.) Mar 6, 2018 at 2:42
• @RobertHarvey Unless your students are denying that homosexual relationships actually exist at all, I don't see the problem. Maths isn't about setting social rules. It's hardly the professor's fault that they exist. Mar 8, 2018 at 22:13
• @immibis: There are many, many other examples to choose from that are far less controversial. The only reason I can think of to choose this particular one would be to make a political point. Respectfully, I don't think that aligns with the primary purpose of a math class. Mar 8, 2018 at 22:26

A few possibilities off the top of my head:

• Students and chairs. How many ways are there for $n$ students to sit in $k$ chairs. The game of musical chairs might be fun to play around with. One can also consider natural restrictions, such as myopic students who need to sit near the front.
• Replace "men" and "women" with faculty from different departments. For example, you might need a curriculum committee made up of mathematicians and physicists.
• In the senate, there are two senators from each state. How many ways are there of making a committee of 6 senators, no two of which are from the same state? This really only works in the US, but I am sure that there are similar phrasings that could work elsewhere. One could also consider party affiliation here, which could lead to more interesting problems.
• True story: My daughter, who is in kindergarten, has a 5th grade "reading buddy." If there are $n$ kindergarteners and $k$ 5th graders, how many ways are their of pairing up students? If you want to appeal to an older audience, maybe we are pairing up tutors with students for individual instruction?
• This is totally not what you want, but still an interesting problem: how many injective functions exist from a set with $n$ elements to a set with $k$ elements? How about surjective functions? How does this change with $n$ and $k$?
• This question on MSE uses 9th and 10th graders. "Juniors" and "Seniors" could easily replace these if you wanted a college aged example.
• +1 I like the students and chairs example. For variety, could also be cars and parking spots. Or ships and berths. Or trucks and loading docks. Or members of a sports team and numbered jerseys. Mar 5, 2018 at 14:32
• @DanChristensen Oh! I like sportsball players and jerseys! That is actually something kind of fun there, too, since teams often retire the numbers of famous players, which means that entirely arbitrary restrictions can be justified (for equally arbitrary reasons). Mar 5, 2018 at 14:42
• I've seen the students and chairs one in the wild and it's been quite easy to understand. Mar 6, 2018 at 11:59
• And at the lower levels, you can put a bunch of chairs in the front of the room and have students come and sit in them, and demonstrate the problem in the classroom. At least until everything goes online. Mar 6, 2018 at 17:12
• @DanChristensen As stable marriages have been discussed, I wouldn't understand a situation where chairs have preference over students to sit on them.
– JiK
Mar 9, 2018 at 10:31

The issue is not making problems about heterosexual married couples. The issues are:

• Implicitly making the assumption that all married couples are heterosexual.
• Making problems about heterosexual marriages but not about other kinds of couples.

Both points are unengaging for people following other types of marriage, but they can easily be solved while keeping the problem clear and interesting. We just need to make all assumptions explicit (thus acknowledging that they aren't universal while making the statement unambiguous) and making a wider array of problems (which can be useful to teach different tools).

## An example

There are 100 single people in a village. How many different marriages can be performed among them in the following situations? Please beware that situations depicted are just simplifications to keep this problem easy and solvable.

### 2018 situation

All people are free to marry any other villager of their choice.

### 1990 situation

There are 55 men an 45 women in the village. A valid marriage must include a man and a woman.

### 1940 situation (somewhere)

There are 30 white men, 28 white women, 21 black men and 21 black women in the village. Local laws only allow a person to marry another person of the same race and different sex.

### Yanomamo kinship system

There are two clans in the village: clan A (30 men, 28 women) and clan B (21 men and 21 women). People are only allowed to marry somebody of different sex and different clan.

### Caste system

There are four castes in the village: caste A (15 men, 15 women), caste B (15 men, 13 women), caste C (10 men, 11 women) and caste D (11 men, 10 women), being A the highest caste and D the lowest caste. A man is allowed to marry a woman of his caste or any lower caste, while a woman is allowed to marry a man of her caste or any higher caste.

### Arthur C. Clarke's Rendezvous with Rama system

There are 100 people in the village. Any arbitrary group of people of any size can form a marriage if all they agree.

## End note

Please notice that the examples don't endorse any marriage system, and make explicit all assumptions. For example, the 1940 system problem with explicit assumptions is just historical, but the same problem with implicit assumptions would be plainly racist.

• Definitely a more interesting and fun exercise in your proposed cases. Mar 5, 2018 at 20:49
• I like this answer very much. It is not the problem itself, it is making the implicit assumption that of course every couple is heterosexual. In mathematics, we often make simplified assumptions - even more in natural sciences (point-like masses, no friction etc.) - that make a problem more accessible. There is nothing inherently bad about this. Just state that it is part of the assumption, and everything is fine. Mar 6, 2018 at 8:43
• “Both points are unengaging for people following other types of marriage” What? Does that mean I (not a pet owner) should not find "engaging" a problem that talks about pets? This doesn't make sense. Analogies in math problems are there to state a problem to solve, not to "engage" people. Mar 6, 2018 at 17:18
• @AndreaLazzarotto Motivation and engagement is an important point of any exercise - in fact, of any learning activity. Relating statements to elements interesting for the learner improves motivation. For example, we teach children to count by counting sweets and pets, not by counting bolts and nuts, or bricks and beams, although both analogies can state the same problem.
– Pere
Mar 6, 2018 at 18:18
• It is still painful to people of color, who continue to be discriminated against, to introduce problems like the 1940 version, just for the sake of the math. I advise against problems like that and the caste one. Mar 8, 2018 at 0:37

Try objects that often occur in pairs but are distinct from each other: forks and spoons (or forks and knives), left and right shoes, salt and pepper shakers, and so on (where each fork has an obvious partner spoon, perhaps sharing the same color or design, and so on).

When I taught a class about the stable marriage problem last week, I replaced "men" and "women" with "medical students" and "hospitals": the classical instance in which the Gale-Shapley algorithm is used in real life.

In addition to the gender issues already mentioned, this has the benefits that:

• We avoid envisioning a dystopian future where everyone's preferences are fed into a computer and the computer tells everyone who they should marry. That's just kind of weird.
• The very similar-looking "men propose" and "women propose" versions of the algorithm now get very different flavor text to distinguish them. In one version, medical students all travel to their next top hospital, and each hospital tells all but one of the visiting students to go home, game-show style. In the other version, hospitals send offers to their favorite student, and each student rejects all but one offer, provisionally accepting the best.

I also took this opportunity to give the participants of my examples the names of characters and hospitals from "House" and "Scrubs". This amused me but appears to have flown over the heads of today's undergrads. Kids these days.

• That’s great! I couldn’t think of a non-gendered version where each of the two groups have preferences for choosing members of the other group, as in the stable marriage problem. This fits the bill perfectly. Mar 6, 2018 at 4:32
• I'm okay with the fact that no one got my Spice Girls reference last week, but if they don't get Scrubs and House, we are all doomed! Mar 6, 2018 at 14:41
• This answer is good. The original problem of pairing couples is somehow artificial anyway. The context of matching in employment or admissions is not as it's done widely in practice. Dec 28, 2021 at 10:34
1. Protons and electrons (form hydrogen atoms)

• Or cations and anions (form salts), e.g. Na+ and Cl-
2. Pens and pen-caps

• Bottles and bottle caps, etc.
3. Textbooks (for the course being taught) and students

4. Light bulbs and light sockets

5. Power cords and electrical outlet sockets

6. Cars and parking spaces

7. Seats and attendees, e.g. students in the classroom and classroom seats

8. Mimes and invisible boxes

9. Numerators and denominators

10. Boxes of cereal and toys-that-go-at-the-bottom-of-boxes-of-cereal

I'm currently racking my brain for two distinct sets of objects S1 and S2, where we might naturally think of pairing objects in S1 to objects in S2, and where there is one most natural pairing

Just for fun, $\TeX$'d up a table:

$${\begin{array}{c|c|c|c} & \textbf{S}_\textbf{1} & \textbf{S}_\textbf{2} & \textbf{Natural Pairing} \\ \hline \small{1} & \text{proton} & \text{electron} & \text{Hydrogen} \\ \hline \small{2} & \text{anion} & \text{cation} & \text{salt} \\ \hline \small{3} & \text{pen} & \text{pen cap} & \text{capped pen} \\ \hline \small{4} & \text{bottle} & \text{bottle cap} & \text{capped bottle} \\ \hline \small{5} & \text{student} & \text{textbook} & \text{prepared student} \\ \hline \small{6} & \text{student} & \text{seat} & \text{seated student} \\ \hline \small{7} & \text{power cord} & \text{power outlet} & \text{plugged-in cord} \\ \hline \small{8} & \text{light bulb} & \text{light socket} & \text{light} \\ \hline \small{9} & \text{car} & \text{parking spot} & \text{parked car} \\ \hline \small{10} & \text{mime} & \text{invisible box} & \text{boxed mime} \\ \hline \small{11} & \text{screw} & \text{screw hole} & \text{inserted screw} \\ \hline \small{12} & \text{left glove} & \text{right glove} & \text{gloves} \\ \hline \small{13} & \text{numerator} & \text{denominator} & \text{fraction} \\ \hline \small{14} & \text{Na}^{+} & \text{Cl}^{-} & \text{NaCl} \\ \hline \small{15} & \text{thing} & \text{name} & \text{named thing} \\ \hline \small{16} & x & y & \left(x,~y\right) \\ \hline \small{17} & \text{longitude} & \text{latitude} & \begin{array}{c} \text{possible site of} \\ \text{buried treasure} \end{array} \end{array}}_{\huge{.}}$$

• Well, to nitpick: fundamental particles like protons and electrons are indistinguishable, so if you ask "How many distinct Hydrogen atoms can be made by pairing from a group of 6 protons and 8 electrons?" the answer might be 1. :D Mar 6, 2018 at 10:34
• @NUnnikrishnan Hah just tell the student that even fundamental particles are distinguishable by their other properties, e.g. location. This is one problem where the implicit sub-typing of objects is important!
– Nat
Mar 7, 2018 at 0:38
• I'm a chemist. I agree with N. U. and would avoid this type of example. teaching wrong thing and bringing a confusion in, if particles are indistinguishable. Mar 7, 2018 at 4:28
• @guest Naw, there's nothing wrong about it; pretty sure that they were just cracking a joke by subtly misapplying the concept of indistinguishability.
– Nat
Mar 7, 2018 at 5:01
• Further to car//parking spot, any vehicle generally and its storage location: aircraft and gates on the ramp, boats and piers, trucks and loading docks, cars and fuel pumps/charging ports, etc.
– Nij
Mar 9, 2018 at 4:35

An idea I find interesting is to use abstract objects: "given X squares and Y circles, in how many ways it's possible to pair one circle with one square?"

If the students are at kindergarten or primary school level, maybe you can give the children squares and circles made with paper, plastic or wood, each with a different color, so they can try these combinations with the objects:

Personally I find this way easier and less distracting than using real life examples. Of course in some exercises you will want the student to be able to examine a real life situation and transform it in a mathematical problem, so in this case abstract objects will not work so well (and there are many good answers with interesting suggestions on meaningful pairings), but when you want to focus only on the mathematics involved, this can be useful.

However, I recommend you to avoid using topics which attract controversial and hot discussions (as gender/sexuality issues) as examples in a math class, as some answers suggested. Firstly, these kind of topics can be confusing to most small children and very distracting for older students, who possibly already have political opinions. I would be very distracted if I feel that the teacher is trying to punch "these damned X" inside a math problem - specially if I am one of these "X"! Also bringing a political topic can even reduce the ability of properly solve mathematical problems! Besides that, parents with a different political leaning may not like to see a teacher injecting political topics on non-political subjects, and if the example implicitly supposes a side is the correct one, this only makes things worse. These parents can cause a problem to you, as trying to process you or the school you teach, for example (if they would be right or wrong on doing that is another question, but I think you want to avoid problems). Basically, just be sure that your replacement is socially acceptable - not only to you, but to other people too!

I like several of the answers which found clever sets that avoid assumptions about genders and sexes. Just to provide an alternative, what about keeping the assumption about sexes, but changing species and turning it into a free biology lesson as well. Many birds mate for life, such as bald eagles.

It would also open up the door for some other interesting math problems. Emperor Penguins are serial monogomists. They pick a mate and stay with them for a whole year, but rarely pick the same mate year after year (15%), so you could put together some interesting combination problems with that! They also have the neat fact that the male takes care of the egg, balancing on his feet as the males huddle in brutal cold winds. The females return later, when the eggs are hatching. This gives the penguin chicks a head start over other creatures which weren't able to manage this brutal feet. Mind you that might not help the math any, but I think it's freaking awesome.

You might also be able to play some really interesting combinatorics with bees. Bees have fascinating caste systems, especially regarding how new queens are dealt with. (The queen has to make sure nobody usurups her, but if the queen dies for any reason, the hive needs to vote a new queen into office by feeding her royal jelly).

There's also the "other" sex systems. We are used to XX/XY, because that's what humans have. Many of the arguments regarding not accepting the other genders or sexuality stem around the universality of this system. Well it's not the only one out there. Bees use X0/XX. Many lizards us ZZ/ZW. A quick biology lesson might start minds turning. Evolution has had several goes at this concept. While they, themselves, are not going to be straightforward substitutions into combinations problems, they are a fascinating chance to learn something other than math in math class.

• Except that even mate-for-life birds get a lot of action on the side. DNA studies have proved this. Mar 5, 2018 at 20:50
• @CarlWitthoft Which is not really all that different from marriage of humans (I don't think I need DNA studies to prove this =) ) Apparently for Emperor penguins the infidelity rate is 15%. Mar 5, 2018 at 21:04
• Interestingly though, I'd stay away from the penguin one. I think people have found penguins can be gay, so it's not as perfect as it seems. Mar 6, 2018 at 17:29
• @Feathercrown The point isn't to be accurate, the point is to be inoffensive. People who object to heteronormative pairings with humans tend not to do so when talking about the mating of animals, so the solution still works. Mar 8, 2018 at 0:11
• It might be more than penguins that 1. mate for life, and yet 2. can form same-sex pair-bonds. For a children's story that comes from a real-life incident, check out And Tango Makes Three. Mar 8, 2018 at 0:44

I'm just thinking out loud here, but one possible option is to keep it as men and women, but have it be about ballroom dancing, or figure skating, instead of dating or marriage.

That way, it might have fewer undertones of "everybody in the world needs to be married off to someone of the opposite sex", and might have more connotations of "this is a specialized hobby where we want to pair men with women for aesthetic reasons, but we're not claiming that the world as a whole needs to be this way."

Such examples could begin with "In a ballroom dancing club, there are 12 women and 10 men..." That wording, at least ideally, leaves open the possibility that the larger world could have nonbinary people. It's more like "this particular club has 12 women and 10 men."

• I don't think that this answers the question. The difficulty is that gendered language is a problem in the first place, in that it implicitly ignores the existence of gay folk, trans folk, ace folk, and so on. The goal is to come up with problem statements that don't exclude people. Mar 3, 2018 at 4:26
• @XanderHenderson: What's the problem with a gay guy doing figure skating with a transwoman? How does this answr exclude anyone? Mar 3, 2018 at 14:43
• @EricDuminil Assuming good faith, consider this problem: "We have 4 black people and 6 white people. How many ways can we sort them into married couples such that no black person marries a white person?" You would never use this example, and it is somewhat nightmarish to even think about presenting it. The reason is that it is exclusionary in a way that shows a lack of understanding about current society. If I changed it to "How many ways can you create pairs of penpals such that no white person writes to a black person," I would have missed the point: why exclude actions based on race at all? Mar 3, 2018 at 15:49
• @ChrisCunningham: My question was a genuine one. I understand the problem in wanting to only marry men and women together. I don't see any problem in asking men and women (who both could be trans- or cis-) to skate together. Also, your point with black and white people isn't a good example IMHO. Allowing only black or white couples would be the same thing as forcing people to marry the same gender. Anyway, the "students and chairs" is a much better, less controversial, example. Mar 3, 2018 at 16:56
• @idmercer Why must Magic Johnson be played by a black actor and Larry Bird by a white actor? Have we learned nothing from Hamilton? Mar 4, 2018 at 2:40

Nuts and bolts? You'll need to specify bolts which are only long enough to accept one nut each, but that's brief enough to do.

Simply state that the question is purely in the context of purely heterosexual couples right out of the gate, then make reference to homosexual couples who are also pairing off but are not included in the context of the problem, using the exact same language to refer to both groups but specifying that the question only refers to the heterosexual group.

This approach has the advantage of maintaining the original content of the problem, while re framing the context slightly to be more inclusive.

And you should maintain the classical problem as it is constructed because classical problems, rather in logic or computing or math are useful intuitive tools that are commonly understood across time and culture. Changing the problem to be more culturally relatable to American students because they have a different definition of marriage might well force you to use an example that is less relatable for students from Middle Eastern/African/Asian countries who have different definitions of marriage and might have encountered the problem as it was classically constructed.

The overwhelming majority of people across time and culture understand/understood the concept of heterosexual monogamous pair bonding (in that they acknowledge it's existence) even if they have/had differing attitudes towards homosexual monogamous pair bonding and monogamy in general. If you try to find an alternative way of framing the problem, you run the risk of using a far less relatable example. Others have suggested using an example from biology; what if students are ignorant of that? How about pop culture references...well what if a student is from somewhere where they didn't have that thing you are referencing?

This is why I argue it is better to append appropriate context to the original problem to make it more inclusive, rather than changing it radically in a way that completely removes the concept of heterosexual pair bonding in humans. By doing that you are making more of an effort to connect your teaching with people from other times and cultures who think differently from you but nonetheless sought to use the same problem to teach the same concept. And you can do that while also making the problem more inclusive in your specific classroom.

• I think this is a good answer in that it challenges the assumptions of the question while still making a good-faith effort to answer the question. Mar 6, 2018 at 16:39

Cut out the middle man and make it about sexual reproduction.

You need precisely one sperm to meet one egg.

Any other combination would be unviable either due to the inability for one sperm to affect multiple eggs or due to multiple sperm affecting a single egg (i.e. polyspermy) creating an unviable zygote.

• Except that is incorrect. first of all, rare cases of viable embryos with two sperms entering the egg happen. Second, a single sperm cannot achieve penetration without the help of a lot of pals banging (sorry) away at the egg's surface. Mar 5, 2018 at 20:51
• @CarlWitthoft Would the students know or care though? Mar 5, 2018 at 23:45
• Teenagers+Sexual topics = jokes and stuff tho = inattentiveness Mar 6, 2018 at 17:35
• @Feathercrown What age are we talking? Where I'm from we weren't taught combinatorics even at age 16. Mar 7, 2018 at 1:15
• @Pharap I was assuming early college, so 17, but I don't think they specified.... :/ Mar 8, 2018 at 5:44

Use terms from literature, TV, movies, theater, and pop and folk culture in general. With a large variety of pairings to choose from, questions can be adapted for a local culture without much difficulty.

e.g.

• Klingons and Romulans
• Montagues and Capulets
• Sharks and Jets
• Hatfields and McCoys
• Jews and Greeks (cf. Gal. 3:28)
• Commies and Alt-Rights
• Sailors and Landlubbers

Using some of these can also make your examples/questions fun! Come up with some weird satirical scenario and make the example stick in peoples' brains. Forsooth, come up with a problem involving matching Montagues and Capulets and mix in Shakespeare-sounding language. Or, pick Sailors and Landlubbers, matey, and be includin some of that stereotypical pirate lingo, arr.

• I know where this is going. Forsooth, pair Montagues with Pirates, me mateys! Mar 6, 2018 at 18:09

Horses and jockeys.

You can also consider problems with not just 1:1 pairings. 5 person basketball teams, etc.

It occurred to me in thinking about the ménage problem that one could reformulate it as a story about students and advisors attending an awards dinner, with the requirement that advisors and students sit alternately, with no student sitting next to their own advisor. One must stipulate that no student has multiple advisors attending the dinner and that no advisor has multiple students attending the dinner.

Agents and missions are a good choice for maximum pairing problems for bipartite graphs. Edge linking agent to a mission means that agent can carry out the mission, so there are no edges linking mission to mission or agent to agent. Agent can't do another agent, or we have an entirely different problem :)