A055295
Number of trees with n nodes and 8 leaves.
Original entry on oeis.org
1, 4, 16, 60, 202, 626, 1787, 4755, 11848, 27881, 62265, 132769, 271431, 534358, 1016390, 1873983, 3358043, 5862811, 9993697, 16664380, 27227873, 43658180, 68789775, 106640700, 162829982, 245127960, 364155076, 534285064, 774774427
Offset: 9
A055296
Number of trees with n nodes and 9 leaves.
Original entry on oeis.org
1, 4, 20, 83, 318, 1095, 3495, 10292, 28389, 73586, 180663, 421949, 942537, 2021060, 4176507, 8342823, 16157071, 30410396, 55755744, 99773709, 174579270, 299163528, 502804996, 829905792, 1346834873, 2151396469
Offset: 10
A055297
Number of trees with n nodes and 10 leaves.
Original entry on oeis.org
1, 5, 25, 116, 482, 1834, 6399, 20688, 62355, 176542, 472051, 1198756, 2904166, 6740600, 15042512, 32382969, 67441667, 136233495, 267534126, 511819591, 955658500, 1744487967, 3117961283, 5463991463, 9400016470, 15893600813
Offset: 11
A055298
Number of trees with n nodes and 11 leaves.
Original entry on oeis.org
1, 5, 30, 151, 698, 2896, 11053, 38865, 127339, 390781, 1131055, 3102493, 8105244, 20247770, 48548878, 112089790, 249930985, 539592972, 1130655414, 2304230739, 4575993619, 8870692319, 16812222795, 31196614962, 56750633235
Offset: 12
A055299
Number of trees with n nodes and 12 leaves.
Original entry on oeis.org
1, 6, 36, 199, 984, 4433, 18257, 69390, 245105, 810418, 2522646, 7432876, 20825678, 55717629, 142862730, 352212459, 837368658, 1924861589, 4288250970, 9278750495, 19537503288, 40103712085, 80377128541
Offset: 13
A262395
Difference between the numbers of trees on n vertices with an even number and an odd number of leaves.
Original entry on oeis.org
1, 1, 0, 1, 0, 1, 1, 3, 2, 5, 5, 13, 13, 29, 32, 71, 81, 177, 209, 449, 538, 1148, 1415, 3002, 3736, 7862, 9930, 20877, 26648, 55756, 71767, 149860, 194507, 405332, 529708, 1101502, 1447956, 3006750, 3974959, 8242691, 10948355, 22673357, 30249668, 62583402, 83831176, 173259448, 232917913, 480970826, 648753720
Offset: 2
A262430
Number of trees on n vertices with an even number of leaves.
Original entry on oeis.org
1, 0, 1, 1, 1, 2, 3, 6, 12, 25, 54, 120, 278, 657, 1586, 3885, 9676, 24350, 61974, 159066, 411637, 1072477, 2812147, 7414611, 19650656, 52319946, 139898593, 375536661, 1011726481, 2734793731, 7415449225, 20165442393, 54986240994, 150314506170, 411889913114, 1131183374539, 3113153283443, 8584839296108, 23718157486109, 65645273392938, 181995130879151, 505374042479921, 1405493247220915, 3914493122094481, 10917513971606377, 30489195524251154, 85254349619909519, 238677545463592954, 668973050139380099, 1877097093098685409, 5272616851780131627
Offset: 0
A262431
Number of trees on n vertices with an odd number of leaves.
Original entry on oeis.org
0, 1, 0, 0, 1, 1, 3, 5, 11, 22, 52, 115, 273, 644, 1573, 3856, 9644, 24279, 61893, 158889, 411428, 1072028, 2811609, 7413463, 19649241, 52316944, 139894857, 375528799, 1011716551, 2734772854, 7415422577, 20165386637, 54986169227, 150314356310, 411889718607, 1131182969207, 3113152753735, 8584838194606, 23718156038153, 65645270386188, 181995126904192, 505374034237230, 1405493236272560, 3914493099421124, 10917513941356709, 30489195461667752, 85254349536078343, 238677545290333506, 668973049906462186, 1877097092617714583, 5272616851131377907
Offset: 0
A303840
Unlabeled trees with n nodes rooted at 2 indistinguishable roots that are leaves.
Original entry on oeis.org
0, 1, 1, 2, 4, 10, 24, 63, 164, 444, 1204, 3328, 9233, 25865, 72734, 205656, 583320, 1660318, 4737540, 13551165, 38837535, 111512229, 320681604, 923528963, 2663057582, 7688068638, 22218350303, 64272720521, 186091334380, 539237928902, 1563731491958, 4537823968645, 13176960639940, 38286514506439, 111306880581963
Offset: 1
a(2)=a(3)=1, because the two roots must be (all) the leaves. a(4)=2 (one pattern from the linear tree, one from the star tree). a(6)=10: 1 pattern from n-Hexane. 2 patterns from 2-Methyl-Pentane. 2 patterns from (2,3)-Bimethyl-Butane. 1 pattern from the star graph. 2 patterns from 3-Methyl-Pentane. 2 patterns from (2,2)-Bimethyl-Butane.
Cf.
A303833 (roots need not be leaves),
A055290 (cardinality of candidates).
-
a000081 := [1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847, 1721159, 4688676, 12826228,
35221832, 97055181, 268282855, 743724984, 2067174645, 5759636510, 16083734329, 45007066269, 126186554308, 354426847597,
997171512998, 2809934352700, 7929819784355, 22409533673568, 63411730258053, 179655930440464, 509588049810620, 1447023384581029,
4113254119923150, 11703780079612453, 33333125878283632] ;
g81 := add( op(i,a000081)*x^i,i=1..nops(a000081) ) ;
g81fin := x ;
g := 0 ;
nmax := nops(a000081) ;
for m from 0 to nmax do
mhalf := floor(m/2) ;
ghalf := g81^mhalf*g81fin ;
gcyc := (ghalf^2+subs(x=x^2,ghalf))/2 ;
if type(m,odd) then
gcyc := gcyc*g81 ;
end if;
g := g+gcyc ;
end do:
taylor(g,x=0,nmax) ;
gfun[seriestolist](%) ;
A304222
Triangle T(n,k) read by rows: number of simple connected graphs with n nodes and k endpoints, n >= 0, 0 <= k <= n.
Original entry on oeis.org
1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 3, 1, 1, 1, 0, 11, 5, 3, 1, 1, 0, 61, 29, 14, 5, 2, 1, 0, 507, 224, 86, 25, 8, 2, 1, 0, 7442, 2666, 762, 184, 48, 11, 3, 1, 0, 197772, 50779, 10173, 1890, 374, 72, 16, 3, 1, 0, 9808209, 1653431, 220627, 29252, 4252, 660, 115, 20, 4, 1, 0
Offset: 0
The triangle starts in row n=0 with column 0 <= k <= n as:
1;
1, 0;
0, 0, 1;
1, 0, 1, 0;
3, 1, 1, 1, 0;
11, 5, 3, 1, 1, 0;
61, 29, 14, 5, 2, 1, 0;
507, 224, 86, 25, 8, 2, 1, 0;
7442, 2666, 762, 184, 48, 11, 3, 1, 0;
197772, 50779, 10173, 1890, 374, 72, 16, 3, 1, 0;
-
InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i) )}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
G(n)={sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, (1 - x^p[i])/(1 - (x*y)^p[i]) + O(x*x^(n-k)))); x^k*s/k!)}
T(n)={my(v=InvEulerMT(Vec(G(n)-1))); v[2]=y^2; concat([[1]], vector(#v, n, Vecrev(v[n], n+1))) }
my(A=T(10)); for(n=1, #A, print(A[n])) \\ Andrew Howroyd, Jan 22 2021
Comments