Name the members! What are the odds of getting at least one right? (an actually interesting math problem for stan Twitter)

This game has circulated K-Pop stan Twitter:

EDZT3eAU4AMqWAL.png

I’ve never actually attempted it myself, as I know that 99.999999% of the time I will screw this up. Badly. However, I’ve seen some pretty amusing results and heard some pretty funny stories about it.

Sometimes, people would play this game by getting a list of member names first to match them to their faces. This ostensibly increases their odds of getting everyone’s names right from practically zero to merely something undetectable by 10-digit calculators, and perhaps gives them something of a fighting chance of getting at least one. Anyway, let’s try this variant of this game, as described in a puzzle I posed to my followers:

It was pretty close, but a plurality said that the odds of getting at least one correct get better as the number of members gets larger. Let’s see how correct this is.

(Before we proceed, of course I’m making the following assumptions: we play fairly, i.e. we assign distinct names to every member.)

 

A Preliminary Approach

Let’s start by looking at small cases.

Say you have only one member. This isn’t particularly interesting, because there’s literally no way you can mess this up. This case also pretty much never pops up, so we can safely ignore it.

Now suppose we’re talking two members. Still not particularly interesting–there are only two possibilities. Either you get them both right, or you get them both wrong. So the odds are now 50%.

If we stop here, then our conclusion is that the odds are worse the more members you have.

Let’s move on to three members, the first actually “interesting” case here.

For convenience, let’s say that the members are 1, 2, and 3. Then we can think of each assignment of “names” as an arrangement of the three numbers: the first number is the “name” we assign to Member 1, the second number is the name assigned to Member 2, and the third member is the name assigned to Member 3. A number in the correct place is a member correctly named. Basically, getting them all right would be the arrangement 1 2 3.

There aren’t too many possible arrangements. In fact, there are exactly 6, and it’s not hard to list them all (red numbers denote numbers in their places):

1 2 3 ✔️
1 3 2 ✔️
2 1 3 ✔️
2 3 1
3 1 2
3 2 1 ✔️

Thus, the odds of getting at least one member are \dfrac{4}{6} \approx 67\%.

In a similar vein, we can attack the case of four members. The list is a bit longer, but still manageable:

1 2 3 4 ✔️    2 1 3 4 ✔️     3 1 2 4 ✔️     4 1 2 3
1 2 4 3 ✔️    2 1 4 3          3 1 4 2           4 1 3 2 ✔️
1 3 2 4 ✔️    2 3 1 4 ✔️     3 2 1 4 ✔️     4 2 1 3 ✔️
1 3 4 2 ✔️    2 3 4 1          3 2 4 1 ✔️      4 2 3 1 ✔️
1 4 2 3 ✔️    2 4 1 3          3 4 1 2           4 3 1 2
1 4 3 2 ✔️    2 4 3 1 ✔️     3 4 2 1           4 3 2 1

This gives us odds of \dfrac{15}{24} \approx 63\%.

Listing all arrangements isn’t exactly the best way to study this though. The reason is that the number of arrangements grows extremely rapidly as the number of members does. For five members, we have 120 arrangements; for seven members, we have 5,040 arrangements; for the 21-member NCT, there are more than 51 quintillion arrangements (51,090,942,171,709,440,000 to be exact)!

We thus need to attack this more systematically. In the succeeding sections, we will cover some basic counting concepts, then apply them to this problem.

 

Factorials

Again and again, we will be considering products of the form n \times (n - 1) \times \dots \times 3 \times 2 \times 1 where n is a positive integer. We denote this product by n!. Before you break your roommate’s ear yelling out numbers, know that this is actually read as “n factorial.” For example, 3! = 3 \times 2 \times 1 = 6; 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120, and 21! = 51,090,942,171,709,440,000. As a matter of convention, it is useful to define 0! = 1. We will see why in a bit.

In fact, the number of possibilities for n members is exactly n!. To see why this is so, let’s look at the case for three members. For member 1, there are exactly three possible names you can give them. Then for member 2, since one of the names has been assigned to member 1, there are exactly two more names. Finally, for member 3, there is exactly one name remaining.

Thus the total number of possibilities we have for three members is 3 \times 2 \times 1 = 3! = 6. More generally, if you have n members, then there are n possible names for the first member, n - 1 possible names for the second member, and so on and so forth until you have to assign the last name to the last member, and the total number of possibilities is n \times (n - 1) \times \dots \times 1 which is exactly how we defined n!.

 

Permutations and Combinations

