Math & systems theory question: Nodes, links, systems

Let’s say you have Nodes which are the basic building blocks (A, B, C). Then you have Links which are connections between Nodes (AB, BC, CD). Then you have Systems which are patterns of connections (ABC). Presume that 1) Nodes can only be linked once to count as a Link 2) Links can only be combined once to count as a System 3) The order of arrangement is irrelevant. E.g.:

With 1 Node, (A) you have 1 Node, 0 Links, 0 Systems because A has no other Node to link to and there are no Links to combine into a System.

2 Nodes (A, B) = 1 Link (AB) = 0 Systems because you only have 1 Link and a System requires 2+ Links.

3 Nodes (A, B, C) = 3 Links (AB, AC, BC) = 1 System (ABC)

4 Nodes (A, B, C, D) = 6 Links (AB, AC, AD BC, BD, CD) = 4 Systems (BCD, ACD, BCD, ABCD)

I started doing 5 Nodes and realized it was going to be unwieldy. Someone else must have worked on this and come up with a way to calculate it.
As for why anyone would care to nerd out on this: It may be relevant to many complex systems. It’s the basis of the network effect in economics* and may be applicable to other fields which we can discuss later. It’s one of the main reasons why Beta eventually had no chance against VHS, Sony’s consoles have been beating Microsoft’s, Youtube/Steam/Facebook are so dominant.

Note how the number of Links increases more than linearly as a function of the number of Nodes. The number of Links starts off lower than the number of Nodes but quickly catches up. When you go from 1000 Nodes to 1001Nodes, you’re only adding 1 Node but you’re adding 1000 (potential) Links. I expect something similar will happen with Systems but I don’t know how to calculate this efficiently.
When answering, please keep in mind that many readers (like me) don’t have a math background.

ETA: Please note that a System can be composed of 2+ Links and can only use each Node once so a 5 Node network with A, B, C, D, E as Nodes could have ABC, ABD, ABE, ACD, ACE, ADE, ABCD, ABCE, ABDE, ABCDE etc as Systems.
Beyond the arrangements of Links that are System, are there higher-order levels which can be discerned?

I don’t understand your example. A “system requires 2 links” which “can only be combined once” so with 6 links (2+2+2) you should have a maximum of 3 systems, no?

You’re right, there is an ambiguity in whether a System should be defined as 1) greater than a Link i.e.: 3+ Nodes or 2) a combination of Links. Now that you make me realize this (thank you), I’m interested in the way to figure this out using either definition.

If using the definition of “a combination of Links”, then Systems should be written as (AB+CD, AC+BD, AD+BC).

Sorry for the capitalisation and double posts, I’m in the process of figuring it out. Capitalisation may lead to fewer misunderstandings.

First I’ll note that you don’t actually ask a question in the OP so I’m not 100% sure what you’re after.

That said, I think you’re trying to count (and possibly enumerate) the number of subsets of a set.

Take the set S = {a, b, c} with three elements and we’ll generalize to a set with n elements.

There are 2^n subsets of S.

There is always the 1 subset with no elements. {}

There are n subsets with 1 element: {a}, {b}, {c}.

There are n (n - 1) / 2 subsets with two elements: {a, b}, {a, c}, {b, c}.

Therefore there are 2^n - n (n - 1) / 2 - n - 1 subsets with more than two elements.

And there’s a well-known formula for the number of subsets of a particular size k. These are known as combinations. So, if a link is defined by the two nodes it connects, the number of links would be [sub]n[/sub]C[sub]2[/sub], which = n(n-1)/2.

Is the OP thinking of matroids?

I’m rusty so bear with me. Below I’ll give some terminology that you can google and what I think the answers are.

In graph theory, what you call Nodes are called vertices, what you call Links are called edges, what you call Systems are called simple paths.

You are dealing with complete graphs.

The number of edges (Links) in a complete graph G=(V,E) where the number of vertices is n is e = n C 2 = n!/(2!x(n-2)!)

The number of simple paths in a complete graph is (n-2)!.

This all assumes I understand your question.

He didn’t really ask a question. I’m hoping he comes back to clarify.

So, 5 Nodes would make for 32 - 10 - 5 - 1=16 subsets with more than 2 elements?

This all assumes I understand my question : )
I was thinking about combinations of various kinds while taking a walk this morning and I vaguely perceived patterns I knew I didn’t know enough about to clearly discern so I asked here.

Matroids and graph theory seem at least related.
Lance is right that I didn’t ask a question. I wanted to know how to calculate how many subsets of 2 in a set of n and how many double subsets of subsets of 2 in a set of n. I might not want to limit it to subsets of 2 and double subsets of subsets of 2 but it may be simpler to start there.

Correct.

I’ll add that Pascal’s triangle does a bunch of nifty things and counting subsets is one of them. For example the fifth row of Pascal’s triangle is 1, 5, 10, 10, 5, 1. These numbers are the number of subsets of a set with five elements that contain 0, 1, 2, 3, 4, 5 elements. We also have 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5.

In that case, as has already been pointed out, with n elements the number of subsets of 2 is n(n-1)/2.

Example: n = 4. {A, B, C, D} -> {AB, AC, AD, BC, BD, CD}

So the number of subsets of size 2 of that is n(n^2 - n - 2)(n-1)/8:

{{{AB}, {AC}}, {{AB}, {AD}}, {{AB}, {BC}}, {{AB}, {BD}}, {{AB}, {CD}}, {{AC}, {AD}}, {{AC}, {BC}}, {{AC}, {BD}}, {{AC}, {CD}}, {{AD}, {BC}}, {{AD}, {BD}}, {{AD}, {CD}}, {{BC}, {BD}}, {{BC}, {CD}}, {{BD}, {CD}}} (15 of them).

This number increases like n^4.

If I wanted to know the number of subsets of 3 for n, how would that go? Could I have the formula and an example?

Sure. The number of subsets of size 3 is given by the binomial coefficient (n ¦ 3). To calculate this, you can use the formula n(n-1)(n-2)/6 = n^3/6 - n^2/2 + n/3 .

Example: {A, B, C, D} -> {{A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}}    n = 4 -> (n ¦ 3) = 4

Some examination of the factorial function and how it’s used to calculate combinations might help make this clearer.

n! can be thought of as “given a list of n things, how many ways can you arrange them.” There’s n choices for the first item, and n-1 for the second, and n-2 for the third… all the way down to just 1 choice for the nth.

So for n choose k, you want “given a list of n things, how many different ways can you choose k of them, where order doesn’t matter”.

First, figure out how many ways there are to arrange k items out of your set of n. This looks a lot like n!, except that it cuts off. n choices for the first item, n-1 for the second, and so on. But instead of getting all the way down to 1 choice for the nth item, you stop at (n-k+1) choices for the kth item.

So, it looks like (n)(n-1)…(n-k+1).

The remaining terms that would make it a full n! are: (n-k) * (n-k-1) * …

That sequence is (n-k)!

So, the sequence that cuts off is the original n!, then divide out the terms from (n-k)!

Or: n! / (n-k)!

Ok, so n! / (n-k)! is the number of ways to arrange k items from a list of n, but that overcounts. For example, if we have items A and B, this will include both (A, B) and (B,A) as separate elements.

How much does it overcount by? It overcounts by the number of ways there are to arrange a list of k items. Hey, that’s just our first definition, but with a k: k!

So, dividing that out, we get:

n choose k = n! / ((k!) * (n-k)!)

Discrete Math is the broader subject. It deals with math of things that can be counted with integers.

Games are good sources for basic problems. For example: How many different poker hands are there?

Well, there are 52 cards, and a hand consists of 5 of them.

So that’s 52 choose 5 = 52! / (5! * 47!) = about 2.5 million.

Hmm. How many of those are flushes.

Well, there are 13 cards in a suit, so there are 13 choose 5 ways to make a flush of one suit. Multiply by 4 for all the suits, and you get:

4 * 13 choose 5 = 4 * 13! / (5! * 8!) = 5184.

And so on.

Minor nitpick… first you transposed two digits. It should be 5148. Second you included straight and royal flushes.

13 choose 5 * 4 choose 1 - 10 choose 1 * 4 choose 1 = 5108 flushes

Thanks for the typo correction.

Any directed graph that is a complete graph will have N-1 edges, so it really depends on what your definition of a sub-graph is. But really this is combinations.

Here is an image that a “unit-test” makes in some of my code, it is all possible graphs for 6 vertices.

But in the above case where you have n elements the number of k-combinations is equal to the binomial coefficient.

So if you have n objects that you want in k groupings, where n and k are both positive integers the formula is:

C(n,k) = n!/(k!(n-k)!)
or C(n, k) = ff(n, k)/k!

For sets of 3

Items | combinations
1000 = 166,167,000
1001 = 166,666,500
2000 = 1,331,334,000
100,000 = 166,661,666,700,000

Calculating that last one took my computer 455 ns ± 1.13 ns ( 7 runs of 1000000)

And for how many 52 card 5 hand combos, that is 2,598,960 which took 455 ns to calculate.
If n is a Number and k is an Integer and k != 1 and n != k, Then you can use a series of primes like the sieve of Eratosthenes and find k using modular arithmetic pretty quickly.

O(log(n)) or close to O time as far as time complexity goes.
It actually is impossible for me to tell the difference between calculating how many 5 card hands in a deck of cards as it is to find how many 16 card hands in a deck of 377964473009227 cards

The answer is 220 digits long:

8290793268294641721831827222405371982951642473023392319392800092473572670335548152498579483947828534313783166589487780378733991894277888742373984661930195373959047175443207948990999998660853921026878913196008125633914580

387 ns ± 1.47 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Note that ns is nanosecond or 0.000000001 seconds. So my machine calculated that last result in about the time that light takes to travel the length of a football field.

As written this is incorrect. I suspect you meant to say something else or left something off.