%I #14 Mar 30 2024 11:24:07
%S 1,1,1,2,5,13,36,105,321,1024,3395,11661,41378,151327,569225,2198354,
%T 8703137,35270825,146143500,618422645,2669920997,11749633216,
%U 52662799223,240219771145,1114389479586,5254248378467,25163576418877,122344307889466,603563444819805,3019832976420725,15316879844905428
%N Number of Git graphs (also called Git feature branch graphs) with n vertices.
%C 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.
%H J. Courtiel and M. Pépin, <a href="https://hal.science/hal-04487862">Random Generation of Git Graphs</a>, 2024 (preprint).
%F 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).
%F We have:
%F g(n,k) = (n-1)*g(n-1,k-1) + Sum_{j>=0} (k-1)*g(n-1-j,k-1),
%F 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.
%F g(n,n) = 1.
%e There are 5 Git graphs of size 5 with 3 black vertices:
%e @---@---@ @---@---@ @---@---@
%e \ / \ / \ / |\ / /
%e O O -O-O- | O /
%e \_O_/
%e @---@-----@ @-----@---@
%e \ / \ /
%e O-O O-O
%K nonn
%O 0,4
%A _Julien Courtiel_, Mar 04 2024