William D. JonesLooking for a specific integer sequence, but OEIS search is failing...
"Number of possible directed graphs with 'n' nodes"
I think it's 1, 6, and uhhh... I lost count after that.
I remember talking about this with @steve a while ago, before Twitter went to hell:
https://x.com/cr1901/status/1469005874517717001
But when he and the other responder deleted (I don't blame them), the context was lost...
alexing@alexing According to past-me, nodes were not interchangeable: https://mastodon.social/@cr1901/116302086631790379
But good to know :D!
I Can't Believe It's Not Zero!@alexing I remembered the actual sequence I wanted, still don't have an OEIS, but it can be derived from Steve's reply:
0 nodes: 1 graph
1 node: 1 or 2 graphs (do you allow a -> a?)
2 nodes: 3 graphs (disconnected, a->b, b->a)? or more (self-loops allowed)?
@cr1901 self-loops allowed is the easy case IIRC, I think it's in one of Doug McIlroy's papers.
@steve No, these weren't DAGs, loops are allowed. I vaguely recall John McCall chiming in with the correct sequence. But that tweet is long gone (and based on location info, I was on my phone at the time, so I can't even look at my browser history).
I also remember that while calculating the number of graphs is easy, there's no "plug it in and immediately get an answer" formula for arbitrary 'n'. So for large 'n', you're f***ed :D.
@cr1901 are (a -> b) and (b -> a) different graphs from your perspective?
@cr1901 Then it should be 2^(n^2) if self loops are allowed and 2^(n^2-n) if not. (For each ordered pair of nodes (a,b) either there is or isn't an edge (a->b))
@steve You're correct :D! I just remembered that in my original tweet, I wanted to sum up those values for each "n" from 0 to 2^k to get "number of possible FSMs that fit into k-bits".
I was using _that_ calculation as a proxy for "number of possible computer programs that can fit into a k-bit address space". I chose k=16 b/c it seems small enough. But uhh, even for k=16, the number is... large.
@cr1901 It's a reasonable estimate for FSMs, though not quite right (FSMs don't care about node labels, only start and accept states, and have alphabet symbols associated with their transitions). You could fix it up without too much fuss, though, and Doug probably did so back in the 1950s, so I expect it's on OEIS.
@steve Yea, in my state transition diagrams, node labels matter because each node is supposed to represent "concatenation of all state bits into a bitvector". Each node has a different bitvector value to reflect physical reality. So I'm using FSM as an incorrect shorthand for "state transition diagram".
Not caring about node labels allows you to e.g. have two states could have the same bitvector value but different valid transitions.
@steve Anyways, I don't have to do exact calculations to know:
* There are A LOT of possible programs.
* Most of them are useless.
* It's a small miracle that we can find useful ones in a principled manner.
@steve One final observation... 2^(2^n) is actually a reasonable approximation to "total number of possible programs that use n bits of state or less", because the ratio
2^(2^n)/2^(2^(n + 1))
approaches 0 extremely quickly. Trying to sum up the smaller values of "n" basically has nil effect. Wish I realized that back in late 2021. Ahhh well...
@steve I have bad ADHD today, and I started thinking about the "number of possible FSMs with 'n' states" problem again. Also lamenting the fragile nature of hyperlinks.