A permutation of k distinct objects out of n distinct ones is an ordered selection of k objects out of n, where k \le n. We denote by P(n, k) the number of permutations of k objects out of n. For example, suppose we want P(n, n). That is, we choose all n objects, and order them. Basically, we are just counting the number of ways to arrange n objects. Thus, from the above, P(n, n) = n!.

For another example, we want P(3, 2). We have exactly six such permutations: 1 2, 1 3, 2 1, 2 3, 3 1, and 3 2. There is another way to arrive at that answer without listing everything down. First, we count the number of possible choices for our first number. There are three. Then, for each choice of the first number the number of choices for the second number is two, and so we have 3 \times 2 = 6 permutations, as desired.

More generally, suppose we want permutations of k objects out of n. For the first object, there are n possibilities. For the second, since we already chose one object, there are n - 1 possibilities left. For the third, as we have chosen two objects, there are n - 2 possibilities. And so on and so forth. Until we get to the kth object, where, since we have chosen k - 1 objects, we have n - (k - 1) = n - k + 1 possibilities. Thus,

P(n, k) = n \times (n - 1) \times (n - 2) \times \dots \times (n - k + 1).

In fact, we can rewrite this formula in terms of factorials. This is the product of all numbers from n to n - k + 1. However, we can think of this as the product of all numbers from n to 1, but we remove everything from n - k to 1. Thus, we have

\displaystyle P(n, k) = \frac{n!}{(n-k)!}.

(This is why we use 0! = 1.)

Combinations are like permutations, except that this time, order does not matter. We denote the number of combinations of k objects out of n by C(n,k).

For example, if we want \displaystyle C(3,2), we want to choose two out of 1, 2, 3. We choose 1 and 2, 1 and 3, or 2 and 3. (Note that choosing 2 and 1 is the same as choosing 1 and 2.) Thus \displaystyle C(3,2) = 3.

Let’s find a more general pattern given n and k. From the above, counting the number of permutations of k objects out of n, we have \displaystyle P(n, k) = \frac{n!}{(n-k)!}. However, for each combination of k objects, we have k! different arrangements, and thus there are k! different permutations corresponding to any such combination. Thus, we have

\begin{aligned}[t] C(n,k) &= \frac{P(n,k)}{k!} \\ &= \frac{1}{k!} \times \frac{n!}{(n-k)!} \\ &= \frac{n!}{k! \times (n-k)!} \end{aligned}

 

The Principle of Inclusion And Exclusion

Suppose we want to count the number of items in a bunch of sets. Say we have two fandoms, A and B, and we want to count how many people are in at least one of the two fandoms. First, we count the number in A, then we count the number in B. Then we add them. Unfortunately, this approach gives us too many, because some people are in both fandoms and get counted twice. To compensate, we subtract the number of people in both fandoms. Now everyone is counted exactly once, and we are happy.

Let’s try this for the case of three fandoms. Let’s add C as a third fandom. So if we naively add the number of those in A, those in B, and those in C, we’ve counted the number of people in A and B, B and C, or C and A twice, and in fact we’ve counted the number of people in all three fandoms thrice! To compensate, we subtract the number of people in A and B, B and C, and C and A.

However, when we do this, we subtract the number of people in all three fandoms thrice. Since we added them thrice earlier, they are no longer accounted for. To finish off, we have to add this number back.

In general, if we want to count the total number of distinct elements of a union of sets, we first count the number in one of the sets, then we subtract the number in two of the sets, then add back the number in three of the sets, and so(w)on and so forth.

This formula is called the principle of inclusion and exclusion.

Let’s now try and apply this to our original problem. For the case of four members, we counted exactly 15 arrangements with at least one correctly placed number. Let’s see if we can get this number without listing everything.

First, we count the number of arrangements with one correctly placed number. If 1 is placed correctly, then we can place 2, 3, 4 wherever we want. This gives us 3! = 6 arrangements where 1 is placed correctly. Similarly, we have 6 arrangements where 2 is placed correctly, 6 arrangements where 3 is placed correctly, and 6 arrangements where 4 is placed correctly.

Of course, if we naively add these together, we get 6 \times 4 = 24 arrangements with at least one correctly placed number, which doesn’t make any sense at all.

The problem is that we’ve counted some arrangements more than once. For example, when we counted the arrangements with 1 placed correctly, we also counted some arrangements where 2 was placed correctly as well; these arrangements then got double-counted when we counted the number of arrangements with two placed correctly.

To compensate, we count the number of arrangements with two correctly placed numbers. For example, if we place 1 and 2 correctly, we have to place 3 and 4, and there are exactly 2! = 2 ways to do this. Similar count for 1 and 3, 1 and 4, 2 and 3, 2 and 4, 3 and 4. Thus we subtract 2 \times 6 = 12 from our answer.

