login
A370886
Number of Git graphs (also called Git feature branch graphs) with n vertices.
0
1, 1, 1, 2, 5, 13, 36, 105, 321, 1024, 3395, 11661, 41378, 151327, 569225, 2198354, 8703137, 35270825, 146143500, 618422645, 2669920997, 11749633216, 52662799223, 240219771145, 1114389479586, 5254248378467, 25163576418877, 122344307889466, 603563444819805, 3019832976420725, 15316879844905428
OFFSET
0,4
COMMENTS
A Git (feature branch) graph is a DAG consisting of a "main branch", i.e., a directed path of black vertices, and a set of "feature branches", i.e., directed paths of white vertices starting and ending on vertices of the main branch, such that two feature branches cannot end on the same vertex of the main branch.
LINKS
J. Courtiel and M. Pépin, Random Generation of Git Graphs, 2024 (preprint).
FORMULA
Let g(n,k) be the number of Git graphs with n vertices, k of which are black. Then a(n) = Sum_{k=1..n} g(n,k).
We have:
g(n,k) = (n-1)*g(n-1,k-1) + Sum_{j>=0} (k-1)*g(n-1-j,k-1),
g(n,k) = Sum_{f=1..k-1} Stirling1(k,f)*binomial(n-k-1,k-f-1), for k < n, where Stirling1(k,f) denotes the unsigned Stirling numbers of the first kind.
g(n,n) = 1.
EXAMPLE
There are 5 Git graphs of size 5 with 3 black vertices:
@---@---@ @---@---@ @---@---@
\ / \ / \ / |\ / /
O O -O-O- | O /
\_O_/
@---@-----@ @-----@---@
\ / \ /
O-O O-O
CROSSREFS
Sequence in context: A135310 A135337 A133365 * A135335 A336989 A066723
KEYWORD
nonn
AUTHOR
Julien Courtiel, Mar 04 2024
STATUS
approved