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
KEYWORD
nonn
AUTHOR
Julien Courtiel, Mar 04 2024
STATUS
approved