Skip to content

A counting problem, and a real problem with counting

December 28, 2020 pm31 2:10 pm

How many ways can we give eleven identical candies to four children? it is obviously possible (necessary) for some to get more than others, and there is not even a guarantee that each child gets something.

That’s equivalent to asking how many solutions there are to:

a + b + c + d = 11, a, b, c, d \in \mathbb{N} (including 0 in the natural numbers).

Now, you could give all eleven to the oldest, all eleven to the second oldest,… Or ten to the oldest and one to the second oldest, and ten to the oldest and one to the second youngest… This is going to be a long-ish list. In fact, I chose numbers just big enough that listing them would be an awkward exercise.

Solving the same problem, with smaller numbers, might help. Let’s give three candies to three kids: u + v + w = 3, u, v, w \in \mathbb{N}

Now we can make a list. I’m just writing numbers. 201 means two for the oldest, none of the middle, one for the youngest.

300, 210, 201, 120, 111, 102, 030, 021, 012, 003.

That’s ten ways.

But how do we scale this up?

One way, a common way, is to turn the numbers into a graphic. Lay the three candies out, and like the divider at the supermarket checkout, put in a physical barrier between the first kid’s loot and the second’s.  For 201 we can write ++//+. The pluses represent candies. So this is two candies for the first kid, then a divider, then another divider right away which means nothing for the middle kid, and one candy after the last divider for the littlest kid. If instead we were giving all three to the middle child, that would look like:  /+++/. Nothing for the oldest, all in the middle, nothing for the youngest.

Why are there three pluses? Three candies. Why are there only two dividers? There is one less divider than the number of kids.

So we can restate our problem as: How many arrangements are there of //+++?

Well, that’s a question with a well-known answer: \frac{5!}{3!2!} where 5! would be the arrangements of five things that are all different from each other, and 3! divides out the repetitions of +s and the 2! the repetition of /s.

A small, but important note: Any slash-plus pattern can be converted into kids and candies:  //++//++++++/+ would be 002061. And any candy-kid distribution can be converted into slashes and pluses: 222201 would be ++/++/++/++//+.

We might as well answer the original question. Eleven candies? four kids? That’s all the arrangements of eleven pluses and three slashes: +++++++++++/// which is \frac{14!}{11!3!} which is 364 ways.

– – — — —– ——– ————- ——————— ————- ——– —– — — – –

The April COVID-19 surge took John Horton Conway from us. Otherwise, he might have told us who created the Confederate monument that stands in combinatorics, that we need to take down.

Conway paid attention to credit. While on sabbatical in 2013 I took a Number Theory class with him. His historical tangents were fascinating. He not only knew who had come up with “if and only if” – but over a half century later, he was still a little jealous. And a little annoyed that his “unless and except unless” or some such, which he thought much more useful, never came into popular use. He kept track of politics, too. There was a story about a German mathematician with questionable choices of friends during the war… I often think that I should have ignored the number theory, and instead taken detailed notes on the mathematicians. The gossip-y stuff would have filled a paper, or maybe been the start of a book…

– – — — —– ——– ————- ——————— ————- ——– —– — — – –

My “pluses and slashes,” or “pluses and dividers,” I have been calling them that for a while. I privately chose not to use the more common name. John Horton Conway probably could have told me who came up with the common name – and whether they were being clever, or cute, or political.

In any case, *||**|*** for 1023 is conventionally referred to as “stars and bars” and if not an intentional Confederate monument is at least an unnecessary and unwelcome Confederate reference.

– – — — —– ——– ————- ——————— ————- ——– —– — — – –

I was talking to Sue Van Hattum yesterday, and she had not realized this, and was – rightly – horrified. She posted on Facebook. I told her I would blog about it. Which I am doing.

I checked my shelf. A dozen books on the topic, and only one reference I could find (they may be there, but unindexed). But on the web? All over the place. Lots of guides for secondary school mathematics. Texts in computer science and discrete mathematics. And some lecture notes by college professors.

bars and stars

– – — — —– ——– ————- ——————— ————- ——– —– — — – –

Where next?

  1. Get a new name
  2. Get rid of the old name

I admit that the old name “sounded” nice – it rhymed. And in comparison “pluses and slashes”? Meh. But I’ll take it. A better suggestion would be, well, better. Art of Problem Solving uses Balls and Urns (as well as the other), but that doesn’t really sound better. And it does not translate into this:  ++//++/+. I don’t see balls and urns. I see pluses and slashes. Sue suggested a relationship to 11001101, and there is a one to one correspondence, but the 0s aren’t really dividers, and I’d like to save them for something else.

And no need to wait for 1. before moving on 2. Do them both, simultaneously. Reach teachers, mathematicians, and eventually publishers? This should be easy.

 

5 Comments leave one →
  1. December 28, 2020 pm31 6:38 pm 6:38 pm

    If wikipedia is correct, the method is at at least old as 1915, when it was used to describe energy configurations. The name was popularized by William Feller in 1950. (See wikipedia on ‘stars and bars’.)

    Finding a good name is definitely step one. The better a name we find, the easier step two will be. A friend of mine has suggested pins and bins, which is bouncy enough, but doesn’t get the image quite right. She rejected bolts, but I thought nuts and bolts might be promising, it’s a tool, at least, as is the method.

    This feels like a fun bit of anti-racist activism to me. I think we can do this. (Getting authors and publishers on board does not sound easy to me, but definitely worthwhile and doable.)

  2. December 28, 2020 pm31 8:53 pm 8:53 pm

    JD
    I just stole this for my Number Facts page for 364th Day. As for “stars and bars”, lets keep it for the** l**|***|* and eliminate rebel battle flags. I love great notation and terminology and will not be put off by people who call Halmos’ stop a tombstone. I communicated with J H C for several years by internet while working in Japan and was forever altered by his knowledge of language and trivia

    • December 29, 2020 am31 2:53 am 2:53 am

      Pat,

      it was indeed Halmos who Conway expressed a little professional jealousy towards (iff). But I didn’t know the end of proof box was called a tombstone, and I certainly didn’t know that that was Halmos’ doing. I think I like that.

      Language is interesting. I am reading Graphs and Their Uses (Øystein Ore) with a small group of high school juniors and seniors. I paused before reading the jealous husbands problem – but it is a really nice problem. We can make a quick note of the assumptions about marriage and gender, and turn to the math.

      But I think this is different. The model – well the model is beautiful. But the name? Most books don’t include it. I use Ivan Niven’s Mathematics of Choice or How to Count without Counting (this is an elective for a larger group of high school students) –

      – interesting I guess that I’ve gone to old MAA books twice –

      and Niven doesn’t use stars and bars. I used to introduce it, anyhow, and I still do, but for the last few years I’ve just called it something else.

      But I’ve done so privately. This is the first time I’ve written or spoken about it with others. And whatever happens, I will continue to write ++//++/+ or **||**|* or something like that, but I’ll probably say sticks and stones or pluses and slashes.

      I do wonder what Conway would have said. He was fascinating, and quirky, and quick to connect one topic to another. I think he felt a connection between the math and the process that created it.

      • December 29, 2020 pm31 2:51 pm 2:51 pm

        I’ve always appreciated the moment when I reach matching theory in a graph theory class and I get to use the word “heteronormativity”.

        “Balls and urns” is a good description of the *problem* (in your case, the kids are the urns, the candies are the balls) but it doesn’t describe the *solution method* at all.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

<span>%d</span> bloggers like this: