Writing a Combinatorial Proof

This started life as a post on Quora, answering the question:

For any positive integer n, how do you write a combinatorial proof of the identity

\displaystyle {2n \choose n} = \sum_{i = 0}^{n} {n \choose i} {n \choose n-i}?

To write a combinatorial proof, the idea is to describe how each side of the equation is actually counting the same set of objects.

Now, if you have a set of 2n objects, \displaystyle {2n \choose n} (that is 2n choose n) is the number of subsets of that set which contain exactly n of them.

Now pretend that you’ve taken your 2n objects and put them into two boxes with n objects in each. Think about what each of your terms on the other side of the equation, \displaystyle {n \choose i}{n \choose n-i} represent. Then consider what you get when you add all of these together. You should be able to explain that this really does count the same thing as \displaystyle {2n \choose n}.

Now when I wrote the above, I wondered if this was a homework question someone had posted to Quora.  I didn’t fill in all the details since, while I’m happy to help someone with their homework, I don’t want to do it for them.

But in case anyone wants to see a worked out example, here’s the standard initial example of a combinatorial proof.  This is the identity that makes Pascal’s Triangle work as nicely as it does.

Theorem: \displaystyle {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.

Proof: Let’s start by thinking about the expression on the left.  If we have a set with n objects in it, \displaystyle {n \choose k} is the number of ways we can select a subset of k objects.  To say that another way, it’s the number of ways we can pick k objects out of our set without caring what order they’re in.

Now suppose one of our objects has decided to wear a hat.  If we’re looking to select a subset with k objects, we can decide to include or exclude the one wearing the hat.

Say we don’t want to include the guy with the hat.  In that case, all k objects, have to be selected from the n-1 objects that aren’t wearing hats.  We can do this in \displaystyle {n-1 \choose k} different ways.

Now suppose we decide to include the one with the hat.  Well then, to get k objects altogether, we need to select k-1 more from the set.  There’s \displaystyle {n-1 \choose k-1} ways to get the rest of the objects that you need.

Putting these two together we see that \displaystyle {n-1 \choose k} + {n-1 \choose k-1} is also the number of ways to select a subset of k objects from a set containing n things.

Therefore, our identity must be true.

If you’d like to try one on your own, \displaystyle 2^n = \sum_{i = 0}^{n} {n \choose i} is another nice example.

Not Your Father’s Comic Book Box or Something Clever About Cardboard

First Published 28 January 2018

I got one of BCW’s new comic bins for my “Good Stuff.” Here’s a few impressions.

The bin is just slightly too tall for my shelves (designed for long boxes) and not quite wide enough for comics in mylar sleeves. Neither of those things was unexpected, but a pleasant surprise would have been nice. If BCW markets a magazine-sized bin, I’ll probably pick one up.

The bin wasn’t too hard to assemble, but the on-line video was little help; it was pretty vague and didn’t address the things that weren’t intuitively obvious. I would have preferred printed directions. I noticed there was a certain amount of static electricity present and that attracted dust. The next one gets assembled in the cat-free comic room.

The removable dividers are ideal for keeping your books upright even when the box is not-quite-full.

Once assembled, the bin feels sturdy and looks nice. A set of them would give you good storage that uses space efficiently. It’s not airtight, so I don’t think condensation is likely to be an issue.

A set would likely be cost-prohibitive for a large collection, but I think a few bins for high-end books would be a good investment.

 

The Credit Where it’s Due Department: Why no Byrne Variants?

A happy mail call today. I got my Alex Ross variants of the new Fantastic Four #1. These look great. Both honor one of the most iconic covers of all time; the first FF #1 from 1961. I’m not usually one to be enthused about variant covers, but I’m really happy to get these. It’s a fitting tribute to Lee and Kirby who created the team and set the standard for everything that came after that first book. It’s also nice to mark the occasion of the FF’s return to the Marvel Universe with something special. That’s a big deal to me and I think it’s a big deal to a lot of people.

But I seems to me that this variant nonsense has kind of gotten out of hand. There are literally something like forty different versions of this book. Many different artists, homages to many different eras. Lots of them look great. Many of them don’t. The anatomy in some of the artwork makes me cringe. They metaphorically raised Mike Weiringo from the dead so he could have his own variant.

Don’t get me wrong. Mike Weiringo deserves his own cover. More than almost anyone else whose artwork was featured. As I said, I’m not really one for variants, but I want one of those too.

But here’s the thing: in the last 57 years, there have been three really well regarded runs on the World’s Greatest Comic Magazine. The first was Lee/Kirby. The third was Waid/Weiringo. The second? John Byrne. Byrne took over FF after a long run of inconsistent creative teams; the quality had been uneven and interest in the book had waned. Byrne almost singlehandedly reinvigorated the title as writer, artist and inker and returned the FF to both popularity and importance.

So why isn’t there a John Byrne variant of the new FF #1? Did Byrne refuse? Is there bad blood between Byrne and Marvel? Is he just too hard to work with or was this an intentional slight? I for one would like to know. Eschewing a Byrne variant is a strange and indefensible oversight. It’s especially strange given that the same thing happened with Action Comics #1000. A Byrne variant there would seem to be a no-brainer, especially with Schuster and Swan unavailable. Byrne’s impact on Superman was significant. But once again in a sea of uneven variants, Byrne gets overlooked. I wonder if he’ll even be asked back when NextMen gets revived. I think Byrne and his fans deserve better.

How do you prove a conjecture is false?

First posted to Quora on Friday, 7 September 2018

That depends on the nature of the statement.

If you have a universal statement, which is to say a statement that all of the things in some category share some property, you merely have to provide a counter-example.

So if you wanted to disprove the statement, “all prime numbers are odd” you’d merely have to point out that 2 is even and the statement cannot be true.

Disproving an existential statement is usually more work. These statements say that there is at least one thing that has a particular property. To disprove an existential statement, you need a general argument that that property can never happen.

So to prove that the statement “There is a pair of even integers whose sum is odd” is false, you must prove that the sum of any two even integers must be even.

Those are the cases “all” and “some.” The cases “none” and “some are not” are similar.

To disprove a statement like “None of the items in set A have property B” you simply have to find one that does. If you want to show a statement like “Some of the items in set A do not have property B” is false you need a general argument that everything in A has property B.

In any case, disproving a statement is equivalent to proving its negation.

 

Renovating an Old Comic

This was first posted on 11 July 2018

——-

IMG_8899I just finished up a fun project that I thought I’d share.

I got a coverless copy of Avengers 23 from my LCS (thanks, Jared Aiosa) last month. I decided to renovate it, so I:
* Found a scan online and recreated the cover.
* Printed and trimmed it.
* Attached it to the book.
* Trimmed the book a tiny bit and flattened it under some dictionaries.
IMG_8904I’m pretty pleased with the results.  With a bit of practice, I bet I could get much better at this.

It’s pretty obvious that the result isn’t a mint condition book.  Not only is the interior clearly an older book that has a lot of wear, the cover is printed on standard 24 lb. bond paper and is not glossy, although you get some gloss from the ink.  The paper is also too white to have been attached to newsprint for nearly 50 years.

Despite all of that, he cover is clearly marked as being a replica, which I believe is an essential step for a project like this.

You can check out the finished project here.

Coming soon… how to videos.

Coming Attractions and “Old Guys Who Like Old Comics”

In the next few weeks, I’ll be finding some things I first posted in other places and adding them here.

One of the places I’ve been posting things is on the (closed) group Old Guys Who Like Old Comics on Facebook.

Nice people, nice group, well moderated.  It never descends into anarchy or trollery, even with 13,000 or so members.

“Old” is defined very broadly; it’s a state of mind.  Ditto with “guys,” everyone’s welcome. “Old Comics” on the other hand is closely monitored.  Nothing after 1986.  If you know comics, you know that’s a bright clear line.  Dark Knight, Watchmen… comics were never the same after 1986 for better AND for worse.

If you like comics and you’re on FB, it’s worth checking out.

Here We Go! Or, in the words of Adm. Stockdale, “Who am I? Why am I here?”

Hi, Everybody!

Holy crap, that sample introduction that WordPress gave us was a pretentious mess.  Luckily it’s gone including that picture of the sunset or whatever the hell that was.

I’m Joseph Kolacinski, a mathematics professor at Elmira College.  I’m interested in all sorts of nerdy things: mathematics, star trek, comic books, science fiction, vexillology, voting theory, politics, rock music.  Also cats.  I like cats.

IMG_3931What do you actually need to know about me?  Probably nothing.  Feel free to skip on to the posts that happen to interest you, whenever those start appearing.

I’m “Joseph” or “Dr. K.” as the students call me, to my face anyway.  If you call me “Joe” I’ll be immediately suspicious.  No one’s called me “Joe” since 1991, except for a few old friends who haven’t gotten the memo.

I own more comic books than any sane person should be allowed to have.  That’s what happens when part of your brain thinks that, if you possess objects labeled 1, 2, 3 and 5, you must, using any means necessary, seek out and possess the object labeled 4.  And that part of your brain can scream much louder than the rest of your brain.

I maintain, as I’ve stated in the past, that David Letterman is the greatest living American.  That whole thing with the affair was pretty disappointing though.

I’ve been thinking about starting a blog for a while now.  The original concept was called “Blogging the Marvel Universe.”  I would start in November 1961 and trace out the history of the MU, reading, reviewing and analyzing the comics as they came out.  I realized that would quickly start to feel like homework and I’d get bored.  But in the meantime, I’ve been writing reviews and publishing them on Facebook and more recently I’ve been answering things on Quora.  I’d like a single place to archive the stuff that’s worth preserving, and here we are.  But don’t kid yourself.  Far more than just the stuff that’s worth preserving.  You have been warned.

UPDATE: Already a fail on the not-feeling-like-homework thing as the original version of this post disappeared with an accidental click.  That was possibly the greatest piece of prose ever written in the language of Shakespeare.  Now you have this.  Sorry.