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

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

Author

Julien Courtiel, Mar 04 2024

Keywords

• nonn

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.

Examples

			There are 5 Git graphs of size 5 with 3 black vertices:
@---@---@    @---@---@    @---@---@
 \ / \ /      \     /     |\ /   /
  O   O        -O-O-      | O   /
                           \_O_/
@---@-----@     @-----@---@
     \   /       \   /
      O-O         O-O
		

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.