How Many Relationships? Combinatorics Problem

In a webcomic I'm reading, there are twelve trolls on another planet that form lots of relationships with each other. A given troll can form a relationship with any other troll. One of the trolls, Nepeta, keeps a chart of relationships between the beings (including herself). There can be up to 66 pairings between the trolls at any given time, but there can be less; a troll is not necessarily in a relationship. If a troll can be in at most 11 relationship at a time, How many different charts can Nepeta make?

Please give your answer along with the math behind it. I really feel that I should know how to do this, but the exact method escapes me. Thanks!

Note by Trevor B.
7 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

Supose that T(n)T(n) is your problem with nn trolls. Then you are asking for T(12)T(12). I will give a recurrence and then compute base cases, so that T(12)T(12) can be calculated.

Choose a particular troll XX. There are two cases, that troll is NOT calling someone and here there are T(n1)T(n-1) different and unique cases, of pairings among the other n1n-1.

If it is indeed paired with someone, there are n1n-1 possible relationships with XX. In any case, the other n2n-2 trolls can pair in T(n2)T(n-2) ways, and each of these decisions will produce a different pairing for the nn. So here , by multiplicative law, we have (n1)T(n2)(n-1)T(n-2) ways.

So by additive law, T(n)=T(n1)+(n2)T(n2)T(n)=T(n-1)+(n-2)T(n-2). And for 0 and 1 persons, there is only one case possible, namely no pairs at all, so the recursion starts with T(0)=T(1)=1T(0)=T(1)=1. Given this, then T(12)=140152T(12)=140152

This problem is part of graph theory, and using graph theory language it asks for the number for matchings in a (numbered) K12K_{12}. A matching is basically that, pairings such that each element is at most at 1 but not necesarilly, and K12K_{12} is the graph of vertex and all edges. We interpret this as that there are 1212 persons and an edge is a possible pairing. These are preciselly the telephone numbers In particular, you are asking for T(12)=140152T(12)=140152

There are other particular numbers that we can count, like the number of perfect matchings in a graph (that is, when everyone has a pair) and the number of matchings with exactly kk pairs.

Additionally, here is Haskell code to produce the series, just for the kicks:

let te = 1:1:zipWith3 (\a b c-> a+b*c) (tail te) [1..] te

Now, given any graph this, the number of matchings in that graph, is called the Hosoya index. We can calculate the index in polinomial time (that is, "fast") if the graph is complete and other special cases (as an example, the code I just gave).

But it is #P-complete to find an algorithm that computes it for any graph, and in fact #P=P \#P=P implies the famous Clay Millenium Prize Theorem P=NPP=NP. If someone were to find such algorithm, then it would also prove P=NPP=NP. Funny how things connect. Hope this helps!

Diego Roque - 7 years, 6 months ago

Log in to reply

If I understand you right, then since we have twelve trolls and 6 pairings, don't we necessarily have everyone in exactly one relationship? Just want to make the question clear before answering..

Michael Tong - 7 years, 6 months ago

Log in to reply

It is up to six pairings.

Diego Roque - 7 years, 6 months ago

Log in to reply


Swapnil Saste - 7 years, 6 months ago

Log in to reply

My homestuck powers can't handle the math. I expected it to be like a regular shipping equation like Dirk mentioned (which is (n^2 - n) / 2), but it isn't, so yeah, damn son. Pretty cool to see the solution though.

Edmund Sia II - 7 years, 1 month ago

Log in to reply

If there's only one pair then number of relationships possible is 12C2 (Combination of two from 12 options)

For 2 pairs we have (12C2 * 10C2)/2! i.e. ((No of ways 2 can be selected out of 10) *(No of ways 2 can be selected from the remaining 10)) / (No of ways two pairs can be arranged.)

Similarly for 3 pairs we will have (12C2 * 10C2 *8C2)/3!

Similarly we can get no of relationships possible if there would have been 4,4 or 6 pairs

Adding them up we get 12C2 + (12C2 * 10C2)/2! + (12C2 * 10C2 * 8C2)/3! + (12C2 * 10C2 * 8C2 * 6C2)/4! + (12C2 * 10C2 * 8C2 *6C2 * 4C2)/5! +(12C2 * 10C2 * 8C2 *6C2 *4C2 * 2C2)/6!

66 + 1485+13860 +51975+62370+10395


Suyash Chandak - 7 years, 6 months ago

Log in to reply

For no pairs, 12C0 = 1 . Answer should be 140151+1 = 140152

Arun Shankar S - 7 years, 6 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...