Julien Courtiel - cp's OEIS frontend

User: Julien Courtiel

Julien Courtiel has authored 2 sequences.

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

Julien Courtiel, Mar 04 2024

nonn

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.

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

J. Courtiel and M. Pépin, Random Generation of Git Graphs, 2024 (preprint).

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.

A287223 Numbers of tree alignments.

Original entry on oeis.org

0, 0, 2, 6, 22, 88, 370, 1612, 7232, 33304, 157102, 757804, 3731352, 18720504, 95519428, 494733144, 2596388976, 13783481424, 73906300822, 399722732236, 2178164438936, 11946745980632, 65898275096796, 365308080119688, 2033992114316240, 11369167905107888, 63769939599193228, 358804271821028088, 2024523256299630832

Offset: 0

Julien Courtiel, May 22 2017

nonn

The notion of tree alignment is due to Jiang, Whang and Zhang (Alignment of trees—an alternative to tree edit).

			For n = 3, the number 6=2x3 corresponds to the number of alignments between a one-vertex tree and a two-vertices tree, or between a two-vertices tree and a one-vertex tree.

C. Chauve, J. Courtiel and Y. Ponty, Counting, Generating and Sampling Tree Alignments, in Algorithms for Computational Biology, 2016, Lecture Notes in Computer Science, vol 9702.

G.f.: (1+sqrt(1-4*t)) * (2+8*t^2-(2-8*t) * sqrt(1-4*t)-12*t+2*sqrt(2)*R ) / (-4*t*(4*sqrt(1-4*t))) where R = sqrt((1-8*t+12*t^2)*(2*t^2+(2*t-1)*sqrt(1-4*t)+1-4*t)) (no combinatorial interpretation known).

cp's OEIS Frontend

User: Julien Courtiel

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

Views

Author

Keywords

Comments

Examples

Links

Formula