Lifoma Salaam - cp's OEIS frontend

User: Lifoma Salaam

Lifoma Salaam has authored 4 sequences.

A179176 Number of vertices with even distance from the root in "0-1-2" Motzkin trees on n edges.

1, 1, 3, 9, 24, 66, 187, 529, 1506, 4312, 12394, 35742, 103377, 299745, 871011, 2535873, 7395522, 21600720, 63176964, 185004852, 542365407, 1591631595, 4675170690, 13744341390, 40438307599, 119063564395, 350799321531

Offset: 0

Lifoma Salaam, Jan 04 2011

nonn

"0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers.

			We have a(3)=9, as there are 9 vertices with even distance from the root in the 4 "0-1-2" Motzkin trees on 3 edges.

Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008.

Cf. A178834, A121320, A091958, A143364, A091958.

with(LREtools): with(FormalPowerSeries): # requires Maple 2022
M:= (1-z-sqrt(1-2*z-3*z^2))/(2*z^2): T:=1/sqrt(1-2*z-3*z^2):
ogf:= (M*T^2)/(2*T-1): req:= FindRE(ogf,z,u(n)):
init:= [1, 1, 3, 9, 24, 66]: iseq:= seq(u(i-1)=init[i],i=1..nops(init)):
rmin:= subs(n=n-4, MinimalRecurrence(req,u(n),{iseq})[1]); # Mathar's recurrence
a:= gfun:-rectoproc({rmin, iseq}, u(n), remember):
seq(a(n),n=0..27); # Georg Fischer, Nov 04 2022
# Alternative, using function FindSeq from A174403:
ogf := (1-x-sqrt(-3*x^2-2*x+1))/(2*x^2*(3*x^2+2*sqrt(-3*x^2-2*x+1)+2*x-1)):
a := FindSeq(ogf): seq(a(n), n=0..28); # Peter Luschny, Nov 04 2022

G.f.: (M*T^2)/(2T-1) where M =(1-z-sqrt(1-2*z-3*z^2))/(2*z^2), the g.f. for the Motzkin numbers, and T=1/sqrt(1-2*z-3*z^2), the g.f. for the central trinomial numbers.

D-finite with recurrence: 3*(n+2)*(2*n-1)*a(n) -(4*n+5)*(2*n-1)*a(n-1) +(-20*n^2-8*n+27)*a(n-2) -3*(2*n+3)*(4*n-3)*a(n-3) -9*(2*n+3)*(n-1)*a(n-4)=0. - R. J. Mathar, Jul 24 2012

A178834 a(n) counts anti-chains of size two in "0,1,2" Motzkin trees on n edges.

Original entry on oeis.org

0, 0, 1, 5, 23, 91, 341, 1221, 4249, 14465, 48442, 160134, 523872, 1699252, 5472713, 17520217, 55801733, 176942269, 558906164, 1759436704, 5522119250, 17285351782, 53977433618, 168194390290, 523076690018, 1623869984706

Offset: 0

Lifoma Salaam, Dec 27 2010

nonn

"0,1,2" trees are rooted trees where each vertex has outdegree zero, one or two. They are counted by the Motzkin numbers.
From Petros Hadjicostas, Jun 02 2020: (Start)
Let A(r,n) be the number of ordered pairs (T, s), where T is a "0,1,2" tree (Motzkin tree) with n edges and s is an r-element anti-chain in T. See Definition 42, p. 30, in Salaam (2008) but we use different notation here.
An r-element anti-chain in a tree is a set of r nodes such that, for every two nodes u and v in the set, u is neither an ancestor nor a descendant of v.
For the current sequence, a(n) = A(r=2, n) for n >= 0.
Let A[r](z) = Sum_{n >= 0} A(r,n)*z^n be the g.f. of the sequence (A(r,n): n >= 0) for fixed r >= 1.
In Theorem 44 (p. 33), Salaam proved that A[r](z) = c_{r-1} * z^(2*r-2) * L(z)^(r-1) * V(z)^r, where c_r = (1/(r + 1))*binomial(2*r, r) is the r-th Catalan number in A000108, L(z) = T(z) = 1/sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers A002426, and V(z) = T(z)*M(z), where M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2) is the g.f. of the Motzkin numbers A001006.
It follows (see Table 2.4, p. 39) that A[r](z) = c_{r-1} * z^(2*r-2) * T(z)^(2*r-1) * M(z)^r for fixed r >= 1.
For r = 1, A[r=1](z) = Sum_{n >= 0} A(r=1, n)*z^n = T(z)*M(z) = V(z) is the g.f. of the total number of vertices in all "0,1,2" trees with n edges (i.e., the g.f. of the sequence (A005717(n+1): n >= 0)).
For r = 2, A[r=2](z) = z^2 * T(z)^3 * M(z)^2 is the g.f. of the current sequence. (End)

			For n = 3, we have a(3) = 5 because there are 5 two-element anti-chains on "0,1,2" Motzkin trees on 3 edges.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008; see Definition 42 (p. 30), Theorem 44 (p. 33), and Table 2.4 (p. 39).

