×

# 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!

Note by Trevor B.
3 years, 2 months ago

Sort by:

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! · 3 years, 2 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. · 2 years, 9 months ago

140152 · 3 years, 2 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.. · 3 years, 2 months ago

It is up to six pairings. · 3 years, 2 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 · 3 years, 2 months ago