cp's OEIS Frontend

A182220 Largest number k such that there exists an extensional acyclic digraph on n labeled nodes with k sources.

%I A182220 #42 Oct 14 2021 18:09:41
%S A182220 1,1,1,2,2,3,4,5,5,6,7,8,9,10,11,12,12,13,14,15,16,17,18,19,20,21,22,
%T A182220 23,24,25,26,27,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,
%U A182220 45,46,47,48,49,50,51,52,53,54,55,56,57,58,58,59,60,61
%N A182220 Largest number k such that there exists an extensional acyclic digraph on n labeled nodes with k sources.
%C A182220 Also the length of row n of A182162.
%C A182220 This seems to be simply the natural numbers, with the terms in A000325 repeated.
%C A182220 It appears a(n+1) is the number of distinct possible heights of binary trees with n nodes. The minimum height of an n node binary tree is A000523(n), the maximum height is n-1 and all intermediate heights are possible. This conjecture is therefore equivalent to the conjectured formulas. - _Yuchun Ji_, Mar 22 2021
%C A182220 Conjecture: Partial sums of A347523, thus a(n) is the number of nonpowers of 2 <= n-1, or with offset 0: a(n) is the number of nonpowers of 2 <= n. - _Omar E. Pol_, Sep 30 2021
%H A182220 S. Wagner, <a href="http://math.sun.ac.za/swagner/DigraphsFull.pdf">Asymptotic enumeration of extensional acyclic digraphs</a>, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).
%F A182220 Conjecture, for all n >= 3: a(n) = A083058(n-1) + 1 = n - 1 - A000523(n-1) = n - 1 - floor(log(2,n)). - _Antti Karttunen_, Aug 17 2013
%F A182220 Conjecture:  a(1) = 0, a(n) = n - 1 - Sum_{i=1..n} sign(floor((n-1)/ 2^i)), n > 1. - _Wesley Ivan Hurt_, Feb 02 2014
%F A182220 Conjecture: a(n) = n - Sum_{k=0..n-2} A036987(k). - _Paul Barry_, Mar 07 2017
%p A182220 A001192 := proc(n) option remember: if(n=0)then return 1: fi: return add((-1)^(n-k-1)*binomial(2^k-k, n-k)*procname(k), k=0..n-1); end: A182162 := proc(n, l) local vl: vl := add((-1)^(k-l)*binomial(n, k)*binomial(k, l)*binomial(2^(n-k)-n+k, k)*k!*(n-k)!*A001192(n-k), k=l..n): return vl: end: A182220 := proc(n) local l: for l from n to 1 by -1 do if(A182162(n, l)>0)then break:fi:od: return l: end: seq(A182220(n),n=1..60);
%Y A182220 Cf. A083058, A182162.
%K A182220 nonn
%O A182220 1,4
%A A182220 _Nathaniel Johnston_, Apr 19 2012