This leaves us with an undercount now, though, for similar reasons. The arrangements where three numbers were placed correctly were subtracted too many times, so now we have to add them back in. We have exactly one arrangement where 1, 2, and 3 are placed correctly. Similarly, we have one arrangement where 1, 2, and 4 are placed correctly; one where 1, 3, and 4 are placed correctly; one where 2, 3, and 4 are placed correctly. We thus add 4 to our answer.

And again, to compensate for the overcounting, we have to subtract the arrangement where all four are placed correctly, namely 1 2 3 4. Thus, finally we subtract 1, and our answer is 24 - 12 + 4 - 1 = 15, as we wanted.

Let’s tackle this generally. Suppose you want to count the number of arrangements of n numbers with at least k of them placed correctly. First, we choose which k of them to place correctly. There are C(n,k) ways to do this. Then, for the remaining n - k objects, there are (n - k)! ways to arrange them. Hence, there are \displaystyle C(n,k)\times(n-k)! such arrangements.

Thus, by applying the same reasoning as in the preceding example, the number of arrangements of n numbers with at least one number placed correctly, which we shall denote by A(n), is given by the formula

\begin{aligned}[t] A(n) &= \displaystyle C(n,1)\times(n-1)! - C(n,2)\times(n-2)! + C(n,3)\times(n-3)! - \dots + (-1)^{n-1} \times C(n,n) \times (n-n)! \\ &= \frac{n!}{1!\times(n-1)!}(n-1)! - \frac{n!}{2!\times(n-2)!}(n-2)! + \frac{n!}{3!\times(n-3)!}\times(n-3)! - \dots + (-1)^{n-1}\times\frac{n!}{n!\times 0!}\times 0! \\ &= n! \times \left(1 - \frac{1}{2!} + \frac{1}{3!} - \dots + \frac{(-1)^{n-1}}{n!} \right) \end{aligned}

and so, if we define by P(n) the probability of getting at least one out of n members right (let’s not confuse this with P(n,k)), we have

\begin{aligned}[t] P(n) &= \frac{A(n)}{n!} \\ &= 1 - \frac{1}{2!} + \frac{1}{3!} - \dots + \frac{(-1)^{n-1}}{n!}. \end{aligned}

With the above formula, let’s study the behavior of the values of P(n).

\begin{array}{c|c} n & P(n) \\ \hline 1 & 1.000000 \\ 2 & 0.500000 \\ 3 & 0.666667 \\ 4 & 0.625000 \\ 5 & 0.633333 \\ 6 & 0.631944 \\ 7 & 0.632143 \\ 8 & 0.632118 \\ 9 & 0.632121 \\ 10 & 0.632121 \end{array}

You can see that the values go up and down. However, they quickly get close to about 0.632121. In fact, we are sure they won’t get too far from that after some point. Note that the difference between consecutive values of n is \dfrac{1}{n!}. Since n! gets large rapidly, \dfrac{1}{n!} gets very small rapidly. Moreover, aside from the changes getting very small rapidly, they also take turns going in opposite directions, so any “attempts” to break away from this limiting value are immediately undone by the next change.

This reasoning can made just a bit more rigorous to conclude that indeed the answer is that the probability, in fact, stays roughly the same as n gets large.

 

An Infinite Series

We can do even better than 0.63, in fact, if we want a name for this value. Euler’s number, denoted in many calculators as e with approximate value e \approx 2.71828, is a magical and mysterious thing, and if I were to try and explain all of its awesome properties, I would never finish this article. Anyway, one of the cool things about it is that for any number x, the sum

\displaystyle 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots

gets closer and closer to the exponential e^x the more terms we add.

If we let x = -1, this means that

\displaystyle 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots

gets closer and closer to e^{-1} = \dfrac{1}{e} \approx 0.37.

Hence, from simple manipulation, we see that

\displaystyle \frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \dots

gets closer and closer to 1 - \dfrac{1}{e} \approx 0.63 the more terms we add. But in fact the sums of the first n terms here are exactly our values of P(n).

 

Exercise: The Case n = 7

e0097535b9082b6bd787e3d4a7955c5c92a32c4fc538e5d381aa6eef491b86bc.jpg

These girls’ stage names are JiU, SuA, Siyeon, Handong, Yoohyeon, Dami, and Gahyeon.

  1. Based on the formula above, what are the odds you will get at least one of them right?
  2. Do try and identify these members.
  3. Bonus: try to identify them in the clip below.

The 2019 Music Log: Ep. 1 (a reboot)

