login
Number of trees of diameter 4.
(Formerly M1350 N0518)
15

%I M1350 N0518 #84 Mar 28 2022 07:46:30

%S 0,0,0,0,1,2,5,8,14,21,32,45,65,88,121,161,215,280,367,471,607,771,

%T 980,1232,1551,1933,2410,2983,3690,4536,5574,6811,8317,10110,12276,

%U 14848,17941,21600,25977,31146,37298,44542,53132,63218,75131,89089

%N Number of trees of diameter 4.

%C Number of partitions of n-1 with at least two parts of size 2 or larger. - _Franklin T. Adams-Watters_, Jan 13 2006

%C Also equal to the number of partitions p of n-1 such that max(p)-min(p) > 1. Example: a(7)=5 because we have [5,1],[4,2],[4,1,1],[3,2,1] and [3,1,1,1]. - _Giovanni Resta_, Feb 06 2006

%C Also number of partitions of n-1 with at least two parts that are smaller than the largest part. Example: a(7)=5 because we have [4,1,1],[3,2,1],[3,1,1,1],[2,2,1,1,1] and [2,1,1,1,1]. - _Emeric Deutsch_, May 01 2006

%C Also number of regions of n-1 that do not contain 1 as a part, n >= 2 (cf. A186114, A206437). - _Omar E. Pol_, Dec 01 2011

%C Also rank of the last region of n-1 multiplied by -1, n >= 2 (cf. A194447). - _Omar E. Pol_, Feb 11 2012

%C Also sum of ranks of the regions of n-1 that contain emergent parts, n >= 2 (cf. A182699). For the definition of "regions of n" see A206437. - _Omar E. Pol_, Feb 21 2012

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Christian G. Bower, <a href="/A000094/b000094.txt">Table of n, a(n) for n = 1..500</a>

%H J. Riordan, <a href="http://dx.doi.org/10.1147/rd.45.0473">Enumeration of trees by height and diameter</a>, IBM J. Res. Dev. 4 (1960), 473-478.

%H J. Riordan, <a href="/A007401/a007401_8.pdf">The enumeration of trees by height and diameter</a>, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)

%H Miloslav Znojil, <a href="https://arxiv.org/abs/2008.00479">Perturbation theory near degenerate exceptional points</a>, arXiv:2008.00479 [math-ph], 2020.

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n+1) = A000041(n)-n for n>0. - _John W. Layman_

%F G.f.: x/product(1-x^j,j=1..infinity)-x-x^2/(1-x)^2. - _Emeric Deutsch_, May 01 2006

%F G.f.: sum(sum(x^(i+j+1)/product(1-x^k, k=i..j), i=1..j-2), j=3..infinity). - _Emeric Deutsch_, May 01 2006

%F a(n+1) = Sum_{m=1..n} A083751(m). - _Gregory Gerard Wojnar_, Oct 13 2020

%e From _Gus Wiseman_, Apr 12 2019: (Start)

%e The a(5) = 1 through a(9) = 14 partitions of n-1 with at least two parts of size 2 or larger, or non-hooks, are the following. The Heinz numbers of these partitions are given by A105441.

%e (22) (32) (33) (43) (44)

%e (221) (42) (52) (53)

%e (222) (322) (62)

%e (321) (331) (332)

%e (2211) (421) (422)

%e (2221) (431)

%e (3211) (521)

%e (22111) (2222)

%e (3221)

%e (3311)

%e (4211)

%e (22211)

%e (32111)

%e (221111)

%e The a(5) = 1 through a(9) = 14 partitions of n-1 whose maximum part minus minimum part is at least 2 are the following. The Heinz numbers of these partitions are given by A307516.

%e (31) (41) (42) (52) (53)

%e (311) (51) (61) (62)

%e (321) (331) (71)

%e (411) (421) (422)

%e (3111) (511) (431)

%e (3211) (521)

%e (4111) (611)

%e (31111) (3221)

%e (3311)

%e (4211)

%e (5111)

%e (32111)

%e (41111)

%e (311111)

%e The a(5) = 1 through a(9) = 14 partitions of n-1 with at least two parts that are smaller than the largest part are the following. The Heinz numbers of these partitions are given by A307517.

%e (211) (311) (321) (322) (422)

%e (2111) (411) (421) (431)

%e (2211) (511) (521)

%e (3111) (3211) (611)

%e (21111) (4111) (3221)

%e (22111) (3311)

%e (31111) (4211)

%e (211111) (5111)

%e (22211)

%e (32111)

%e (41111)

%e (221111)

%e (311111)

%e (2111111)

%e (End)

%p g:=x/product(1-x^j,j=1..70)-x-x^2/(1-x)^2: gser:=series(g,x=0,48): seq(coeff(gser,x,n),n=1..46); # _Emeric Deutsch_, May 01 2006

%p A000094 := proc(n)

%p combinat[numbpart](n-1)-n+1 ;

%p end proc: # _R. J. Mathar_, May 17 2016

%t t=Table[PartitionsP[n]-n,{n,0,45}];

%t ReplacePart[t,0,1]

%t (* _Clark Kimberling_, Mar 05 2012 *)

%t CoefficientList[1/QPochhammer[x]-x/(1-x)^2-1+O[x]^50, x] (* _Jean-François Alcover_, Feb 04 2016 *)

%Y Cf. A000041, A206437, A034853, A000147 (diameter 5).

%Y Cf. A006918, A083751, A084835, A105441, A115720, A257990, A307516, A307517, A325164.

%K nonn

%O 1,6

%A _N. J. A. Sloane_

%E More terms from _Franklin T. Adams-Watters_, Jan 13 2006