cp's OEIS Frontend

A358585 Number of ordered rooted trees with n nodes, most of which are leaves.

%I A358585 #17 Jan 13 2024 16:13:32
%S A358585 1,0,1,1,7,11,66,127,715,1549,8398,19691,104006,258194,1337220,
%T A358585 3467115,17678835,47440745,238819350,659060677,3282060210,9271024542,
%U A358585 45741281820,131788178171,644952073662,1890110798926,9183676536076,27316119923002,131873975875180,397407983278484
%N A358585 Number of ordered rooted trees with n nodes, most of which are leaves.
%H A358585 Andrew Howroyd, <a href="/A358585/b358585.txt">Table of n, a(n) for n = 1..1000</a>
%F A358585 From _Andrew Howroyd_, Jan 13 2024: (Start)
%F A358585 a(n) = Sum_{k=1..floor((n-1)/2)} A001263(n-1, k) for n >= 2.
%F A358585 a(2*n) = (A000108(2*n-1) - A000891(n-1))/2 for n >= 1;
%F A358585 a(2*n+1) = A000108(2*n)/2 for n >= 1. (End)
%e A358585 The a(1) = 1 through a(6) = 11 ordered trees:
%e A358585   o  .  (oo)  (ooo)  (oooo)   (ooooo)
%e A358585                      ((o)oo)  ((o)ooo)
%e A358585                      ((oo)o)  ((oo)oo)
%e A358585                      ((ooo))  ((ooo)o)
%e A358585                      (o(o)o)  ((oooo))
%e A358585                      (o(oo))  (o(o)oo)
%e A358585                      (oo(o))  (o(oo)o)
%e A358585                               (o(ooo))
%e A358585                               (oo(o)o)
%e A358585                               (oo(oo))
%e A358585                               (ooo(o))
%t A358585 aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
%t A358585 Table[Length[Select[aot[n],Count[#,{},{0,Infinity}]>Count[#,_[__],{0,Infinity}]&]],{n,10}]
%o A358585 (PARI) a(n) = if(n==1, 1, n--; (binomial(2*n,n)/(n+1) - if(n%2, binomial(n, (n-1)/2)^2 / n))/2) \\ _Andrew Howroyd_, Jan 13 2024
%Y A358585 For equality we have A000891, unordered A185650.
%Y A358585 Odd-indexed terms are A065097.
%Y A358585 The unordered version is A358581.
%Y A358585 The opposite is the same, unordered A358582.
%Y A358585 The non-strict version is A358586, unordered A358583.
%Y A358585 A000108 counts ordered rooted trees, unordered A000081.
%Y A358585 A001263 counts ordered rooted trees by nodes and leaves, unordered A055277.
%Y A358585 A080936 counts ordered rooted trees by nodes and height, unordered A034781.
%Y A358585 A090181 counts ordered rooted trees by nodes and internals, unord. A358575.
%Y A358585 A358590 counts square ordered trees, unordered A358589 (ranked by A358577).
%Y A358585 Cf. A109129, A342507, A358371, A358579, A358580, A358584, A358588, A358590.
%K A358585 nonn
%O A358585 1,5
%A A358585 _Gus Wiseman_, Nov 24 2022
%E A358585 a(16) onwards from _Andrew Howroyd_, Jan 13 2024