Cf. A000108, A002426, A001006, A005717.

m:=30; R:=PowerSeriesRing(Rationals(), m); [0,0] cat Coefficients(R!( (1-x-Sqrt(1-2*x-3*x^2))^2/(4*x^2*Sqrt(1-2*x-3*x^2)^3) )); // G. C. Greubel, Jan 21 2019

M:= (1-z -Sqrt[1-2*z-3*z^2])/(2*z^2); T:= 1/Sqrt[1-2*z-3*z^2]; CoefficientList[Series[z^2*M^2*T^3, {z, 0, 30}], z] (* G. C. Greubel, Jan 21 2019 *)

z='z+O('z^33); M=(1-z-sqrt(1-2*z-3*z^2))/(2*z^2); T=1/sqrt(1-2*z-3*z^2); v=Vec(z^2*M^2*T^3+'tmp); v[1]=0; v

((1-x-sqrt(1-2*x-3*x^2))^2/(4*x^2*sqrt(1-2*x-3*x^2)^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jan 21 2019

G.f.: z^2 * M(z)^2 * T(z)^3, where M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2) is the g.f. of the Motzkin numbers and T(z) = 1/sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers.
D-finite with recurrence: -(n-2)*(n+2)*a(n) + (4*n^2-n-8)*a(n-1) + (2*n^2-n-12)*a(n-2) - 3*n*(4*n-3)*a(n-3) - 9*n*(n-1)*a(n-4) = 0. - R. J. Mathar, Jun 14 2016
a(n) ~ 3^(n + 3/2) * sqrt(n) / (4*sqrt(Pi)) * (1 - sqrt(3*Pi)/sqrt(n)). - Vaclav Kotesovec, Mar 08 2023

A139262 Total number of two-element anti-chains over all ordered trees on n edges.

Original entry on oeis.org

0, 0, 1, 8, 47, 244, 1186, 5536, 25147, 112028, 491870, 2135440, 9188406, 39249768, 166656772, 704069248, 2961699667, 12412521388, 51854046982, 216013684528, 897632738722, 3721813363288, 15401045060572, 63616796642368, 262357557683422, 1080387930269464, 4443100381114156

Offset: 0

Lifoma Salaam, Apr 12 2008

nonn

From Miklos Bona, Mar 04 2009: (Start)
This is the same as the total number of inversions in all 132-avoiding permutations of length n by the well-known bijection between ordered trees on n edges and such permutations.
For example, there are five permutations of length three that avoid 132, namely, 123, 213, 231, 312, and 321. Their numbers of inversions are, respectively, 0,1,2,2, and 3, for a total of eight inversions.
(End)
Appears to be a shifted version of A029760. - R. J. Mathar, Mar 30 2014
a(n) is the number of total East steps below y = x-1 of all North-East paths from (0,0) to (n,n). Details can be found in Section 3.1 and Section 5 in Pan and Remmel's link. - Ran Pan, Feb 01 2016

			a(3) = 8 because there are 5 ordered trees on 3 edges and two of the trees have 2 two-element anti-chain each, one of the trees has three two element anti-chains, one of the trees has one two element anti-chain and the last tree does not have any two-element anti-chains. Hence in ordered trees on 3 edges there are a total of (2)(2)+1(3)+1(1) = 8 two element anti-chains.

Robert Israel, Table of n, a(n) for n = 0..1650
Miklós Bóna, Surprising Symmetries in Objects Counted by Catalan Numbers, Electronic J. Combin., 19 (2012), #P62, eq. (2).
Ran Pan, Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008.
Sittipong Thamrongpairoj, Dowling Set Partitions, and Positional Marked Patterns, Ph. D. Dissertation, University of California-San Diego (2019).

Cf. A129182, A139263.

0, seq((n+1)*(2*n-1)!/(n!*(n-1)!) - 2^(2*n-1), n=1..30); # Robert Israel, Feb 02 2016

a[0] = 0; a[n_] := (n+1)(2n-1)!/(n! (n-1)!) - 2^(2n-1);
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 19 2018, from Maple *)

G.f.: (up to offset): A = x^2*(B^3)*(C^2), where B is the generating function for the central binomial coefficients and C is the generating function for the Catalan numbers. Thus A = x^2*(1/sqrt(1-4*x))^3*((1-sqrt(1-4*x))/2*x)^2.
2*a(n) = (n+1)*A000984(n) - 4^n. - J. M. Bergot, Feb 02 2013
Conjecture: n*(n-2)*a(n) +2*(-4*n^2+9*n-3)*a(n-1) +8*(n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Feb 03 2013
The above conjecture follows easily from the formula by J. M. Bergot. - Robert Israel, Feb 02 2016
a(n) = Sum_{k=0..n^2} (n^2-k)/2 * A129182(n,k). - Alois P. Heinz, Mar 31 2018

Terms beyond a(9) added by Joerg Arndt, Dec 30 2012

A139263 Number of two element anti-chains in Riordan trees on n edges (also called non-redundant trees, i.e., ordered trees where no vertex has out-degree equal to 1).

Original entry on oeis.org

0, 0, 1, 3, 14, 48, 172, 580, 1941, 6373, 20725, 66763, 213575, 679141, 2148948, 6771068, 21257741, 66529077, 207639925, 646480555, 2008458669, 6227766899, 19277394308, 59577651108, 183865477474, 566700165898, 1744578701517, 5364804428455, 16480883532586, 50582859417868, 155114365434224

Offset: 0

Lifoma Salaam, Apr 12 2008

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..2093
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008; see p. 40.

Cf. A001006, A005043, A102839, A139262, A178834.

R:=PowerSeriesRing(Rationals(), 35); [0,0] cat Coefficients(R!( (1 -x -Sqrt(1-2*x-3*x^2))*Sqrt(1-2*x-3*x^2)/(2*(1+x)*(1-2*x-3*x^2)^2) )); // G. C. Greubel, Jun 02 2020

a:= proc(n) option remember; `if`(n<4, [0$2, 1, 3][n+1],
      ((4*n-3)*(n-2)*a(n-1)+(2*n+9)*(n-2)*a(n-2)-3*
       (4*n-9)*n*a(n-3)-9*(n-1)*n*a(n-4))/(n*(n-2)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 02 2020

CoefficientList[Series[(1 -x -Sqrt[1-2*x-3*x^2])*Sqrt[1-2*x-3*x^2]/(2*(1+x)*(1 - 2*x-3*x^2)^2), {x, 0, 35}], x] (* G. C. Greubel, Jun 02 2020 *)

default(seriesprecision, 50)
f(x) = 1/sqrt(1-2*x-3*x^2);
r(x) = (1+x-sqrt(1-2*x-3*x^2))/(2*x*(1+x));
a(n) = polcoef(x^2*r(x)^2*f(x)^3, n, x);
for(n=0, 30, print1(a(n), ",")) \\ Petros Hadjicostas, Jun 02 2020

r(x)=(1+x-sqrt(1-2*x-3*x^2))/(2*x*(1+x))
m(x)=(1-x-sqrt(1-2*x-3*x^2))/(2*x^2)
g(x)=derivative(x*r(x),x)
a(x)=x^2*(x*m(x)+1)^3*g(x)^3/r(x)
taylor(a(x),x,0,30).list() # Petros Hadjicostas, Jun 02 2020

G.f.: A(x) = x^2 * (x*M(x) + 1)^3 * (d(x*R(x))/dx)^3/R(x), where M is the generating function for the Motzkin numbers and R is the generating function for the Riordan numbers.
From Petros Hadjicostas, Jun 02 2020: (Start)
Here R(x) = (1 + x - sqrt(1 - 2*x - 3*x^2))/(2*x*(1-x)) = g.f. of A005043 and M(x) = (1 - x - sqrt(1 - 2*x - 3*x^2))/(2*x^2) = g.f. of A001006.
If we let s(x) = sqrt(1 - 2*x - 3*x^2), then A(x) = x^2*((1 + x - s(x))/(2*x*(1 + x)))^2/s(x)^3 (see p. 40 in Salaam (2008)).
Alternatively, we may write A(x) = x^2 * R(x)^2 * B(x), where B(x) = g.f. of (A102839(n+1): n >= 0). (End)

a(10)-a(30) from Petros Hadjicostas, Jun 02 2020

cp's OEIS Frontend

User: Lifoma Salaam

A179176 Number of vertices with even distance from the root in "0-1-2" Motzkin trees on n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A178834 a(n) counts anti-chains of size two in "0,1,2" Motzkin trees on n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A139262 Total number of two-element anti-chains over all ordered trees on n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A139263 Number of two element anti-chains in Riordan trees on n edges (also called non-redundant trees, i.e., ordered trees where no vertex has out-degree equal to 1).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions