A036774 -id:A036774 - cp's OEIS frontend

A336309 Triangular array read by rows. T(n,k) is the number of labeled rooted unordered binary trees (as in A036774) with path length exactly k, n >= 1, 0 <= k <= C(n,2).

1, 0, 2, 0, 0, 3, 6, 0, 0, 0, 0, 24, 12, 24, 0, 0, 0, 0, 0, 0, 120, 120, 120, 60, 120, 0, 0, 0, 0, 0, 0, 0, 0, 360, 1440, 360, 1440, 720, 720, 360, 720, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 630, 7560, 10080, 10080, 7560, 12600, 7560, 10080, 5040, 5040, 2520, 5040

Offset: 1

Geoffrey Critzer, Jul 17 2020

The path length of a tree is the distance from the root to a node summed over all nodes in the tree.

			  1,
  0, 2,
  0, 0, 3, 6,
  0, 0, 0, 0, 24, 12,  24,
  0, 0, 0, 0,  0,  0, 120, 120, 120,   60,   120,
  0, 0, 0, 0,  0,  0,   0,   0, 360, 1440,   360, 1440, 720, 720, 360, 720

Cf. A036774.

nn = 6; f[z_, u_] := Sum[Sum[a[n, k] u^k z^n/n!, {k, 0, Binomial[n, 2]}], {n, 1,
   nn}]; sol =SolveAlways[Series[0 == f[z, u] - z (1 + f[u z, u] + f[u z, u]^2/2!), {z, 0, nn}], {z, u}];Level[Table[Table[a[n, k], {k, 0, Binomial[n, 2]}], {n, 1, nn}] /. sol, {2}] // Grid

E.g.f. satisfies A(x,y) = x + x*A(y*x,y) + x*A(y*x,y)^2/2.

A071356 Expansion of (1 - 2x - sqrt(1 - 4x - 4x^2))/(4x^2).

Original entry on oeis.org

1, 2, 6, 20, 72, 272, 1064, 4272, 17504, 72896, 307648, 1312896, 5655808, 24562176, 107419264, 472675072, 2091206144, 9296612352, 41507566592, 186045061120, 836830457856, 3776131489792, 17089399689216, 77548125675520, 352766964908032

Offset: 0

N. J. A. Sloane, Jun 12 2002

nonn

Number of underdiagonal lattice paths from (0,0) to the line x=n, using only steps R=(1,0), V=(0,1) and D=(1,2). Also number of Motzkin paths of length n in which both the "up" and the "level" steps come in two colors. E.g., a(2)=6 because we have RR, RVR, RRV, RD, RVRV and RRVV. - Emeric Deutsch, Dec 21 2003
Inverse binomial transform of little Schroeder numbers 1,3,11,... (A001003 with first term deleted). - David Callan, Feb 07 2004
a(n) is the number of planar trees satisfying: 1) Every internal node has at least two children, 2) Among the children of a node, only the leftmost and the rightmost children can be leaves, 3) The tree has n+1 leaves. For instance, a(3)=6. - Marcelo Aguiar (maguiar(AT)math.tamu.edu), Oct 14 2005
Hankel transform is A006125(n+1)=2^C(n+1,2). - Paul Barry, Jan 08 2008
Equals binomial transform of A025235: (1, 1, 3, 7, 21, 61, 191, ...). - Gary W. Adamson, Sep 03 2010
Conjecturally, the number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j) <= e(k). [Martinez and Savage, 2.19] - Eric M. Schmidt, Jul 17 2017
Let s denote West's stack-sorting map, and let Av_n(tau_1, ..., tau_r) denote the set of permutations of [n] that avoid the patterns tau_1, ..., tau_r. It is conjectured that a(n) = |s^{-1}(Av_{n+1}(132, 231))| = |s^{-1}(Av_{n+1}(132, 312))| = |s^{-1}(Av_{n+1}(231, 312))|. Only the last of these equalities is known. - Colin Defant, Sep 16 2018

			a(3) = 20 = sum of top row terms in M^3 = (9 + 7 + 3 + 1).

Fung Lam, Table of n, a(n) for n = 0..1465
Marcelo Aguiar and Walter Moreira, Combinatorics of the free Baxter algebra, arXiv:math/0510169 [math.CO], 2005-2007, see Corollary 3.3.iii.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Miklos Bona, Stack-sorting preimages and 0-1-trees, arXiv:2505.18295 [math.CO], 2025. See p. 3.
Vuong Bui, Bounding Klarner's constant from above using a simple recurrence, arXiv:2412.20143 [math.CO], 2024.
Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
Colin Defant, Enumeration of Stack-Sorting Preimages via a Decomposition Lemma, arXiv:1904.02829 [math.CO], 2019.
Serkan Demiriz, Adem Şahin, and Sezer Erdem, Some topological and geometric properties of novel generalized Motzkin sequence spaces, Rendiconti Circ. Mat. Palermo Ser. 2 (2025) Vol. 74, No. 136. See p. 4.
Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
Li Guo and Yunnan Li, Braided dendriform and tridendriform algebras and braided Hopf algebras of planar trees, arXiv:1906.06454 [math.QA], 2019.
Bin Han, The gamma-positive coefficients arising in segmented permutations, Discrete Math., 344 (2012), #112336. See p. 7.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Chetak Hossain, Quotients Derived from Posets in Algebraic and Topological Combinatorics, Ph. D. Dissertation, North Carolina State University (2019).
Germain Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973), p. 32-33 (same sequence but with offset 1).
Germain Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Donatella Merlini, Douglas G. Rogers, Renzo Sprugnoli, and M. Cecilia Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.
Louis W. Shapiro and Carol J. Wang, A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height, JIS 12 (2009) 09.3.2.

A036774(n) = a(n-1) * n! / 2^(n-1).
Row sums of A071943.
Cf. A000108, A025235.

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!((1 - 2*x - Sqrt(1 - 4*x - 4*x^2))/(4*x^2))); // Vincenzo Librandi, Jan 21 2020

CoefficientList[Series[(1-2*x-Sqrt[1-4*x-4*x^2])/(4*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 24 2013 *)
a[n_] := 2^n Hypergeometric2F1[(1-n)/2, -n/2, 2, 2];
Table[a[n], {n, 0, 24}] (* Peter Luschny, May 30 2021 *)

a(n)=if(n<0,0,n++; polcoeff(serreverse(x/(1+2*x+2*x^2)+x*O(x^n)),n))

{a(n)= if(n<1, n==0, polcoeff( 2/(1 -2*x +sqrt(1 -4*x -4*x^2 +x*O(x^n))), n))}

{a(n)= local(A); if(n<0, 0, A= x*O(x^n); n!*simplify(polcoeff( exp(2*x +A)* besseli(1, 2*x* quadgen(8) +A), n)))} /* Michael Somos, Mar 31 2007 */

def A071356_list(n):  # n>=1
    T = [0]*(n+1); R = [1]
    for m in (1..n-1):
        a,b,c = 1,0,0
        for k in range(m,-1,-1):
            r = a + 2*(b + c)
            if k < m : T[k+2] = u;
            a,b,c = T[k-1],a,b
            u = r
        T[1] = u; R.append(u)
    return R
A071356_list(25)  # Peter Luschny, Nov 01 2012

G.f. A(x) satisfies 2x^2*A(x)^2+(2x-1)*A(x)+1=0 and A(x)=1/(1-2x-2x^2/A(x)). - Michael Somos, Sep 06 2003
a(n) = Sum_{k=0..floor(n/2)} C(n, 2k)C(k)2^(n-2k)*2^k. - Paul Barry, May 18 2005
G.f.: (1 - 2*x - sqrt(1 - 4*x - 4*x^2) )/(4*x^2) = 2/(1 - 2*x +sqrt(1 - 4*x - 4*x^2)).
Moment representation is a(n) = (1/(4*Pi))*int(x^n*sqrt(4-4x-x^2), x, -2*sqrt(2)-2, 2*sqrt(2)-2). - Paul Barry, Jan 08 2008
G.f.: 1/(1-2x-2x^2/(1-2x-2x^2/(1-2x-2x^2/(1-2x-2x^2/(1-2x-2x^2/.... (continued fraction). - Paul Barry, Dec 06 2008
From Gary W. Adamson, Jul 22 2011: (Start)
a(n) = sum of top row terms of M^n, M = an infinite square production matrix as follows:
  1, 1, 0, 0, 0, 0, ...
  2, 1, 1, 0, 0, 0, ...
  2, 2, 1, 1, 0, 0, ...
  2, 2, 2, 1, 1, 0, ...
  2, 2, 2, 2, 1, 1, ...
  2, 2, 2, 2, 2, 1, ... (End)
E.g.f.: a(n) = n!* [x^n] exp(2*x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - Peter Luschny, Aug 25 2012
D-finite with recurrence: (n+2)*a(n) +2*(-2*n-1)*a(n-1) +4*(-n+1)*a(n-2)=0. - R. J. Mathar, Dec 02 2012 (Formula verified and used for computations. - Fung Lam, Feb 24 2014)
a(n) ~ 2^(n - 1/4) * (1+sqrt(2))^(n + 3/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 24 2013, simplified Jan 26 2019
a(n) = A179190(n+2)/4. - R. J. Mathar, Jan 20 2020
a(n) = 2^n * hypergeom((1 - n)/2, -n/2, 2, 2). - Peter Luschny, May 30 2021
a(n) = (-2*î)^(n+2) * (Legendre_P(n+2, i) - Legendre_P(n, i))/(4*(2*n + 3)). - Peter Bala, May 06 2024
From Emanuele Munarini, Jun 13 2024: (Start)
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*binomial(n-k, k)*2^(n-k)/(k+1).
a(n) = Sum_{k=0..floor((n+2)/3)} binomial(n-2k+2, 2k)*Catalan(n-2k+1).
a(n) = Sum_{k=0..floor((n+2)/4)} binomial(n-2k+1, 2k+1)*Catalan(n-2k). (End)

A063895 Start with x, xy; then concatenate each word in turn with all preceding words, getting x xy xxy xxxy xyxxy xxxxy xyxxxy xxyxxxy ...; sequence gives number of words of length n. Also binary trees by degree: x (x,y) (x,(x,y)) (x,(x,(x,y))) ((x,y),(x,(x,y)))...

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 11, 22, 43, 88, 179, 372, 774, 1631, 3448, 7347, 15713, 33791, 72923, 158021, 343495, 749102, 1638103, 3591724, 7893802, 17387931, 38379200, 84875596, 188036830, 417284181, 927469845, 2064465341, 4601670625, 10270463565, 22950838755

Offset: 1

Claude Lenormand (claude.lenormand(AT)free.fr), Aug 29 2001

Also binary rooted identity trees (those with no symmetries, cf. A004111).
From Gus Wiseman, May 04 2021: (Start)
Also the number of unlabeled binary rooted semi-identity trees with 2*n - 1 nodes. In a semi-identity tree, only the non-leaf branches directly under any given vertex are required to be distinct. Alternatively, an unlabeled rooted tree is a semi-identity tree iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees. For example, the a(3) = 1 through a(6) = 6 trees are:
  (o(oo))  (o(o(oo)))  ((oo)(o(oo)))  ((oo)(o(o(oo))))  ((o(oo))(o(o(oo))))
                       (o(o(o(oo))))  (o((oo)(o(oo))))  ((oo)((oo)(o(oo))))
                                      (o(o(o(o(oo)))))  ((oo)(o(o(o(oo)))))
                                                        (o((oo)(o(o(oo)))))
                                                        (o(o((oo)(o(oo)))))
                                                        (o(o(o(o(o(oo))))))
The a(8) = 11 trees with 15 nodes:
  ((o(oo))((oo)(o(oo))))
  ((o(oo))(o(o(o(oo)))))
  ((oo)((oo)(o(o(oo)))))
  ((oo)(o((oo)(o(oo)))))
  ((oo)(o(o(o(o(oo))))))
  (o((o(oo))(o(o(oo)))))
  (o((oo)((oo)(o(oo)))))
  (o((oo)(o(o(o(oo))))))
  (o(o((oo)(o(o(oo))))))
  (o(o(o((oo)(o(oo))))))
  (o(o(o(o(o(o(oo)))))))
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for sequences related to rooted trees

Cf. A063894, A036774.
The non-semi-identity version is 2*A001190(n)-1, ranked by A111299.
Semi-binary trees are also counted by A001190, but ranked by A292050.
The not necessarily binary version is A306200, ranked A306202.
The Matula-Goebel numbers of these trees are A339193.
The plane tree version is A343663.
A000081 counts unlabeled rooted trees with n nodes.
A004111 counts identity trees, ranked by A276625.
A306201 counts balanced semi-identity trees, ranked by A306203.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
Cf. A001678, A331934, A331963, A331964.

a:= proc(n) option remember; `if`(n<3, n*(3-n)/2, add(a(i)*a(n-i),
      i=1..(n-1)/2)+`if`(irem(n, 2, 'r')=0, (p->(p-1)*p/2)(a(r)), 0))
    end:
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 02 2013

a[n_] := a[n] = If[n<3, n*(3-n)/2, Sum[a[i]*a[n-i], {i, 1, (n-1)/2}]+If[{q, r} = QuotientRemainder[n, 2]; r == 0, (a[q]-1)*a[q]/2, 0]]; Table[a[n], {n, 1, 36}] (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)
ursiq[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursiq/@ptn]],#=={}||#=={{},{}}||Length[#]==2&&(UnsameQ@@DeleteCases[#,{}])&],{ptn,IntegerPartitions[n-1]}];Table[Length[ursiq[n]],{n,1,15,2}] (* Gus Wiseman, May 04 2021 *)

{a(n)=local(A, m); if(n<1, 0, m=1; A=O(x); while( m<=n, m*=2; A=1-sqrt(1-2*x-2*x^2+subst(A, x, x^2))); polcoeff(A, n))}

a(n) = (sum a(i)*a(j), i+j=n, i2. a(1)=a(2)=1.
G.f. A(x) = 1-sqrt(1-2x-2x^2+A(x^2)) satisfies x+x^2-A(x)+(A(x)^2-A(x^2))/2=0, A(0)=0. - Michael Somos, Sep 06 2003
a(n) ~ c * d^n / n^(3/2), where d = 2.33141659246516873904600076533362924695..., c = 0.2873051160895040470174351963... . - Vaclav Kotesovec, Sep 11 2014

Additional comments and g.f. from Christian G. Bower, Nov 29 2001

A325201 Square array whose entry A(n,k) is the number of labeled rooted trees on a set of size n where each node has at most k neighbors that are further away from the root than the node itself, for n >= 0, k >= 0, read by descending antidiagonals.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 6, 0, 0, 1, 2, 9, 24, 0, 0, 1, 2, 9, 60, 120, 0, 0, 1, 2, 9, 64, 540, 720, 0, 0, 1, 2, 9, 64, 620, 6120, 5040, 0, 0, 1, 2, 9, 64, 625, 7620, 83790, 40320, 0, 0, 1, 2, 9, 64, 625, 7770, 113610, 1345680, 362880, 0, 0, 1, 2, 9, 64, 625, 7776, 117390, 1992480, 24811920, 3628800, 0

Offset: 1

Benjamin Otto, Apr 08 2019

A preimage constraint on a function is a set of nonnegative integers such that the size of the inverse image of any element is one of the values in that set. View a labeled rooted tree as an endofunction on the set {1,2,...,n} by sending every non-root node to its neighbor that is closer to the root and sending the root to itself.

Thus, A(n,k) is the number of endofunctions on a set of size n with exactly one cyclic point and such that each preimage has at most k entries.

			Array begins:
           0           0           0           0           0 ...
           0           1           1           1           1 ...
           0           2           2           2           2 ...
           0           6           9           9           9 ...
           0          24          60          64          64 ...
           0         120         540         620         625 ...
           0         720        6120        7620        7770 ...
           0        5040       83790      113610      117390 ...
           0       40320     1345680     1992480     2088520 ...
           0      362880    24811920    40194000    42771960 ...
           0     3628800   516650400   916927200   991090800 ...
           0    39916800 11992503600 23341071600 25635767850 ...
         ...

B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.

Column 0: A000004.
Column 1 is A000142, except at n=0 term.
Columns 2-9: A036774, A036775, A036776, A036777, A325205, A325206, A325207, A325208.
A(n,n) gives A152917.
Similar array for arbitrary endofunctions (without limitation on the number of cyclic points) with the same preimage condition {i>=0 | i<=k}: A306800.

e[k_][x_] := Sum[x^j/j!, {j, 0, k}];
A[0, ] = A[, 0] = 0; A[n_, k_] := (n-1)! Coefficient[e[k][x]^n, x, n-1];
Table[A[n-k, k], {n, 0, 11}, {k, n, 0, -1}] (* Jean-François Alcover, Jul 06 2019 *)

# print first num_entries entries in column k
import math, sympy; x=sympy.symbols('x')
k=5; num_entries = 64
P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [0,1]; curr_pow = eP
for term in range(1, num_entries-1):
    curr_pow=(curr_pow*eP).expand()
    r.append(curr_pow.coeff(x**term)*math.factorial(term))
print(r)

A(n,k) = (n-1)! * [x^(n-1)] e_k(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. When k>1, the link above yields explicit constants c_k, r_k so that the columns are asymptotically c_k * n^(-3/2) * r_k^-n. Stirling's approximation gives column k=1, and column k=0 is 0.

A036775 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 3 neighbors that are further away from the root than the node itself.

Original entry on oeis.org

0, 1, 2, 9, 64, 620, 7620, 113610, 1992480, 40194000, 916927200, 23341071600, 655922836800, 20169411662400, 673645440468000, 24285190867938000, 939899116892736000, 38870133445791648000, 1710655202853140544000, 79826043011286892320000, 3936948118406837614080000, 204621522793150838094720000

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of unordered rooted labeled trees such that each node has outdegree <= 3. - Geoffrey Critzer, Mar 22 2013
A preimage constraint on a function is a set of nonnegative integers such that the size of the inverse image of any element is one of the values in that set. View a labeled rooted tree as an endofunction on the set {1,2,...,n} by sending every non-root node to its neighbor that is closer to the root and sending the root to itself. Thus a(n) is the number of endofunctions on a set of size n with exactly one cyclic point and such that each preimage has at most 3 entries. - Benjamin Otto, Apr 08 2019
From pp. 3-4 in Takacs (1993), we see that n is the number of nodes in a labeled rooted tree such that each node has outdegree <= 3, and (as noted above by G. Critzer), a(n) is the number of such unordered rooted labeled trees (with n nodes). - Petros Hadjicostas, Jun 09 2019

B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 3.
Index entries for sequences related to rooted trees

Cf. A036774, A036776, A036777.

Column k=3 of A325201; see that entry for sequences related to other preimage constraints constructions. - Benjamin Otto, Apr 08 2019

nn=18;f[x_]:=Sum[a[n]x^n/n!,{n,0,nn}];s=SolveAlways[0==Series[f[x]-x(1+f[x]+f[x]^2/2+f[x]^3/3!),{x,0,nn}],x];Table[a[n],{n,0,nn}]/.s (* Geoffrey Critzer, Mar 22 2013 *)
Table[3*n!*Sum[Binomial[n+1,j]*Sum[Binomial[j,i-j]*2^(4*j-2*n-i-2)*6^(n+i+1)*Binomial[n-j+1,3*j-n-i-2],{i,j,n+j}]/6^(3*j),{j,0,n+1}],{n,0,20}] (* Vaclav Kotesovec after Vladimir Kruchinin, Jan 08 2014 *)
f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
a[n_] := If[n == 1, 1, Derivative[n - 1][f[3, n]][0]];
a /@ Range[0, 21] (* Jean-François Alcover, Apr 20 2020, after Petros Hadjicostas in A036777 *)

a(n):=3*n!*sum((binomial(n+1,j)*sum(binomial(j,i-j)*2^(4*j-2*n-i-2)*6^(n+i+1)*binomial(n-j+1,3*j-n-i-2),i,j,n+j))/6^(3*j),j,0,(n+1)); /* Vladimir Kruchinin, Nov 21 2011 */

# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=3; num_entries = 64
P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [0,1]; curr_pow = eP
for term in range(1,num_entries-1):
   curr_pow=(curr_pow*eP).expand()
   r.append(curr_pow.coeff(x**term)*math.factorial(term))
print(r) # Benjamin Otto, Apr 08 2019

E.g.f.: (for shifted sequence a(0)=0, a(1)=1, ...) A(x) satisfies A(x) = 1 + x*A(x) + (1/2)*x^2*A(x)^2 + (1/6)*x^3*A(x)^3.
a(n) = 3*n!*Sum_{j=0..n+1} binomial(n+1, j)*Sum_{i=j..n+j} binomial(j, i-j)*2^(4*j-2*n-i-2)*6^(n+i+1)*binomial(n-j+1, 3*j-n-i-2)/6^(3*j). - Vladimir Kruchinin, Nov 21 2011
a(n) ~ sqrt(s/(1+r*s)) * n^n / (r^(n+1) * exp(n)), where r = 0.37589405207806352... is the root of the equation -8 + 21*r + 2*r^3 = 0 and s = 2.86947048655283754... is the root of the equation -12 + 36*s - 57*s^2 + 16*s^3 = 0. - Vaclav Kotesovec, Jan 08 2014
a(n) = (n-1)! * [x^(n-1)] e_3(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The Otto link above yields explicit constants c_k, r_k so that the columns are asymptotically c_3 * n^(-3/2) * r_3^-n. - Benjamin Otto, Apr 08 2019

Edited by N. J. A. Sloane, Jul 13 2019 using data from a duplicate of this entry that was submitted by Benjamin Otto, Apr 08 2019

A036776 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 4 neighbors that are further away from the root than the node itself.

Original entry on oeis.org

0, 1, 2, 9, 64, 625, 7770, 117390, 2088520, 42771960, 991090800, 25635767850, 732235165200, 22890759391500, 777398836414200, 28501053507927000, 1121908690738836000, 47194400446765572000, 2112854517933207048000, 100302903229033765260000, 5032863920347902999360000

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of unordered rooted labeled trees such that each node has outdegree <= 4. - Geoffrey Critzer, Mar 23 2013

From pp. 3-4 in Takacs (1993), we see that n is the number of nodes in a labeled rooted tree such that each node has outdegree <= 3, and (as noted above by G. Critzer), a(n) is the number of such unordered rooted labeled trees (with n nodes). Apparently, the author of this sequence and other contributors exclude the node at the root, and thus the offset here is 0 (rather than 1). - Petros Hadjicostas, Jun 09 2019

B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 4.
Index entries for sequences related to rooted trees

Cf. A036774, A036775, A036777. Column k=4 of A325201; see that entry for sequences related to other preimage constraints constructions.

nn=18;f[x_]:=Sum[a[n]x^n/n!,{n,0,nn}];s=SolveAlways[0==Series[f[x]-x(1+f[x]+f[x]^2/2+f[x]^3/3!+f[x]^4/4!),{x,0,nn}],x];Table[a[n],{n,0,nn}]/.s  (* Geoffrey Critzer, Mar 23 2013 *)
f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
a[n_] := If[n == 1, 1, Derivative[n-1][f[4, n]][0]];
a /@ Range[0, 20] (* Jean-François Alcover, Apr 20 2020, after Petros Hadjicostas in A036777 *)

a(n):=(n!*sum(binomial(n+1,r)*sum(binomial(r,m)*sum(binomial(j,-r+n-m-j)*2^(2*r-2*n+m+2*j)*binomial(m,j)*(3)^(-j),j,0,m),m,0,r),r,0,n+1)); /* Vladimir Kruchinin, Nov 22 2011 */

# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=4; num_entries = 64
P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [0,1]; curr_pow = eP
for term in range(1,num_entries-1):
   curr_pow=(curr_pow*eP).expand()
   r.append(curr_pow.coeff(x**term)*math.factorial(term))
print(r) # Benjamin Otto, Apr 11 2019

From Vladimir Kruchinin, Nov 22 2011: (Start)
E.g.f. A(x) satisfies: A(x) = 1 + x*A(x) + (1/2)*x^2*A(x)^2 + (1/6)*x^3*A(x)^3 + (1/24)*A(x)^4.
a(n) = n!*Sum_{r=0..n+1} binomial(n+1,r)*Sum_{m=0..r} binomial(r,m)*Sum_{j=0..m} binomial(j,-r+n-m-j)*2^(2*r-2*n+m+2*j)*binomial(m,j)*3^(-j). (End)
a(n) = (n-1)! * [x^(n-1)] e_4(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The Otto link above yields explicit constants c_k, r_k so that the columns are asymptotically c_4 * n^(-3/2) * r_4^-n. - Benjamin Otto, Apr 11 2019

Edited by N. J. A. Sloane, Jul 13 2019 using data from a duplicate of this entry that was submitted by Benjamin Otto, Apr 08 2019

A036777 Number of labeled rooted trees with a degree constraint (described in the comments below).

Original entry on oeis.org

0, 1, 2, 9, 64, 625, 7776, 117642, 2096752, 43030008, 999357660, 25912953990, 742054808880, 23259517076796, 792084372215136, 29120668067951460, 1149560690861943360, 48497162427675081120, 2177517061087611122880, 103677374170183264555104, 5217647895920644618674240, 276740347650892414464815640, 15429120173129978156923361280, 902095425530332280621924069520

Offset: 0

N. J. A. Sloane

nonn

From Petros Hadjicostas, Jun 09 2019: (Start)
Quoting from p. 3 of Takacs (1993): "Denote by S_n* the set of all rooted trees with n labeled vertices. ... let us define R as a fixed set of nonnegative integers which always contains 0. Denote by S_n*(R) the subset of S_n* which contains all the trees in S_n* in which the degree of the root is in R and, if j is the degree of any other vertex of a tree, then j-1 \in R."
Quoting from p. 4 of Takacs (1993): "Theorem 2: The number of trees in S_n*(R) is |S_n^*(R)| = (n - 1)! Coeff. of x^(n-1) in ( Sum_{i \in R} x^i/i! )^n."
When R = {0,1,...,r}, the quantity |S_n*(R)|/n^(n-1) has a probabilistic interpretation related to the generalized birthday problem. Let us "put balls at random one by one in n boxes until one of the boxes contains r + 1 balls" (p. 4 in Takacs). We assume that every box has the same probability (i.e., 1/n). Then |S_n*(R)|/n^(n-1) is the probability that at least n balls are needed until the above process stops (i.e., until at least one of the n boxes contains r + 1 balls).
(End)

			Here a(n)/n^(n-1) is the probability that at least n balls are needed until one of the n boxes contains r + 1 = 6 balls (for the first time) when the n boxes are equally likely and we randomly distribute balls in the boxes (one by one) until one box gets r + 1 = 6 balls for the first time.  Clearly, a(n) = n^(n-1) for n = 1..6 for obvious reasons! But a(7) = 117642 < 117649 = 7^6. - _Petros Hadjicostas_, Jun 09 2019

B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 5.
Index entries for sequences related to rooted trees

Cf. A036774 (r = 2), A036775 (r = 3), A036776 (r = 4).

# This is a crude Maple program based on Eq. (14), p. 4, in Takacs (1993). It calculates a(n) for n >= 2.
ff := proc(r, n) simplify(subs(x = 0, diff(sum(x^k/k!, k = 0 .. r)^n, x$(n - 1)))); end;
seq(ff(5, i), i = 2 .. 40); # Petros Hadjicostas, Jun 09 2019

f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
a[n_] := If[n == 1, 1, Derivative[n-1][f[5, n]][0]];
a /@ Range[0, 23] (* Jean-François Alcover, Apr 20 2020, after Petros Hadjicostas *)

In Theorem 2 from p. 4 in Takacs (1993)--see the COMMENTS above--let R = {0,1,...,r} with r = 5. - Petros Hadjicostas, Jun 09 2019

More terms, name edited, and offset changed by Petros Hadjicostas, Jun 09 2019

A089975 Array read by ascending antidiagonals: T(n,k) is the number of n-letter words from a k-letter alphabet such that no letter appears more than twice.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 4, 3, 1, 0, 0, 6, 9, 4, 1, 0, 0, 6, 24, 16, 5, 1, 0, 0, 0, 54, 60, 25, 6, 1, 0, 0, 0, 90, 204, 120, 36, 7, 1, 0, 0, 0, 90, 600, 540, 210, 49, 8, 1, 0, 0, 0, 0, 1440, 2220, 1170, 336, 64, 9, 1, 0, 0, 0, 0, 2520, 8100, 6120, 2226, 504, 81, 10, 1

Offset: 0

Paul Boddington, Nov 17 2003

			Array begins:
  1, 1, 1,  1,    1,     1,      1,      1,       1,       1,       1, ...
  0, 1, 2,  3,    4,     5,      6,      7,       8,       9,      10, ...
  0, 1, 4,  9,   16,    25,     36,     49,      64,      81,     100, ...
  0, 0, 6, 24,   60,   120,    210,    336,     504,     720,     990, ...
  0, 0, 6, 54,  204,   540,   1170,   2226,    3864,    6264,    9630, ...
  0, 0, 0, 90,  600,  2220,   6120,  14070,   28560,   52920,   91440, ...
  0, 0, 0, 90, 1440,  8100,  29520,  83790,  201600,  430920,  842400, ...
  0, 0, 0,  0, 2520, 25200, 128520, 463680, 1345680, 3356640, 7484400, ...
  ... - _Robert FERREOL_, Nov 03 2017

Dennis Walsh, Width-Restricted Finite Functions

T(1, k) = A001477(k); T(2, k) = A000290(k); T(3, k) = A007531(k); T(n, n) = A012244(n); T(n, n+1) = A036774(n); T(n, n+2) = A003692(n+1); T(2*n, n) = A000680(n); sum(T(n, k), n=0..2*k) = A003011(k); sum(T(r, n-r), r=0..n) = A089976(n).

See A141765 for an irregular triangle version : T(n,k)=A141765(k,n) for n <= 2k.

T:=(n,k)->add(n!*k!/(n-2*i)!/i!/(k-n+i)!/2^i,i=max(0,n-k)..n/2):
or
T:=proc(n,k) option remember :if n=0 then 1 elif n=1 then k elif k=0 then 0 else T(n, k-1)+n*T(n-1, k-1)+binomial(n,2)*T(n-2, k-1) fi end:
or
T:=(n,k)-> n!*coeff((1 + x + x^2/2)^k, x,n):
seq(seq(T(n-k,k),k=0..n),n=0..20);
# Robert FERREOL, Nov 07 2017

T[n_, k_] := Sum[n!*k!/(2^i*(n - 2 i)!*(k - n + i)!*i!), {i, Max[0, n - k], Floor[n/2]}];
Table[T[n-k , k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 05 2017, after Robert FERREOL *)

from math import factorial as f
def T(n,k):
    return sum(f(n)*f(k)//f(n-2*i)//f(i)//f(k-n+i)//2**i for i in range(max(0,n-k),n//2+1))
[T(n-k,k) for n in range(21) for k in range(n+1)]
# Robert FERREOL, Oct 17 2017

T(n, k) = T(n, k-1) + n*T(n-1, k-1) + binomial(n, 2)*T(n-2, k-1) for n >= 2 and k >= 1.
T(n, k) = Sum_{i=max(0,n-k)..floor(n/2)} n!*k!/(2^i*(n-2*i)!*(k-n+i)!*i!). - Robert FERREOL, Oct 30 2017
T(n,k) = (-1)^n*n!*2^(-n/2)*GegenbauerC(n, -k, 1/sqrt(2)) for k >= n. - Robert Israel, Nov 08 2017
G.f.: Sum({n>=0} T(n,k)x^n)=n!(1 + x + x^2/2)^k. See Walsh link. - Robert FERREOL, Nov 14 2017

A182037 Expansion of 1 - (1 - 2*x - x^2)^(1/2).

Original entry on oeis.org

0, 1, 2, 6, 36, 300, 3240, 42840, 670320, 12111120, 248119200, 5683154400, 143910043200, 3991909521600, 120376874217600, 3920816403504000, 137177166174048000, 5130755025780384000, 204295093225134912000, 8627985710304472512000, 385222786392984059520000

Offset: 0

Geoffrey Critzer, Apr 07 2012

nonn

a(n) is the number of rooted labeled trees such that (i) the root vertex has at most one child and (ii) all other vertices have at most two children.
a(n) is the number of planar binary trees with leaves labeled by {1, ...,n} considered modulo swapping of the planar order at all the internal nodes except for the highest ones. - Bérénice Delcroix-Oger, Jun 25 2025
F(x) = -e.g.f. (below) = -1 + (2-(1+x)^2)^(1/2) is self-inverse about x=0, i.e., its own compositional inverse, so the negative of the integer sequence remains unchanged by Lagrange inversion. This results from viewing y=F(x) as describing the arc, in the second and fourth quadrant, of a circle centered at (-1,-1) with radius sqrt(2). - Tom Copeland, Oct 05 2012

Michael De Vlieger, Table of n, a(n) for n = 0..394
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
Bérénice Delcroix-Oger and Clément Dupont, Lie-operads and operadic modules from poset cohomology, arXiv:2505.06094 [math.CO], 2025. See p. 23.

nn = 15; a = (1 - x - (1 - 2 x - x^2)^(1/2))/x; Range[0, nn]! * CoefficientList[Series[x + a x, {x, 0, nn}], x]

E.g.f.: 1 - (1-2*x-x^2)^(1/2).
E.g.f.: x*(1+A(x)) where A(x) is the e.g.f. of A036774.
a(n) ~ sqrt(2-sqrt(2)) * n^(n-1) * (1+sqrt(2))^n / exp(n). - Vaclav Kotesovec, Sep 25 2013
From Benedict W. J. Irwin, May 25 2016: (Start)
Let y(0)=1, y(1)=-1, and (1-n)*y(n) - (2n+1)*y(n+1) + (n+2)*y(n+2) = 0,
a(n) = -n!y(n), n > 0. (End)
a(n) + (-2*n+3)*a(n-1) - (n-1)*(n-3)*a(n-2) = 0. - R. J. Mathar, Jun 08 2016
a(1)=1, a(2)=2 and a(n) = (1/2) * Sum_{k=1..n-1} C(n,k)*a(k)*a(n-k) for n>= 3. - Bérénice Delcroix-Oger, Jun 25 2025

A141765 Triangle T, read by rows, such that row n equals column 0 of matrix power M^n where M is a triangular matrix defined by M(k+m,k) = binomial(k+m,k) for m=0..2 and zeros elsewhere. Width-2-restricted finite functions.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 4, 6, 6, 1, 3, 9, 24, 54, 90, 90, 1, 4, 16, 60, 204, 600, 1440, 2520, 2520, 1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400, 1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400, 1, 7, 49, 336, 2226

Offset: 0

Paul D. Hanna, Jul 28 2008

T(k,n) is the number of distinct ways in which n labeled objects can be distributed in k labeled urns allowing at most 2 objects to fall in each urn. - N-E. Fahssi, Apr 22 2009

T(k,n) is the number of functions f:[n]->[k] such that the preimage set under f of any element of [k] has size 2 or less. - Dennis P. Walsh, Feb 15 2011

			This triangle T begins:
1;
1, 1, 1;
1, 2, 4, 6, 6;
1, 3, 9, 24, 54, 90, 90;
1, 4, 16, 60, 204, 600, 1440, 2520, 2520;
1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400;
1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400;
1, 7, 49, 336, 2226, 14070, 83790, 463680, 2346120, 10636920, 42071400, 139708800, 366735600, 681080400, 681080400,
1, 8, 64, 504, 3864, 28560, 201600, 1345680, 8401680, 48444480, 254016000, 1187524800, 4819953600, 16345929600, 43589145600, 81729648000, 81729648000,
1, 9, 81, 720, 6264, 52920, 430920, 3356640, 24811920, 172504080, 1116536400, 6646147200, 35835307200, 171632260800, 711047937600, 2451889440000, 6620101488000, 12504636144000, 12504636144000,
...
Rows 6 and 8 appear in Park (2015). - _N. J. A. Sloane_, Jan 31 2016
Let M be the triangular matrix that begins:
  1;
  1,  1;
  1,  2,  1;
  0,  3,  3,  1;
  0,  0,  6,  4,  1;
  0,  0,  0, 10,  5,  1; ...
where M(k+m,k) = C(k+m,k) for m=0,1,2 and zeros elsewhere.
Illustrate that row n of T = column 0 of M^n for n >= 0 as follows.
The matrix square M^2 begins:
   1;
   2,  1;
   4,  4,  1;
   6, 12,  6,  1;
   6, 24, 24,  8,  1;
   0, 30, 60, 40, 10,  1; ...
with column 0 of M^2 forming row 2 of T.
The matrix cube M^3 begins:
   1;
   3,   1;
   9,   6,   1;
  24,  27,   9,   1;
  54,  96,  54,  12,   1;
  90, 270, 240,  90,  15,   1;
  90, 540, 810, 480, 135,  18,   1; ...
with column 0 of M^3 forming row 3 of T.
T(2,3)=6 because there are 6 ways to lodge 3 distinguishable balls, labeled by numbers 1,2 and 3, in 2 distinguishable boxes, each of which can hold at most 2 balls. - _N-E. Fahssi_, Apr 22 2009
T(5,8)=63000 because there are 63000 ways to assign 8 students to a dorm room when there are 5 different two-bed dorm rooms that are available. (See link for details of the count.) - _Dennis P. Walsh_, Feb 15 2011

Dennis Walsh, Width-restricted finite functions
Donghwi Park, Space-state complexity of Korean chess and Chinese chess, arXiv preprint arXiv:1507.06401, 2015

Cf. A003011 (row sums), A000680 (right border); diagonals: A012244, A036774, A003692.

seq(seq(n!*sum(binomial(k,j)*binomial(j,n-j)*2^(j-n),j=ceil(n/2)..k),n=0..2*k),k=1..10); # Dennis P. Walsh, Feb 15 2011

T[k_, n_] := If[n == 0, 1, n! Coefficient[(1 + x + x^2/2)^k, x^n]]; TableForm[Table[T[k, n], {k, 0, 10}, {n, 0, 2 k}]] (* N-E. Fahssi, Apr 22 2009 *)

{T(n,k)=local(M=matrix(n+1,n+1,n,k,if(n>=k,if(n-k<=2,binomial(n-1,k-1))))); if(k>2*n,0,(M^n)[k+1,1])}

T(k,n) = n!*Sum_{i=ceiling(n/2)..k} binomial(k,i)*binomial(i,n-i)*2^(i-n). - Dennis P. Walsh, Feb 15 2011
T(n,2*n) = (2n)!/2^n; thus the rightmost border of T equals A000680.
Main diagonal (central terms) equals A012244.
Other diagonals include A036774 and A003692.
Row sums of triangle T equals A003011, the number of permutations of up to n kinds of objects, where each kind of object can occur at most two times.
T(k,n) = n![x^n](1+x+x^2/2)^k. Double e.g.f.: Sum_{k,n} T(k,n)*(z^k/k!)*(x^n/n!) = exp(z(1+x+x^2/2)). - N-E. Fahssi, Apr 22 2009
T(j+k,n) = Sum_{i=0..n} binomial(n,i)*T(j,i)*T(k,n-i). - Dennis P. Walsh, Feb 15 2011

cp's OEIS Frontend

A336309 Triangular array read by rows. T(n,k) is the number of labeled rooted unordered binary trees (as in A036774) with path length exactly k, n >= 1, 0 <= k <= C(n,2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A071356 Expansion of (1 - 2*x - sqrt(1 - 4*x - 4*x^2))/(4*x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Sage

Formula

A063895 Start with x, xy; then concatenate each word in turn with all preceding words, getting x xy xxy xxxy xyxxy xxxxy xyxxxy xxyxxxy ...; sequence gives number of words of length n. Also binary trees by degree: x (x,y) (x,(x,y)) (x,(x,(x,y))) ((x,y),(x,(x,y)))...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A325201 Square array whose entry A(n,k) is the number of labeled rooted trees on a set of size n where each node has at most k neighbors that are further away from the root than the node itself, for n >= 0, k >= 0, read by descending antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A036775 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 3 neighbors that are further away from the root than the node itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

Python

Formula

Extensions

A036776 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 4 neighbors that are further away from the root than the node itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

Python

Formula

Extensions

A036777 Number of labeled rooted trees with a degree constraint (described in the comments below).

Views

A071356 Expansion of (1 - 2x - sqrt(1 - 4x - 4x^2))/(4x^2).