cp's OEIS Frontend

A370886 Number of Git graphs (also called Git feature branch graphs) with n vertices.

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