A102403 -id:A102403 - cp's OEIS frontend

A303023 Number of anti-binary (no binary branchings) unlabeled rooted trees with n nodes.

1, 1, 1, 2, 4, 8, 16, 32, 66, 139, 297, 642, 1404, 3097, 6888, 15428, 34770, 78785, 179397, 410264, 941935, 2170275, 5016604, 11630024, 27034824, 63000261, 147148341, 344419767, 807746487, 1897829065, 4466643367, 10529301944, 24858143953, 58769113863

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

			The a(6) = 8 rooted trees:
  (((((o)))))
  (((ooo)))
  ((oo(o)))
  (oo((o)))
  (o(o)(o))
  ((oooo))
  (ooo(o))
  (ooooo)

Alois P. Heinz, Table of n, a(n) for n = 1..2000

Cf. A000081, A000598, A001190, A001678, A102403, A292050, A298204, A298422.

Cf. A303022, A303024, A303025, A303026, A303027, A318520.

b:= proc(n, i, t) option remember; `if`(n=0, `if`(t=1, 0, 1), `if`(i<1, 0,
      add(b(n-i*j, i-1, max(0, t-j))*binomial(a(i)+j-1, j), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n-1$2, 3)):
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 27 2018

burt[n_]:=burt[n]=If[n==1,{{}},Join@@Table[Union[Sort/@Tuples[burt/@c]],{c,Select[IntegerPartitions[n-1],Length[#]!=2&]}]];
Table[Length[burt[n]],{n,20}]
(* Second program: *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[t == 1, 0, 1], If[i < 1, 0, Sum[b[n-i*j, i-1, Max[0, t-j]]*Binomial[a[i]+j-1, j], {j, 0, n/i}]]];
a[n_] := If[n < 2, n, b[n-1, n-1, 3]];
Array[a, 50] (* Jean-François Alcover, May 16 2021, after Alois P. Heinz *)

a(24)-a(34) from Alois P. Heinz, Aug 27 2018

A303022 Number of free pure symmetric multifunctions (with empty expressions allowed) with one atom, n positions, and no unitary parts (subexpressions of the form x[y]).

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 27, 63, 152, 376, 939, 2371, 6047, 15577, 40429, 105637, 277625, 733518, 1947126, 5190503, 13888811, 37291968, 100444019, 271316998, 734802247, 1994873116, 5427893149, 14799525982, 40429761365, 110645688034, 303316712450, 832799212777

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

Also the number of orderless Mathematica expressions with one atom, n positions, and no unitary parts.

			The a(6) = 12 Mathematica expressions:
  o[o,o[][]]
  o[o[],o[]]
  o[o,o,o[]]
  o[o,o,o,o]
  o[][o,o[]]
  o[][o,o,o]
  o[][][o,o]
  o[o,o[]][]
  o[o,o,o][]
  o[][o,o][]
  o[o,o][][]
  o[][][][][]

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000108, A001003, A001006, A007853, A102403, A126120, A318049.

Cf. A303023, A303024, A303025, A303026, A303027.

allOLBF[n_]:=allOLBF[n]=If[n==1,{"o"},Join@@Cases[Table[PR[k,n-k-1],{k,n-1}],PR[h_,g_]:>Join@@Table[Apply@@@Tuples[{allOLBF[h],Select[Union[Sort/@Tuples[allOLBF/@p]],Length[#]!=1&]}],{p,IntegerPartitions[g]}]]];
Table[Length[allOLBF[n]],{n,10}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[1]); for(n=2, n, my(t=EulerT(v)-v); v=concat(v, v[n-1] + sum(k=1, n-2, v[k]*t[n-k-1]))); v} \\ Andrew Howroyd, Aug 19 2018

Terms a(21) and beyond from Andrew Howroyd, Aug 19 2018

A303025 Number of series-reduced anti-binary (no unary or binary branchings) unlabeled rooted trees with n nodes.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 2, 3, 4, 7, 11, 17, 28, 46, 74, 123, 205, 341, 571, 964, 1629, 2764, 4707, 8040, 13766, 23639, 40681, 70163, 121256, 209960, 364168, 632694, 1100906, 1918375, 3347346, 5848271, 10229977, 17915018, 31407088, 55116661, 96818589, 170229939

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

			The a(10) = 7 rooted trees:
  (oo(oo(ooo)))
  (o(ooo)(ooo))
  (oo(oooooo))
  (ooo(ooooo))
  (oooo(oooo))
  (ooooo(ooo))
  (ooooooooo)

Alois P. Heinz, Table of n, a(n) for n = 1..2000

Cf. A000081, A000598, A001190, A001678, A102403, A298204, A298422.

Cf. A303022, A303023, A303024, A303026, A303027.

b:= proc(n, i, t) option remember; `if`(n=0, `if`(t=0, 1, 0), `if`(i<1, 0,
      add(b(n-i*j, i-1, max(0, t-j))*binomial(a(i)+j-1, j), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n-1$2, 3)):
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 27 2018

zurt[n_]:=zurt[n]=If[n==1,{{}},Join@@Table[Union[Sort/@Tuples[zurt/@c]],{c,Select[IntegerPartitions[n-1],Length[#]>2&]}]];
Table[Length[zurt[n]],{n,20}]
(* Second program: *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[t == 0, 1, 0], If[i < 1, 0, Sum[b[n-i*j, i - 1, Max[0, t-j]]*Binomial[a[i]+j-1, j], {j, 0, n/i}]]];
a[n_] :=  If[n < 2, n, b[n-1, n-1, 3]];
Array[a, 50] (* Jean-François Alcover, May 17 2021, after Alois P. Heinz *)

a(36)-a(42) from Alois P. Heinz, Aug 27 2018

A303027 Number of free pure symmetric multifunctions with one atom, n positions, and no empty or unitary parts (subexpressions of the form x[] or x[y]).

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 3, 5, 7, 15, 28, 47, 90, 175, 319, 607, 1181, 2251, 4325, 8449, 16425, 31992, 62823, 123521, 243047, 480316, 951290, 1886293, 3749341, 7467815, 14893500, 29752398, 59532947, 119274491, 239275400, 480638121, 966571853, 1945901716, 3921699524

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

Also the number of orderless Mathematica expressions with one atom, n positions, and no empty or unitary parts.

			The a(10) = 15 Mathematica expressions:
  o[o,o[o,o[o,o]]]
  o[o,o[o,o][o,o]]
  o[o[o,o],o[o,o]]
  o[o,o][o,o[o,o]]
  o[o,o[o,o]][o,o]
  o[o,o][o,o][o,o]
  o[o,o[o,o,o,o,o]]
  o[o,o,o[o,o,o,o]]
  o[o,o,o,o[o,o,o]]
  o[o,o,o,o,o[o,o]]
  o[o,o][o,o,o,o,o]
  o[o,o,o][o,o,o,o]
  o[o,o,o,o][o,o,o]
  o[o,o,o,o,o][o,o]
  o[o,o,o,o,o,o,o,o]

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000108, A001003, A001006, A007853, A102403, A126120, A318049.

Cf. A303022, A303023, A303024, A303025, A303026.

allOLZR[n_]:=allOLZR[n]=If[n==1,{"o"},Join@@Cases[Table[PR[k,n-k-1],{k,n-1}],PR[h_,g_]:>Join@@Table[Apply@@@Tuples[{allOLZR[h],Select[Union[Sort/@Tuples[allOLZR/@p]],Length[#]>1&]}],{p,IntegerPartitions[g]}]]];
Table[Length[allOLZR[n]],{n,25}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[1]); for(n=2, n, my(t=EulerT(v)-v); v=concat(v, sum(k=1, n-2, v[k]*t[n-k-1]))); v} \\ Andrew Howroyd, Aug 19 2018

Terms a(29) and beyond from Andrew Howroyd, Aug 19 2018

A102402 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k ascents of length 2.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 6, 2, 17, 15, 10, 46, 51, 30, 5, 128, 175, 91, 35, 372, 568, 336, 140, 14, 1109, 1827, 1296, 504, 126, 3349, 5980, 4785, 2010, 630, 42, 10221, 19833, 17215, 8415, 2640, 462, 31527, 66078, 61908, 34210, 11385, 2772, 132, 98178, 220649, 223444, 134706, 50908, 13299, 1716

Offset: 0

Emeric Deutsch, Jan 06 2005

T(n,k) is the number of Łukasiewicz paths of length n having k steps (1,1). A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,0)=2 because we have HHH and U(2)DD, where H=(1,0), U(2)=(1,2) and D=(1,-1). Row n has 1+floor(n/2) terms. Row sums yield the Catalan numbers (A000108). T(2n,n)=A000108(n). Column 0 is A102403

			T(4,2) = 2 because we have UUDDUUDD and UUDUUDDD, where U=(1,1) and D=(1,-1).
Triangle begins:
1;
1;
1,   1;
2,   3;
6,   6,  2;
17, 15, 10;

Alois P. Heinz, Rows n = 0..200, flattened
Index entries for sequences related to Łukasiewicz

Cf. A000108, A102403.

m = 14; G[, ] = 0;
Do[G[t_, z_] = 1 + G[t, z]^2 z + G[t, z]^2 t z^2 - G[t, z]^2 z^2 + G[t, z]^3 z^3 - G[t, z]^3 t z^3 + O[t]^m + O[z]^m, {m}];
CoefficientList[#, t]& /@ Take[CoefficientList[G[t, z], z], m] // Flatten (* Jean-François Alcover, Oct 05 2019 *)

G.f.: G=G(t,z) satisfies z^3*(1-t)G^3+z(1-z+tz)G^2-G+1=0.

A303026 Matula-Goebel numbers of series-reduced anti-binary (no unary or binary branchings) rooted trees.

Original entry on oeis.org

1, 8, 16, 32, 64, 76, 128, 152, 212, 256, 304, 424, 512, 524, 608, 722, 848, 1024, 1048, 1216, 1244, 1444, 1532, 1696, 2014, 2048, 2096, 2432, 2488, 2876, 2888, 3064, 3392, 3524, 4028, 4096, 4192, 4864, 4976, 4978, 5204, 5618, 5752, 5776, 6128, 6476, 6784

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

			The sequence of series-reduced anti-binary rooted trees together with their Matula-Goebel numbers begins:
     1: o
     8: (ooo)
    16: (oooo)
    32: (ooooo)
    64: (oooooo)
    76: (oo(ooo))
   128: (ooooooo)
   152: (ooo(ooo))
   212: (oo(oooo))
   256: (oooooooo)
   304: (oooo(ooo))
   424: (ooo(oooo))
   512: (ooooooooo)
   524: (oo(ooooo))
   608: (ooooo(ooo))
   722: (o(ooo)(ooo))
   848: (oooo(oooo))
  1024: (oooooooooo)
  1048: (ooo(ooooo))
  1216: (oooooo(ooo))
  1244: (oo(oooooo))
  1444: (oo(ooo)(ooo))
  1532: (oo(oo(ooo)))
  1696: (ooooo(oooo))
  2014: (o(ooo)(oooo))
  2048: (ooooooooooo)

Cf. A000081, A000598, A001190, A001678, A007097, A061775, A102403, A111299, A292050, A298422, A298424.

Cf. A303022, A303023, A303024, A303025, A303027.

azQ[n_]:=Or[n==1,And[PrimeOmega[n]>2,And@@Cases[FactorInteger[n],{p_,_}:>azQ[PrimePi[p]]]]]
Select[Range[1000],azQ]

A114507 Number of Dyck paths of semilength n having no ascents of length 3.

Original entry on oeis.org

1, 1, 2, 4, 10, 27, 79, 240, 750, 2387, 7711, 25214, 83315, 277799, 933596, 3159187, 10755190, 36811479, 126594819, 437220744, 1515844359, 5273760446, 18406122609, 64426136558, 226108087891, 795486834627, 2804993559426, 9911529800630, 35090946422404, 124462137097349

Offset: 0

Emeric Deutsch, Dec 03 2005

nonn

Also number of ordered trees with n edges that have no vertices of outdegree 3.

			a(3) = 4 because we have UDUDUD, UDUUDD, UUDDUD and UUDUDD, where U=(1,1), D=(1,-1).

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A102403, A114506, A114509.

Order:=36: Y:=solve(series((Y-Y^2)/(1-Y^3+Y^4),Y)=z,Y): seq(coeff(Y,z^n),n=1..32); #(Y=zG)

a114507(n):= 1/n*sum(binomial(n,j)*binomial(4*j-2*n-2, j-1) *(-1)^(n-j),j,ceiling((n+1)/2),n); /* Works for n > 0. Returns a(n-1). Vladimir Kruchinin, Mar 07 2011 */

a(n)={n++; sum(j=n\2+1, n, binomial(n, j)*binomial(4*j-2*n-2, j-1)*(-1)^(n-j))/n} \\ Andrew Howroyd, Jan 24 2025

G.f. G satisfies z^4*G^4-z^3*G^3+zG^2-G+1=0.
a(n-1) = 1/n*sum(j=ceiling((n+1)/2)..n, binomial(n,j)*binomial(4*j-2*n-2,j-1)*(-1)^(n-j)) n>0. - Vladimir Kruchinin, Mar 07 2011
D-finite with recurrence 2*n*(26405927*n-73197215)*(2*n+3)*(n+1)*a(n) +2*n*(2*n+1)*(26405927*n^2-273126414*n+480676927)*a(n-1) +4*(-793701648*n^4+4928830819*n^3-11073984912*n^2+10499531162*n-3092762541)*a(n-2) +2*(375778330*n^4-3447814000*n^3+22123257551*n^2-60324066977*n+51211836006)*a(n-3) +2*(12664700570*n^4-145150764350*n^3+621947195977*n^2-1179232268341*n+833841845214)*a(n-4) -3*(n-4)*(11017381441*n^3-111829680906*n^2+390445674963*n-461862831838)*a(n-5) -(n-4)*(n-5)*(30888861033*n^2-148676625095*n+156786419682)*a(n-6) +3206*(n-5)*(n-6)*(18970222*n-55906401)*(n-4)*a(n-7)=0. - R. J. Mathar, Jul 26 2022

a(27) onwards from Andrew Howroyd, Jan 24 2025

A114509 Number of Dyck paths of semilength n having no ascents of length 4.

Original entry on oeis.org

1, 1, 2, 5, 13, 37, 111, 345, 1104, 3611, 12016, 40548, 138414, 477076, 1657956, 5802920, 20436910, 72369903, 257518806, 920333307, 3302003826, 11888979066, 42944410207, 155576009845, 565127618392, 2057903975752, 7510967300206

Offset: 0

Emeric Deutsch, Dec 03 2005

nonn

Also number of ordered trees with n edges that have no vertices of outdegree 4.

			a(4) = 13 because among the Catalan(4)=14 Dyck paths of semilength 4 only UUUUDDDD has an ascent of length 4 (here U=(1,1), D=(1,-1)).

Cf. A102403, A114507, A114508.

Order:=35: Y:=solve(series((Y-Y^2)/(1-Y^4+Y^5),Y)=z,Y): seq(coeff(Y,z^n),n=1..30); #(Y=zG)

a114509(n):= 1/n*sum(binomial(n,j)*binomial(5*j-3*n-2,j-1)* (-1)^(n-j),j,ceiling((3*n+2)/5),n); /* Works for n > 0. Returns a(n-1). Vladimir Kruchinin, Mar 07 2011 */

G.f.: G=G(z) satisfies z^5*G^5-z^4*G^4+zG^2-G+1=0.

a(n) = (1/n)*sum(j=ceiling((3*n+2)/5)..n, C(n,j)*C(5*j-3*n-2,j-1) * (-1)^(n-j)), n>0. [Vladimir Kruchinin, Mar 07 2011]

A135307 Number of Dyck paths of semilength n that do not contain the string UDDU.

Original entry on oeis.org

1, 1, 2, 4, 9, 23, 63, 178, 514, 1515, 4545, 13827, 42540, 132124, 413741, 1304891, 4141198, 13214815, 42375461, 136478383, 441285890, 1431925180, 4661485203, 15219836738, 49827678840, 163535624722, 537962562453, 1773437280323

Offset: 0

N. J. A. Sloane, Dec 07 2007

Top left terms of powers of the production matrix M generates sequence A102403. - Gary W. Adamson, Jan 30 2012

			a(6) = 63 since the top row of M^5 = (17, 17, 13, 10, 5, 1), sum of terms = 63.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Eric S. Egge and Kailee Rubin, Snow Leopard Permutations and Their Even and Odd Threads, arXiv:1508.05310 [math.CO], 2015
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Leading column of A135306.
Cf. A102403.
Column k=9 of A243753.

A135306 := proc(n,k) if n =0 then 1 ; else add((-1)^(j-k)*binomial(n-k,j-k)*binomial(2*n-3*j,n-j+1),j=k..floor((n-1)/2)) ; %*binomial(n,k)/n ; fi ; end: A135307 := proc(n) A135306(n,0) ; end: for n from 0 to 30 do printf("%a, ",A135307(n)) ; od: # R. J. Mathar, Dec 08 2007
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [1$2, 2, 4][n+1],
      (2*n*(n-1)*(28*n^2-56*n-3)*a(n-1)
       +(140*n^4-630*n^3+1063*n^2-699*n+144)*a(n-2)
       -12*(n-3)*(14*n^3-42*n^2+16*n+21)*a(n-3)
       +23*(n-3)*(n-4)*(28*n^2-14*n-3)*a(n-4))/
       (n*(n+1)*(28*n^2-70*n+39)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 13 2014

a[n_] := Sum[(-1)^j*Binomial[n, j]*Binomial[2*n-3*j, n-j+1], {j, 0, (n-1)/2}]/n; a[0] = 1; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Nov 27 2014, after R. J. Mathar *)

G.f.: f(x) satisfies x*f(x)^3 - (x+1)*f(x)^2 + (2*x+1)*f(x) - x = 0 . - Eric Rowland, Mar 29 2013
The Sapounakis et al. reference gives an explicit formula.
From Gary W. Adamson, Jan 30 2012: (Start)
a(n) is the sum of top row terms in M^(n-1), where M = the following infinite square production matrix:
  1, 1, 0, 0, 0, 0, ...
  0, 1, 1, 0, 0, 0, ...
  1, 0, 1, 1, 0, 0, ...
  1, 1, 0, 1, 1, 0, ...
  1, 1, 1, 0, 1, 1, ... (End)
a(n) ~ sqrt(8 + 5*sqrt(2) + sqrt(2*(11 + 8*sqrt(2))/7))/4 * ((1 + sqrt(13 + 16*sqrt(2)))/2)^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jan 27 2015

More terms from R. J. Mathar, Dec 08 2007

cp's OEIS Frontend

A303023 Number of anti-binary (no binary branchings) unlabeled rooted trees with n nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A303022 Number of free pure symmetric multifunctions (with empty expressions allowed) with one atom, n positions, and no unitary parts (subexpressions of the form x[y]).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A303025 Number of series-reduced anti-binary (no unary or binary branchings) unlabeled rooted trees with n nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A303027 Number of free pure symmetric multifunctions with one atom, n positions, and no empty or unitary parts (subexpressions of the form x[] or x[y]).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A102402 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k ascents of length 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A303026 Matula-Goebel numbers of series-reduced anti-binary (no unary or binary branchings) rooted trees.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A114507 Number of Dyck paths of semilength n having no ascents of length 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Maxima

PARI

Formula

Extensions