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 $6$ 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 $1$ 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!

#Combinatorics

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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](https://brilliant.org)`	example 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"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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

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

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

So by additive law, $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)=1$ . Given this, then $T(12)=140152$

This problem is part of graph theory, and using graph theory language it asks for the number for matchings in a (numbered) $K_{12}$ . A matching is basically that, pairings such that each element is at most at 1 but not necesarilly, and $K_{12}$ is the graph of vertex and all edges. We interpret this as that there are $12$ persons and an edge is a possible pairing. These are preciselly the telephone numbers http://en.wikipedia.org/wiki/Telephonenumber(mathematics). In particular, you are asking for $T(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 $k$ 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$ implies the famous Clay Millenium Prize Theorem $P=NP$ . If someone were to find such algorithm, then it would also prove $P=NP$ . Funny how things connect. Hope this helps!

Diego Roque - 7 years, 4 months ago

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, 4 months ago

It is up to six pairings.

Diego Roque - 7 years, 4 months ago

140152

Swapnil Saste - 7 years, 4 months ago

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 - 6 years, 12 months ago

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

140151

Suyash Chandak - 7 years, 4 months ago

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

Arun Shankar S - 7 years, 4 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$