A396065 - OEIS

%I #10 May 19 2026 08:37:20

%S 1,1,4,29,335,5665,131705,4028430,156800490,7567091700,443391506250,

%T 31006215829050,2550705276018900,243844277577250350,

%U 26806543530806539500,3357980302742399334000,475494120154548612117000,75572740333888003521315000,13396707931178035747104822000

%N The total number of at-most-4-furcating labeled histories that can be constructed for n labeled leaves.

%C a(n) is the number of "merger histories" of n elements, where at most 4 elements can merge at the same time (see A256006).

%H Emily H. Dickey and Noah A. Rosenberg, <a href="https://doi.org/10.1016/j.dam.2026.04.032">Labeled histories and maximally probable labeled topologies with multifurcation</a>, Discr. Appl. Math. 391 (2026), 192-203. See Table 1.

%F a(n) = (n*(n-1)/2)*a(n-1) + (n*(n-1)*(n-2)/6)*a(n-2) + (n*(n-1)*(n-2)*(n-3)/24)*a(n-3) for n>=4.

%e For n=3, the 4 labeled histories are: (1) merge A with B, then merge the result with C; (2) merge A with C, then merge the result with B; (3) merge B with C, then merge the result with A; (4) merge A, B, and C simultaneously.

%e For n=4, the 29 labeled histories are: the 18 labeled histories with only binary mergers (see A006472(4)); the 6 labeled histories that have a binary merger then a ternary merger; the 4 labeled histories that have a ternary merger then a binary merger; and the 1 labeled history that merges all four elements simultaneously.

%t RecurrenceTable[{A[n]==Binomial[n,2] A[n-1] + Binomial[n,3] A[n-2] + Binomial[n,4] A[n-3], A[0]==0, A[1]==1, A[2]==1}, A, {n, 20}]

%Y Cf. A006472, A256006, A358072 (mergers of up to 3 elements).

%K nonn,easy

%O 1,3

%A _Noah A Rosenberg_, May 15 2026