(aka the real reason I launched this blog)

So, here we are, rebooting my 2019 Music Log, which I started on Twitter. For my newer readers or those who didn’t follow me from Twitter, this was a Twitter thread in which I decided to review what I was listening to. Last year, it was mostly metal album reviews; this year, it seems I’ve turned to K-Pop singles, discussing an occasional metal album here and there.

While I enjoyed doing this thread very much, I decided that I wanted to change things up for a couple of reasons. First, navigation was a nightmare. The thread was at roughly 200 tweets long, meaning if I wanted to dig up something from March I’d have to sift through a lot of stuff. More than that, I found my chosen two-tweet format limiting. Some songs I didn’t feel like discussing for more than one tweet. Other songs I really wanted to dive into in more detail. With me deciding to be more proactive in pursuing my creative interests, I’ve decided (with some encouragement/prodding from friends) to launch this blog, and to take the Music Log here.

First major change: I’ve decided to somewhat try and deflate the ratings. Followers of my previous thread may notice that I handed out a lot of 4s. I grade like a teacher, partly because I am one, so I like to give high scores. This also goes with my philosophy of generally trying to see the good/enjoy in music, though of course with a critical ear. However, as a result I find that I’ve given a lot of songs 4s even though my enjoyment levels over these vary rather wildly. Thus, I’ve decided to move with a working average-to-good song rating of 3.5, moving everything else appropriately. This decision is effective now, but will not affect older ratings. I’m too lazy to revisit five months’ worth of reviews, and I’ve already revisited most of them anyway.

(Speaking of which: I will, however, continue doing a revisited feature, albeit slightly tweaked. I’ll focus less on amending older reviews and more on recapping what grew on me from the last month. More on this on the 15th of July.)

Anyway, without further ado, here is the rebooted 2019 Music Log!

Note: Before anyone asks, I’m not gonna cover any of the BTS World songs yet; I’ve figured I’ll do a full breakdown/review of the album once it comes out in its entirety. I’m still gonna post my Map of the Soul: Persona review (not-really-spoiler: I like it) at some point. I’m really backlogged with regards to album reviews, and I hope to be able to fix this soon.


 

Red Velvet, “Zimzalabim” (3.5/5)

I don’t mind messy in my pop music (I will fight to the death for songs like “Wolf” and “I Got A Boy”) but I do prefer, if not a proper chorus, some central melody amidst the chaos. That said, the chanted titular refrain is not quite it. I get the purpose and even the appeal, but within the framework of the song it serves as example #22537689 of the trap-inspired, momentum-killing chorus that has infested modern American pop music, and now K-Pop. (The background chimes sadly do not help it.) Otherwise, though, there’s a lot to like about this song. The melodic parts are reliably infectious, the electro house dance break is a nice infusion of energy, the vocals in the bridge are spectacular, and the spirited final chorus is one I wish they’d utilized more throughout the song.

 

Stray Kids, “Side Effects” (3.5/5)

Had I dropped a review for this one the same day I listened to it I would probably have given it a 2.5. This song is rather inscrutable, alienating even for the first few spins, but a pulsating bassline and some subtle hooks reward the persistent listener. It is still a little too stop-and-go for my liking, and I still prefer “Miroh” and its galvanizing melody, but this is a daring piece of music that has won me over.

 

SF9, “RPM” (3.5/5)

It seems like SF9 heard all my complaints about their last comeback and quickly fixed them. The needless Auto-Tune is mostly gone. They’ve replaced the languid reggae-esque verses with some chugging electric guitar. They do come in with a rather jarring drop that had me mouthing the chorus of J-Kwon’s “Tipsy” over it for some reason, but they do actually follow it up with a proper sung chorus, something I wish more artists would do! This isn’t quite as anthemic as “Now Or Never,” but this is on the good side of the SF9 releases I’ve heard.

 

Lay, “Honey” (1.5/5)

I admire Lay’s work as one of EXO’s vocalists, but his solo material just hasn’t been for me. That said, last year’s “Namanana” was pretty nice. This one throws away all the goodwill that one built up with me, somehow managing to be both forgettable and incredibly obnoxious at the same time. The repetitive and rather corny music box leitmotif is grating enough, and his disaffected delivery isn’t helping keep my interest, but the random “skrrting” is the final nail in the coffin. I’ve forgiven boy groups for doing it like once or twice in an otherwise good song, but Lay took it way too far. I don’t really see myself returning to this.

 

Twice, “Breakthrough” (4/5)

