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,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

Vaclav Kotesovec, Table of n, a(n) for n = 0..860

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

Mathematica

Table[1 + Sum[Sum[Abs[StirlingS1[k, j]] * Binomial[n-k-1, k-j-1], {j, 1, k-1}], {k, 1, n-1}], {n, 0, 30}] (* Vaclav Kotesovec, Feb 07 2026 *)

Crossrefs

Sequence in context: A135310 A135337 A133365 * A135335 A336989 A066723

Adjacent sequences: A370883 A370884 A370885 * A370887 A370888 A370889

Keyword

nonn

Author

Julien Courtiel, Mar 04 2024

Status

approved