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 Can't Believe It's Not Zero!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)?
@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...