I’m a fan of Twice’s upbeat concepts, but this is absolutely a style I want them to explore further. Those gorgeous harmonies, that sultry chorus, that brassy instrumental that is edgy enough to be exciting without succumbing to trendiness. It vaguely reminds me of some of my favorite Mamamoo material. While I’m not sure I’d really call it a breakthrough, I really enjoy this.

 

Twice, “Happy Happy” (3.5/5)

This is lighthearted summer fun that thankfully doesn’t go into “BDZ”-esque cloying territory. It’s not the showstopper that last year’s “What Is Love” was, and it doesn’t have the knockout moment that defines Twice’s best work, but it’s more than adequate.

 

Somi, “Birthday” (2.5/5)

Congratulations to Somi for finally debuting! Now she gets to put out a disappointing drop chorus like everyone else. The rest of the song is fine, promising even (though I could do without some of the Meghan Trainor-isms) but based on this and his other recent material it seems that Teddy has forgotten how to write an actual chorus. What a shame.

 

Monsta X feat. French Montana, “Who Do U Love?” (4/5)

I’m really not sure that I want Monsta X to keep doing this style (as big a fan as I am of it), but do they pull it off. French Montana’s rap verse is awkward, clunky, and has the annoying skrrting noises I complained about above, to the point that I can’t help but imagine if one of the group’s very capable rappers had just taken that verse instead, but the pleasant side effect of this otherwise superfluous feature is that we get to hear I.M and Joohoney sing, and they’re not bad at it. Everyone who knows my retro instincts would figure out that this is bait for me, and I am absolutely taking it.

 

Ateez, “Illusion” (3.5/5)

The easygoing, sing-songy even chorus is just so ridiculously sticky. It’s the kind of slurred, Auto-Tuned singing that can get irritating, but the melody is so hooky that I forgive it that. Other than that it’s a straightforward hip-hop song, but a more than adequate one.

 

Ateez, “Wave” (3/5)

I feel that “Illusion” is the better track, as this is too tropical pop for my liking, but this song got them their first win, so I can’t really complain. Besides, the square wave synth in the prechorus is awesome, and they have the charisma to pull this off.

 

Taylor Swift, “You Need To Calm Down” (3/5)

Lorde’s “Royals” is a decent song, but I don’t think it needed to be remade, let alone repackaged into a different track, this soon.

 

Bonus clip:

Siyeon, “Speechless”

Speaking of remakes. I love Lee Siyeon. That’s it. Seriously, this might be my new favorite special clip of theirs. While her “Faded” cover is close to my heart and has helped me recruit a few new InSomnia, this one is a far better showcase of her vocals, especially her criminally underutilized lower range. I’ve been pretty loud about emphasizing that songwriting is more important to me than vocal talent or technical ability, but Dreamcatcher have long had both in spades anyway, and I think they’d definitely be a bit worse off without the bonafide rock star main vocal/goddess that Siyeon is, so I’ll let her flex on all of you here.


And that’s it for the first episode of the 2019 Music Log! See you all… not sure when I intend to write another one. Maybe Friday, but no promises. I don’t know yet.

First post, and a brief intro

Welcome to my little corner of the internet! I’d been hinting at this for a while now on my Twitter, but I’ve decided to start a blog. This is a space for things I’d like to have more than 280 characters for. Most of my posts here will be about music, specifically K-Pop and metal. I’ll probably end up posting a lot of other things, though, like math (I just learned WordPress has improved its \LaTeX support, yay!), art, poetry, music, basketball, and miscellaneous rants. Basically, this will be my Twitter, but more verbose, and deader.

 

About me

I’ve had my fair share of aliases, but these days I tend to go by X^{**}. In mathematics, this is the double dual space of the vector space X. What that is, I might explain in greater detail if I’m not feeling too lazy.

Anyway, I’m a mathematics grad student and teacher in my late 20s. I listen to a lot of music, but these days my attention is mostly on K-Pop and most subgenres of metal (except perhaps funeral doom and drone, as I have little patience for them). Some of my favorite musical acts are Dreamcatcher, Madder Mortem, My Chemical Romance, Riverside, Spawn of Possession, Dodecahedron, Nevermore, and Symphony X, among many, many others. I mess around on the guitar and keyboards a bit, and like to do ill-advised karaoke to songs I have no business even attempting to sing. Rest assured, an actual release is probably years away. Or not.

I’ve also been playing Pokémon most of my life. My favorites are (Mega) Houndoom and Jigglypuff. Others I love, in no particular order: Mismagius, Honchkrow, Escavalier, Joltik, Roserade, Aegislash, Haxorus, Cinccino, and yes, Corviknight (despite it not having been released yet).

That’s all for now.