A000346 -id:A000346 - cp's OEIS frontend

A053979 Triangle T(n,k) giving number of rooted maps regardless of genus with n edges and k nodes (n >= 0, k = 1..n+1).

1, 1, 1, 3, 5, 2, 15, 32, 22, 5, 105, 260, 234, 93, 14, 945, 2589, 2750, 1450, 386, 42, 10395, 30669, 36500, 22950, 8178, 1586, 132, 135135, 422232, 546476, 388136, 166110, 43400, 6476, 429, 2027025, 6633360, 9163236, 7123780, 3463634, 1092560, 220708, 26333, 1430

Offset: 0

N. J. A. Sloane, Apr 09 2000

Triangle T(n,k), read by rows, given by (1,2,3,4,5,6,7,8,9,...) DELTA (1,1,1,1,1,1,1,1,1,1,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 21 2011.

A127160*A007318 as infinite lower triangular matrices. - Philippe Deléham, Jan 06 2012

			A(x;t) = t + (t + t^2)*x + (3*t + 5*t^2 + 2*t^3)*x^2 + (15*t + 32*t^2 + 22*t^3 + 5*t^4)*x^3 + ...
Triangle begins :
n\k [1]     [2]     [3]     [4]     [5]     [6]    [7]   [8]
[0] 1;
[1] 1,      1;
[2] 3,      5,      2;
[3] 15,     32,     22,     5;
[4] 105,    260,    234,    93,     14;
[5] 945,    2589,   2750,   1450,   386,    42;
[6] 10395,  30669,  36500,  22950,  8178,   1586,  132;
[7] 135135, 422232, 546476, 388136, 166110, 43400, 6476, 429;
[8] ...

Gheorghe Coserea, Rows n=0..100, flattened
D. Arques and J.-F. Beraud, Rooted maps on orientable surfaces, Riccati's equation and continued fractions, Discrete Math., 215 (2000), 1-12.
R. Cori, Indecomposable permutations, hypermaps and labeled Dyck paths, arXiv:0812.0440v1 [math.CO], 2008.
R. Cori, Indecomposable permutations, hypermaps and labeled Dyck paths, Journal of Combinatorial Theory, Series A 116 (2009) 1326-1343.
J. Courtiel, K. Yeats, Connected chord diagrams and bridgeless maps, arXiv:1611.04611, eq. (18)
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I, J. Comb. Theory B 13 (1972), 192-218, eq. (5).

Cf. A000108, A000346, A001147, A084938. A000698, A025192, A084120, A127160, A167872.

G:=t/(1-(t+1)*z/(1-(t+2)*z/(1-(t+3)*z/(1-(t+4)*z/(1-(t+5)*z/(1-(t+6)*z/(1-(t+7)*z/(1-(t+8)*z/(1-(t+9)*z/(1-(t+10)*z/(1-(t+11)*z/(1-(t+12)*z)))))))))))):Gser:=simplify(series(G,z=0,10)):P[0]:=t:for n from 1 to 9 do P[n]:=sort(expand(coeff(Gser,z^n))) od:seq(seq(coeff(P[n],t^k),k=1..n+1),n=0..9); # Emeric Deutsch, Apr 01 2005

g = t/Fold[1-((t+#2)*z)/#1&, 1, Range[12, 1, -1]]; T[n_, k_] := SeriesCoefficient[g, {z, 0, n}, {t, 0, k}]; Table[T[n, k], {n, 0, 9}, {k, 1, n+1}] // Flatten (* Jean-François Alcover, Jan 08 2014 *)

A053979_ser(N,t='t) = {
  my(x='x+O('x^N), y0=1, y1=0, n=1);
  while(n++, y1 = (1 + t*x*y0^2 + 2*x^2*y0')/(1-x);
    if (y1 == y0, break()); y0 = y1); y0;
};
concat(apply(p->Vecrev(p), Vec(A053979_ser(10))))
\\ test: y=A053979_ser(50); 2*x^2*deriv(y,x) == -t*x*y^2 + (1-x)*y - 1
\\ Gheorghe Coserea, May 31 2017

A053979_seq(N) = {
  my(t='t, R=vector(N), S=vector(N)); R[1]=S[1]=t;
  for (n=2, N,
    R[n] = t*subst(S[n-1],t,t+1);
    S[n] = R[n] + sum(k=1, n-1, R[k]*S[n-k]));
  apply(p->Vecrev(p), R/t);
};
concat(A053979_seq(10))
\\ test: y=t*Ser(apply(p->Polrev(p,'t), A053979_seq(50)),'x); y == t + x*y^2 + x*y + 2*x^2*deriv(y,x) && y == t + x*y*subst(y,t,t+1) \\ Riccati eq && Dyck eq
\\ Gheorghe Coserea, May 31 2017

G.f.: t/(1-(t+1)z/(1-(t+2)z/(1-(t+3)z/(1-(t+4)z/(1-(t+5)z/(1-... (Eq. (5) in the Arques-Beraud reference). - Emeric Deutsch, Apr 01 2005
Sum_{k = 0..n} (-1)^k*2^(n-k)*T(n,k) = A128709(n). Sum_{k = 0..n} T(n,k) = A000698(n+1). - Philippe Deléham, Mar 24 2007
From Peter Bala, Dec 22 2011: (Start)
The o.g.f. in the form G(x,t) = x/(1 - (t+1)*x^2/(1 - (t+2)*x^2/(1 - (t+3)*x^2/(1 - (t+4)*x^2/(1 - ... ))))) = x + (1+t)*x^3 + (3+5*t+2*t^2)*x^5 + ... satisfies the Riccati equation (1 - t*x*G)*G = x + x^3*dG/dx. The cases t = 0, t = 1 and t = 2 give A001147, A000698 and A167872, respectively. The cases t = -2, t = -3 and t = -4 give rational generating functions for aerated and signed versions of A000012, A025192 and A084120, respectively.
The identity G(x,1+t) = 1/(1+t)(1/x-1/G(x,t)) provided t <> -1 allows us to express G(x,n), n = 1,2,..., in terms of G(x,0), a generating function for the double factorial numbers.
Writing G(x,t) = Sum_{n >= 1} R(n,t)*x^(2*n-1), the row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) = (2*n-1)*R(n,t) + t*sum {k = 1..n} R(k,t)*R(n+1-k,t) with initial condition R(1,t) = 1.
G(x,t-1) = x + t*x^3 + (t+2*t^2)*x^5 + (3*t+7*t^2+5*t^3)*x^7 + ... is an o.g.f. for A127160.
The function b(x,t) = - t*G(1/x,t) satisfies the partial differential equation d/dx(b(x,t)) = -(t + (x + b(x,t))*b(x,t)). Hence the differential operator (D^2 + x*D + t), where D = d/dx, factorizes as (D - a(x,t))*(D - b(x,t)), where a(x,t) = -(x + b(x,t)). In the particular case t = -n, a negative integer, the functions a(x,-n) and b(x,-n) become rational functions of x expressible as the ratio of Hermite polynomials.
(End)

More terms from Emeric Deutsch, Apr 01 2005

A049235 Sum of balls on the lawn for the s=3 tennis ball problem.

Original entry on oeis.org

0, 6, 75, 708, 5991, 47868, 369315, 2783448, 20631126, 151026498, 1094965524, 7878119760, 56330252412, 400703095284, 2838060684483, 20027058300144, 140874026880204, 988194254587242, 6915098239841331, 48285969880645908, 336521149274459979

Offset: 0

N. J. A. Sloane, Jan 19 2003

nonn

Robert Israel, Table of n, a(n) for n = 0..1202
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (S_n for s=3).

The four sequences T_n, Y_n, A_n, S_n for s=2 are A000108, A000302, A000346, A031970, for s=3, A001764, A006256, A075045, this sequence, for s=4, A002293, A078995, A078999, A078516.

Cf. A079486.

T := (n,s)->binomial(s*n,n)/((s-1)*n+1); Y := (n,s)->add(binomial(s*k,k)*binomial(s*(n-k),n-k),k=0..n); A := (n,s)->Y(n+1,s)/2-(1/2)*((2*s-3)*n+2*s-2)*T(n+1,s); S := (n,s)->(1/2)*(s*n^2+(3*s-1)*n+2*s)*T(n+1,s)-Y(n+1,s)/2;
F := 3*(2-3*t)*t*((t-1)*(3*t-1))^(-3);  G := t*(t-1)^2;   Ginv := RootOf(G-x,t);
ogf := series(eval(F,t=Ginv), x=0, 20);

a[n_] := a[n] = Switch[n, 0, 0, 1, 6, 2, 75, 3, 708, 4, 5991, _, -((1/(8*(2*(n-5)^2 + 25*(n-5) + 78)))*(-(531441*(n-5)^2* a[n-5]) + 196830*(n-5)^2*a[n-4] - 24057*(n-5)^2*a[n-3] + 1809*(n-5)^2*a[n-2] - 232*(n-5)^2*a[n-1] - 1594323*(n-5)*a[n-5] + 747954*(n-5)*a[n-4] - 120285*(n-5)*a[n-3] + 16362*(n-5)*a[n-2] - 2798*(n-5)*a[n-1] - 1180980*a[n-5] + 656100*a[n-4] - 131220*a[n-3] + 36825*a[n-2] - 8352*a[n-1]))];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 02 2023, after Robert Israel *)

a(n) is asymptotic to c*sqrt(n)*(27/4)^n with c=2.4... - Benoit Cloitre, Jan 26 2003, c = 81*sqrt(3/Pi)/32 = 2.4735502165085321... - Vaclav Kotesovec, Feb 07 2019
G.f.: F(G^(-1)(x)) where F = 3*(2-3*t)*t*((t-1)*(3*t-1))^(-3) and G = t*(t-1)^2.  - Mark van Hoeij, Oct 30 2011
D-finite with recurrence (531441*n^2 + 1594323*n + 1180980)*a(n) + (-196830*n^2 - 747954*n - 656100)*a(n + 1) + (24057*n^2 + 120285*n + 131220)*a(n + 2) + (-1809*n^2 - 16362*n - 36825)*a(n + 3) + (232*n^2 + 2798*n + 8352)*a(n + 4) + (-16*n^2 - 200*n - 624)*a(n + 5) = 0. - Robert Israel, Jun 20 2019

A068551 a(n) = 4^n - binomial(2*n,n).

Original entry on oeis.org

0, 2, 10, 44, 186, 772, 3172, 12952, 52666, 213524, 863820, 3488872, 14073060, 56708264, 228318856, 918624304, 3693886906, 14846262964, 59644341436, 239532643144, 961665098956, 3859788636664, 15488087080696, 62135313450064

Offset: 0

N. J. A. Sloane, Mar 23 2002

Number of rooted two-face n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005
Total number of returns to the x axis in all lattice paths using steps (1,1) and (1,-1) from the origin to (2n,0). Cf. A108747. - Geoffrey Critzer, Jan 30 2012
Total depth of all leaves in all binary trees on 2n+1 nodes. - Marko Riedel, Sep 10 2016

H. W. Gould, Combinatorial Identities, Morgantown, WV, 1972. p. 32.
Hojoo Lee, Posting to Number Theory List, Feb 18 2002.
V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Vincenzo Librandi, Table of n, a(n) for n = 0..175
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO], 2023.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Marko R. Riedel, Average depth of a leaf in a binary tree, Math.Stackexchange.com.
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36(4) (2006), 364-387.

Cf. A000108, A000346, A000984, A005470, A045621.

[4^n - Binomial(2*n,n): n in [0..35]]; // Vincenzo Librandi, Jun 07 2011

A068551:=n->4^n - binomial(2*n,n): seq(A068551(n), n=0..30); # Wesley Ivan Hurt, Mar 22 2014

nn=20;c=(1-(1-4x)^(1/2))/(2x); D[CoefficientList[ Series[ 1/(1-2y x c), {x,0,nn}], x], y]/.y->1 (* Geoffrey Critzer, Jan 30 2012 *)

PARI
```
a(n)=if(n<0,0,4^n-binomial(2*n,n))
```

x='x+O('x^100); concat(0, Vec(1/(1-4*x)-1/sqrt(1-4*x))) \\ Altug Alkan, Dec 29 2015

G.f.: 1/(1 - 4*x) - 1/sqrt(1 - 4*x) = C(x)*2*x/(1 - 4*x) where C(x) = g.f. for Catalan numbers A000108.
a(n) = Sum_{k >= 1} binomial(2*m-2*k, m-k) * binomial(2*k, k).
a(n+1) = 4*a(n) + 2*C(n), where C(n) = Catalan numbers.
a(n) = 2*A000346(n-1) for n > 0.
a(n) = A045621(2*n).
Conjecture: n*a(n) + 2*(3-4*n)*a(n-1) + 8*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Apr 01 2012
Recurrence (an alternative): n*a(n) = 2^9*(2*n - 9)*a(n-5) + 2^8*(18 - 5*n)*a(n-4) + 2^6*(10*n - 27)*a(n-3) + 2^5*(9 - 5*n)*a(n-2) + 2*(10*n - 9)*a(n-1), n >= 5. - Fung Lam, Mar 22 2014
Asymptotics: a(n) ~ 2^(2*n)*(1 - 1/sqrt(n*Pi)). - Fung Lam, Mar 22 2014
E.g.f.: (exp(2*x) - BesselI(0, 2*x))*exp(2*x). - Ilya Gutkovskiy, Sep 10 2016
a(n) = (-1)^(n+1)*binomial(-n, n + 1)*hypergeom([1, 2*n + 1], [n + 2], 1/2). - Peter Luschny, Nov 29 2023

A138158 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and path length k; 0 <= k <= n(n+1)/2.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 1, 3, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 1, 4, 6, 7, 7, 5, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1, 5, 10, 14, 17, 16, 16, 14, 11, 9, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 6, 15, 25, 35, 40, 43, 44, 40, 37, 32, 28, 22, 18, 13, 11, 7, 5, 3, 2, 1, 1

Offset: 0

Emeric Deutsch, Mar 21 2008

T(n,k) is the number of Dyck paths of semilength n for which the sum of the heights of the vertices that terminate an upstep (i.e. peaks and doublerises) is k. Example: T(4,7)=3 because we have UUDUDUDD, UDUUUDDD and UUUDDDUD.
See related triangle A227543.
Row n contains 1+n(n+1)/2 terms.
The maximum in each row of the triangle is A274291. - Torsten Muetze, Nov 28 2018
It appears that for j = 0,1,...,n-1 the first j terms of the rows in reversed order are given by A000041(j), the partition numbers. - Geoffrey Critzer, Jul 14 2020

			T(2,2)=1 because /\ is the only ordered tree with 2 edges and path length 2.
Triangle starts
 1,
 0, 1,
 0, 0, 1, 1,
 0, 0, 0, 1, 2, 1, 1,
 0, 0, 0, 0, 1, 3, 3, 3, 2, 1, 1,
 0, 0, 0, 0, 0, 1, 4, 6, 7, 7, 5, 5, 3, 2, 1, 1,
 0, 0, 0, 0, 0, 0, 1, 5, 10, 14, 17, 16, 16, 14, 11, 9, 7, 5, 3, 2, 1, 1,
 0, 0, 0, 0, 0, 0, 0, 1, 6, 15, 25, 35, 40, 43, 44, 40, 37, 32, 28, 22, 18, 13, 11, 7, 5, 3, 2, 1, 1,
... [_Joerg Arndt_, Feb 21 2014]

Seiichi Manyama, Rows n = 0..38, flattened
Ron M. Adin and Yuval Roichman, On maximal chains in the non-crossing partition lattice, arXiv:1201.4669 [math.CO], 2012-2013.
Luca Ferrari, Unimodality and Dyck paths, arXiv:1207.7295 [math.CO], 2012.
FindStat - Combinatorial Statistic Finder, The bounce statistic of a Dyck path, The dinv statistic of a Dyck path, The area of a Dyck path.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 185.

Cf. A227543, A000108, A005169, A000346, A047998, A274291.

P[0]:=1: for n to 7 do P[n]:=sort(expand(t*(sum(P[j]*P[n-j-1]*t^(n-j-1),j= 0.. n-1)))) end do: for n from 0 to 7 do seq(coeff(P[n], t, j),j=0..(1/2)*n*(n+1)) end do; # yields sequence in triangular form

nmax = 7;
P[0] = 1; P[n_] := P[n] = t*Sum[P[j]*P[n-j-1]*t^(n-j-1), {j, 0, n-1}];
row[n_] := row[n] = CoefficientList[P[n] + O[t]^(n(n+1)/2 + 1), t];
T[n_, k_] := row[n][[k+1]];
Table[T[n, k], {n, 0, nmax}, {k, 0, n(n+1)/2}] // Flatten (* Jean-François Alcover, Jul 11 2018, from Maple *)
nn = 10; f[z_, u_] := Sum[Sum[a[n, k] u^k z^n, {k, 0, Binomial[n, 2]}], {n, 1, nn}]; sol = SolveAlways[Series[0 == f[z, u] - z/(1 - f[u z, u]) , {z, 0, nn}], {z, u}];Level[Table[Table[a[n, k], {k, 0, Binomial[n, 2]}], {n, 1, nn}] /.
sol, {2}] // Grid (* Geoffrey Critzer, Jul 14 2020 *)

G.f. G(t,z) satisfies G(t,z) = 1+t*z*G(t,z)*G(t,t*z).
Row generating polynomials P[n]=P[n](t) are given by P[0]=1, P[n] = t * Sum( P[j]*P[n-j-1]*t^(n-1-j), j=0..n-1 ) (n>=1).
Row sums are the Catalan numbers (A000108).
Sum of entries in column n = A005169(n).
Sum_{k=0..n(n+1)/2} k*T(n,k) = A000346(n-1).
T(n,k) = A047998(k,n).
G.f.: 1/(1 - x*y/(1 - x*y^2/(1 - x*y^3/(1 - x*y^4/(1 - x*y^5)/(1 - ... ))))), a continued fraction. - Ilya Gutkovskiy, Apr 21 2017

A380237 Number of sensed planar maps with n vertices and 2 faces.

Original entry on oeis.org

1, 2, 5, 14, 42, 140, 473, 1670, 5969, 21679, 79419, 293496, 1091006, 4078213, 15312150, 57721030, 218333832, 828408842, 3151769615, 12020870753, 45949957412, 176001205559, 675384194565, 2596119292840, 9994894356158, 38535398284100, 148772774499015, 575079507042663

Offset: 1

Andrew Howroyd, Jan 19 2025

nonn

Also, by duality the number of sensed planar maps with n faces and 2 vertices.

The number of edges is n.

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

Column 2 of A379430.
Cf. A000346 (rooted), A380238 (achiral), A380239 (unsensed), A060404 (with a distinguished face), A103943 (with a distinguished vertex).
Cf. A000108, A210736.

a(n) = {(binomial(n - 1, (n - 1)\2) + sumdiv(n, d, eulerphi(n/d)*(2^(2*d-1) - binomial(2*d-1, d)))/n)/2}

seq(n)={my(c(d)=(1-sqrt(1-4*x^d + O(x*x^(n+d))))/(2*x^d)); Vec(1/(1 - x*c(2)) - 1 - sum(k=1, n, log(2 - c(k))*eulerphi(k)/k))/2}

a(n) = (A210736(n) + A060404(n))/2.
a(n) = (1/(2*n))*(n*binomial(n-1, floor((n-1)/2)) + Sum_{d|n} phi(n/d)*(2^(2*d-1) - binomial(2*d-1, d))).
G.f.: (1/2)*(1/(1 - x*C(x^2)) - 1 - Sum_{k>=1} log(1 - C(x^k)) * phi(k)/k), where C(x) is the g.f. of A000108.

A018218 Sum(C(j)(n-j)4^(n-j-1),j=0..n-1), C = Catalan numbers.

Original entry on oeis.org

0, 1, 9, 58, 325, 1686, 8330, 39796, 185517, 848830, 3827230, 17053356, 75249954, 329353948, 1431575220, 6185613032, 26589395581, 113780713806, 484945025942, 2059546425340, 8719018250838, 36805967321684

Offset: 0

N. J. A. Sloane, Peter Winkler (pw(AT)bell-labs.com)

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..173

[(n+1)*(4^n-Binomial(2*n+1, n))/2: n in [0..25]]; // Vincenzo Librandi, Jun 09 2011

Table[Sum[CatalanNumber[j](n-j)4^(n-j-1),{j,-0,n-1}],{n,0,30}] (* Harvey P. Dale, Nov 15 2020 *)

a(n)=(n+1)*(4^n-binomial(2*n+1, n))/2; G.f.: x*c(x)/(1-4*x)^2, where c(x) = g.f. for Catalan numbers A000108; also convolution of A000346(n-1), n >= 0, where A000346(-1)=0, with A000302 (powers of 4). - Wolfdieter Lang
Asymptotics: a(n) ~ 2^(2*n-1)*(n+1-sqrt(4*n/Pi)). - Fung Lam, Mar 28 2014
Recurrence: (n-1)*n*a(n) = 2*(n-1)*(4*n+1)*a(n-1) - 8*n*(2*n-1)*a(n-2). - Vaclav Kotesovec, Mar 28 2014

A033504 a(n)/4^n is the expected number of tosses of a coin required to obtain n+1 heads or n+1 tails.

Original entry on oeis.org

1, 10, 66, 372, 1930, 9516, 45332, 210664, 960858, 4319100, 19188796, 84438360, 368603716, 1598231992, 6889682280, 29551095248, 126193235194, 536799072924, 2275560109868, 9616650989560, 40527780684972, 170368957887656, 714556104675736, 2990728476330672

Offset: 0

Michael Ulm (ulm(AT)mathematik.uni-ulm.de)

The number of rooted two-vertex n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005

			From _Jeremy Tan_, Mar 13 2018: (Start)
For n=1 the sequences of flips ending at two heads or two tails are:
HH, TT (probability 1/4 each)
HTH, HTT, THH, THT (1/8 each)
The expected number of flips is 2*2*1/4 + 3*4*1/8 = 10/4 = a(1)/4^1. (End)

M. Klamkin, ed., Problems in Applied Mathematics: Selections from SIAM Review, SIAM, 1990; see pp. 127-129.
V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Vincenzo Librandi, Table of n, a(n) for n = 0..172
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36, No.4 (2006), 364-387.

Cf. A002457, A100511, A103943.

Cf. A000346, A130783.

[(n+1)*(2^(2*n+1)-Binomial(2*n+1,n+1)): n in [0..25]]; // Vincenzo Librandi, Jun 09 2011

a[n_]:=(n+1)*(2^(2*n+1)-Binomial[2*n+1,n+1])
a /@ Range[0,50] (* Julien Kluge, Jul 21 2016 *)

With a different offset: Sum_{j=0..n} Sum_{k=0..n} binomial(n, j)*binomial(n, k)*min(j, k) = n*2^(n-1) + (n/2)*binomial(2*n, n). [see Klamkin]
a(n-1) = 4^(n-1)*b(n, n), where b(n, m) = b(n-1, m)/2 + b(n, m-1)/2 + 1; b(n, 0)=b(0, n)=0.
a(n) = Sum_{k=0..n, l=0..n} 2^(2n - k - l) binomial(k+l, k).
a(n) = (2n+1)*Sum_{0<=i,j<=n} binomial(2n, i+j)/(i+j+1). - Benoit Cloitre, Mar 05 2005
a(n) = (n+1)*(2^(2*n+1) - binomial(2*n+1,n+1)). - Vladeta Jovovic, Aug 23 2007
n*a(n) + 6*(-2*n+1)*a(n-1) + 48*(n-1)*a(n-2) + 32*(-2*n+3)*a(n-3) = 0. - R. J. Mathar, Dec 22 2013
a(n) ~ 2^(2*n+1)*n. - Ilya Gutkovskiy, Jul 21 2016

Name corrected by Jeremy Tan, Mar 13 2018

A258431 Sum over all peaks of Dyck paths of semilength n of the arithmetic mean of the x and y coordinates.

Original entry on oeis.org

0, 1, 5, 23, 102, 443, 1898, 8054, 33932, 142163, 592962, 2464226, 10209620, 42190558, 173962532, 715908428, 2941192472, 12065310083, 49428043442, 202249741418, 826671597572, 3375609654698, 13771567556012, 56138319705908, 228669994187432, 930803778591278

Offset: 0

Alois P. Heinz, May 29 2015

A Dyck path of semilength n is a (x,y)-lattice path from (0,0) to (2n,0) that does not go below the x-axis and consists of steps U = (1,1) and D = (1,-1). A peak of a Dyck path is any lattice point visited between two consecutive steps UD.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Wikipedia, Average, Arithmetic mean
Wikipedia, Lattice path

Cf. A000302, A000346, A000531, A002457, A002697, A002802, A029887.

A258431:= func< n | n eq 0 select 0 else (4^(n-1) + Factorial(2*n-1)/Factorial(n-1)^2)/2 >;
[A258431(n): n in [0..40]]; // G. C. Greubel, Mar 18 2023

a:= proc(n) option remember; `if`(n<3, [0, 1, 5][n+1],
       ((8*n-10)*a(n-1)-(16*n-24)*a(n-2))/(n-1))
    end:
seq(a(n), n=0..30);

a[0]=0; a[1]=1; a[2]=5;
a[n_]:= a[n]= (2*(4*n-5)*a[n-1] - 8*(2*n-3)*a[n-2])/(n-1);
Table[a[n], {n,0,30}] (* Jean-François Alcover, May 31 2018, from Maple *)

def A258431(n): return 0 if (n==0) else (4^(n-1) + factorial(2*n-1)/factorial(n-1)^2)/2
[A258431(n) for n in range(41)] # G. C. Greubel, Mar 18 2023

G.f.: x*(1 + sqrt(1-4*x))/(2*sqrt(1-4*x)^3).
a(n) = (2*(4*n-5)*a(n-1) - 8*(2*n-3)*a(n-2))/(n-1) for n>2, a(0)=0, a(1)=1, a(2)=5.
a(n) = (4^(n-1) + (2*n-1)!/(n-1)!^2)/2 for n>0, a(0) = 0.
a(n) = (A000302(n-1) + A002457(n-1))/2 for n>0, a(0) = 0.
a(n) = (1/2)*binomial(2*n,n)*( 1 + 2*(n-1)/(n+1) + 3*(n-1)*(n-2)/((n+1)*(n+2)) + 4*(n-1)*(n-2)*(n-3)/((n+1)*(n+2)*(n+3)) + 5*(n-1)*(n-2)*(n-3)*(n-4)/((n+1)*(n+2)*(n+3)*(n+4)) + ...) for n >= 1. - Peter Bala, Feb 17 2022

A270406 Triangle read by rows: T(n,g) is the number of rooted maps with n edges and 2 faces on an orientable surface of genus g.

Original entry on oeis.org

1, 5, 22, 10, 93, 167, 386, 1720, 483, 1586, 14065, 15018, 6476, 100156, 258972, 56628, 26333, 649950, 3288327, 2668750, 106762, 3944928, 34374186, 66449432, 12317877, 431910, 22764165, 313530000, 1171704435, 792534015, 1744436, 126264820, 2583699888, 16476937840, 26225260226, 4304016990

Offset: 1

Gheorghe Coserea, Mar 16 2016

Row n contains floor((n+1)/2) terms.

			Triangle starts:
n\g    [0]          [1]          [2]          [3]          [4]
[1]    1;
[2]    5;
[3]    22,          10;
[4]    93,          167;
[5]    386,         1720,        483;
[6]    1586,        14065,       15018;
[7]    6476,        100156,      258972,      56628;
[8]    26333,       649950,      3288327,     2668750;
[9]    106762,      3944928,     34374186,    66449432,    12317877;
[10]   431910,      22764165,    313530000,   1171704435,  792534015;
[11]   ...

Gheorghe Coserea, Rows n = 1..101, flattened
Sean R. Carrell, Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014.

Columns k=0-1 give: A000346, A006295.

Q[0, 1, 0] = 1; Q[n_, f_, g_] /; n<0 || f<0 || g<0 = 0;
Q[n_, f_, g_] := Q[n, f, g] = 6/(n+1) ((2n-1)/3 Q[n-1, f, g] + (2n-1)/3 Q[n - 1, f-1, g] + (2n-3) (2n-2) (2n-1)/12 Q[n-2, f, g-1] + 1/2 Sum[l = n-k; Sum[v = f-u; Sum[j = g-i; Boole[l >= 1 && v >= 1 && j >= 0] (2k-1) (2l-1) Q[k-1, u, i] Q[l-1, v, j], {i, 0, g}], {u, 1, f}], {k, 1, n}]);
Table[Table[Q[n, 2, g], {g, 0, (n+1)/2-1}], {n, 1, 11}] // Flatten (* Jean-François Alcover, Aug 10 2018 *)

N = 10; F = 2; gmax(n) = n\2;
Q = matrix(N + 1, N + 1);
Qget(n, g) = { if (g < 0 || g > n/2, 0, Q[n+1, g+1]) };
Qset(n, g, v) = { Q[n+1, g+1] = v };
Quadric({x=1}) = {
  Qset(0, 0, x);
  for (n = 1, length(Q)-1, for (g = 0, gmax(n),
    my(t1 = (1+x)*(2*n-1)/3 * Qget(n-1, g),
       t2 = (2*n-3)*(2*n-2)*(2*n-1)/12 * Qget(n-2, g-1),
       t3 = 1/2 * sum(k = 1, n-1, sum(i = 0, g,
       (2*k-1) * (2*(n-k)-1) * Qget(k-1, i) * Qget(n-k-1, g-i))));
    Qset(n, g, (t1 + t2 + t3) * 6/(n+1))));
};
Quadric('x + O('x^(F+1)));
concat(vector(N+2-F, n, vector(1 + gmax(n-1), g, polcoeff(Qget(n+F-2, g-1), F))))

A346702 The a(n)-th composition in standard order is the odd bisection of the n-th composition in standard order.

Original entry on oeis.org

0, 1, 2, 1, 4, 2, 1, 3, 8, 4, 2, 5, 1, 3, 6, 3, 16, 8, 4, 9, 2, 5, 10, 5, 1, 3, 6, 3, 12, 6, 3, 7, 32, 16, 8, 17, 4, 9, 18, 9, 2, 5, 10, 5, 20, 10, 5, 11, 1, 3, 6, 3, 12, 6, 3, 7, 24, 12, 6, 13, 3, 7, 14, 7, 64, 32, 16, 33, 8, 17, 34, 17, 4, 9, 18, 9, 36, 18

Offset: 0

Gus Wiseman, Aug 12 2021

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

a(n) is the row number in A066099 of the odd bisection of the n-th row of A066099.

			Composition number 741 in standard order is (2,1,1,3,2,1), with odd bisection (2,1,2), which is composition number 22 in standard order, hence a(741) = 22.

Length of the a(n)-th standard composition is A000120(n)/2 rounded up.
Positions of 1's are A003945.
Positions of 2's (and zero) are A083575.
Sum of the a(n)-th standard composition is A209281(n+1).
Positions of first appearances are A290259.
The version for prime indices is A346703.
The version for even bisection is A346705, with sums A346633.
A000120 and A080791 count binary digits 1 and 0, with difference A145037.
A011782 counts compositions.
A029837 gives length of binary expansion.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A345197 counts compositions by sum, length, and alternating sum.
Cf. A000009, A000302, A000346, A025047, A088218, A124754, A294175, A346697 (reverse: A346699).

Table[Total[2^Accumulate[Reverse[First/@Partition[Append[ Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse,0],2]]]]/2,{n,0,100}]

A029837(a(n)) = A209281(n).

cp's OEIS Frontend

A053979 Triangle T(n,k) giving number of rooted maps regardless of genus with n edges and k nodes (n >= 0, k = 1..n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A049235 Sum of balls on the lawn for the s=3 tennis ball problem.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A068551 a(n) = 4^n - binomial(2*n,n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A138158 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and path length k; 0 <= k <= n(n+1)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A380237 Number of sensed planar maps with n vertices and 2 faces.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

A018218 Sum(C(j)*(n-j)*4^(n-j-1),j=0..n-1), C = Catalan numbers.

Views

Author

Keywords

Links

Programs

Magma

Mathematica

Formula

A033504 a(n)/4^n is the expected number of tosses of a coin required to obtain n+1 heads or n+1 tails.

Views

Author

Keywords

Comments

Examples

References

A018218 Sum(C(j)(n-j)4^(n-j-1),j=0..n-1), C = Catalan numbers.