A033504 -id:A033504 - cp's OEIS frontend

A000346 a(n) = 2^(2n+1) - binomial(2n+1, n+1).

1, 5, 22, 93, 386, 1586, 6476, 26333, 106762, 431910, 1744436, 7036530, 28354132, 114159428, 459312152, 1846943453, 7423131482, 29822170718, 119766321572, 480832549478, 1929894318332, 7744043540348, 31067656725032, 124613686513778, 499744650202436

Offset: 0

N. J. A. Sloane, Wolfdieter Lang

Also a(n) = 2nd elementary symmetric function of binomial(n,0), binomial(n,1), ..., binomial(n,n).
Also a(n) = one half the sum of the heights, over all Dyck (n+2)-paths, of the vertices that are at even height and terminate an upstep. For example with n=1, these vertices are indicated by asterisks in the 5 Dyck 3-paths: UU*UDDD, UU*DU*DD, UDUU*DD, UDUDUD, UU*DDUD, yielding a(1)=(2+4+2+0+2)/2=5. - David Callan, Jul 14 2006
Hankel transform is (-1)^n*(2n+1); the Hankel transform of sum(k=0..n, C(2*n,k) ) - C(2n,n) is (-1)^n*n. - Paul Barry, Jan 21 2007
Row sums of the Riordan matrix (1/(1-4x),(1-sqrt(1-4x))/2) (A187926). - Emanuele Munarini, Mar 16 2011
From Gus Wiseman, Jul 19 2021: (Start)
For n > 0, a(n-1) is also the number of integer compositions of 2n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A053754 /\ A345921. For example, the a(3-1) = 22 compositions of 6 are:
  (6)  (1,5)  (1,1,4)  (1,1,1,3)  (1,1,1,1,2)
       (2,4)  (1,2,3)  (1,1,3,1)  (1,1,2,1,1)
       (4,2)  (1,4,1)  (1,2,1,2)  (2,1,1,1,1)
       (5,1)  (2,1,3)  (1,3,1,1)
              (2,2,2)  (2,1,2,1)
              (3,1,2)  (3,1,1,1)
              (3,2,1)
              (4,1,1)
(End)

			G.f. = 1 + 5*x + 22*x^2 + 93*x^3 + 386*x^4 + 1586*x^5 + 6476*x^6 + ...

T. Myers and L. Shapiro, Some applications of the sequence 1, 5, 22, 93, 386, ... to Dyck paths and ordered trees, Congressus Numerant., 204 (2010), 93-104.
D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..500
R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
Vijay Balasubramanian, Javier M. Magan, and Qingyue Wu, A Tale of Two Hungarians: Tridiagonalizing Random Matrices, arXiv:2208.08452 [hep-th], 2022.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
E. A. Bender, E. R. Canfield and R. W. Robinson, The enumeration of maps on the torus and the projective plane, Canad. Math. Bull., 31 (1988), 257-271; see p. 270.
D. E. Davenport, L. K. Pudwell, L. W. Shapiro and L. C. Woodson, The Boundary of Ordered Trees, 2014.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 185
R. K. Guy, Letter to N. J. A. Sloane
Toufik Mansour and José L. Ramirez, Enumerations of polyominoes determined by Fuss-Catalan words, Australas. J. Combin. 81 (3) (2021) 447-457, table 1.
Mircea Merca, A Special Case of the Generalized Girard-Waring Formula, J. Integer Sequences, Vol. 15 (2012), Article 12.5.7. - From _N. J. A. Sloane_, Nov 25 2012
D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (A_n for s=2).
Vera Posch, Correlators in Matrix Models, Master Thesis, Uppsala Univ. (Sweden 2023). See p. 44.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
W. T. Tutte, On the enumeration of planar maps. Bull. Amer. Math. Soc. 74 1968 64-74.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Thy B13 (1972), 122-141 and 192-218 (eq. 5, b=1).
N. J. A. Sloane, Notes

Cf. A000108, A014137, A014318. A column of A058893. Subdiagonal of A053979.
Bisection of A058622 and (possibly) A007008.
Cf. A045621, A068551.
Cf. A033504, A038806, A055217, A069731.
Even bisection of A294175 (without the first two terms).
The following relate to compositions of 2n with alternating sum k.
- The k > 0 case is counted by A000302.
- The k <= 0 case is counted by A000302.
- The k != 0 case is counted by A000346 (this sequence).
- The k = 0 case is counted by A001700 or A088218.
- The k < 0 case is counted by A008549.
- The k >= 0 case is counted by A114121.
A011782 counts compositions.
A086543 counts partitions with nonzero alternating sum (bisection: A182616).
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001791, A007318, A025047, A027306, A032443, A053754, A120452, A163493, A239830, A344611, A345921.

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

seq(2^(2*n+1)-binomial(2*n,n)*(2*n+1)/(n+1), n=0..12); # Emanuele Munarini, Mar 16 2011

Table[2^(2n+1)-Binomial[2n,n](2n+1)/(n+1),{n,0,20}] (* Emanuele Munarini, Mar 16 2011 *)
a[ n_] := If[ n<-4, 0, (4^(n + 1) - Binomial[2 n + 2, n + 1]) / 2]; (* Michael Somos, Jan 25 2014 *)

makelist(2^(2*n+1)-binomial(2*n,n)*(2*n+1)/(n+1),n,0,12); /* Emanuele Munarini, Mar 16 2011 */

{a(n) = if( n<-4, 0, n++; (2^(2*n) - binomial(2*n, n)) / 2)}; /* Michael Somos, Jan 25 2014 */

G.f.: c(x)/(1-4x), c(x) = g.f. of Catalan numbers.
Convolution of Catalan numbers and powers of 4.
Also one half of convolution of central binomial coeffs. A000984(n), n=0, 1, 2, ... with shifted central binomial coeffs. A000984(n), n=1, 2, 3, ...
a(n) = A045621(2n+1) = (1/2)*A068551(n+1).
a(n) = Sum_{k=0..n} A000984(k)*A001700(n-k). - Philippe Deléham, Jan 22 2004
a(n) = Sum_{k=0..n+1} binomial(n+k, k-1)2^(n-k+1). - Paul Barry, Nov 13 2004
a(n) = Sum_{i=0..n} binomial(2n+2, i). See A008949. - Ed Catmur (ed(AT)catmur.co.uk), Dec 09 2006
a(n) = Sum_{k=0..n+1, C(2n+2,k)} - C(2n+2,n+1). - Paul Barry, Jan 21 2007
Logarithm g.f. log(1/(2-C(x)))=sum(n>0, a(n)/n*x^n), C(x)=(1-sqrt(1-4*x))/2x (A000108). - Vladimir Kruchinin, Aug 10 2010
D-finite with recurrence: (n+3) a(n+2) - 2(4n+9) a(n+1) + 8(2n+3) a(n) = 0. - Emanuele Munarini, Mar 16 2011
E.g.f.:exp(2*x)*(2*exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x)).
This is the first derivative of exp(2*x)*(exp(2*x) - BesselI(0,2*x))/2. See the e.g.f. of A032443 (which has a plus sign) and the remarks given there. - Wolfdieter Lang, Jan 16 2012
a(n) = Sum_{0<=iMircea Merca, Apr 05 2012
A000346 = A004171 - A001700. See A032443 for the sum. - M. F. Hasler, Jan 02 2014
0 = a(n) * (256*a(n+1) - 224*a(n+2) + 40*a(n+3)) + a(n+1) * (-32*a(n+1) + 56*a(n+2) - 14*a(n+3)) + a(n+2) * (-2*a(n+2) + a(n+3)) if n>-5. - Michael Somos, Jan 25 2014
REVERT transform is [1,-5,28,-168,1056,...] = alternating signed version of A069731. - Michael Somos, Jan 25 2014
Convolution square is A038806. - Michael Somos, Jan 25 2014
BINOMIAL transform of A055217(n-1) is a(n-1). - Michael Somos, Jan 25 2014
(n+1) * a(n) = A033504(n). - Michael Somos, Jan 25 2014
Recurrence: (n+1)*a(n) = 512*(2*n-7)*a(n-5) + 256*(13-5*n)*a(n-4) + 64*(10*n-17)*a(n-3) + 32*(4-5*n)*a(n-2) + 2*(10*n+1)*a(n-1), n>=5. - Fung Lam, Mar 21 2014
Asymptotic approximation: a(n) ~ 2^(2n+1)*(1-1/sqrt(n*Pi)). - Fung Lam, Mar 21 2014
a(n) = Sum_{m = n+2..2*(n+1)} binomial(2*(n+1), m), n >= 0. - Wolfdieter Lang, May 22 2015
a(n) = A000302(n) + A008549(n). - Gus Wiseman, Jul 19 2021
a(n) = Sum_{j=1..n+1} Sum_{k=1..j} 2^(j-k)*binomial(n+k-1, n). - Fabio Visonà, May 04 2022
a(n) = (1/2)*(-1)^n*binomial(-(n+1), n+2)*hypergeom([1, 2*n + 3], [n + 3], 1/2). - Peter Luschny, Nov 29 2023

Corrected by Christian G. Bower

A103943 Number of unrooted two-vertex n-edge maps in the plane (planar with a distinguished outside face).

Original entry on oeis.org

1, 3, 12, 48, 196, 798, 3248, 13184, 53416, 216018, 872344, 3518496, 14177528, 57080572, 229657792, 923474944, 3711572176, 14911097514, 59883185096, 240416320928, 964947251544, 3872021946532, 15533828715232, 62306843932928

Offset: 1

Valery A. Liskovets, Mar 17 2005

V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

G. C. Greubel, Table of n, a(n) for n = 1..1000
V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36, No.4 (2006), 364-387.

Cf. A060404, A033504.

f[n_] := (2^(2n - 1) - Binomial[2n - 1, n - 1] + Binomial[n - 1, Floor[n/2]])/2; Table[ f[n], {n, 24}] (* Robert G. Wilson v, Mar 24 2005 *)
Rest[CoefficientList[Series[1/8(-2+2/(1-4x)-1/Sqrt[1-4x]+1/Sqrt[1+4x]+2/Sqrt[-1+2/(1+2x)]-Sqrt[1+Sqrt[1-16x^2]]/Sqrt[1/2-8x^2]), {x, 0, 20}], x]] (* Benedict W. J. Irwin, Aug 13 2016 *)

2a(n) = 2^(2n-1) - binomial(2n-1, n-1) + binomial(n-1, floor(n/2)).

G.f.: 1/8*(2/q^2 -2 + 1/p - 1/q + 2*sqrt(p^2-2*x)/sqrt(q^2+2*x) - sqrt(2 + 2*p*q)/(p*q)), where p=sqrt(1+4*x) and q=sqrt(1-4*x). - Benedict W. J. Irwin, Aug 13 2016

More terms from Robert G. Wilson v, Mar 24 2005

A130783 Maximum value of the n-th difference of a permutation of 0..n.

Original entry on oeis.org

0, 1, 3, 10, 25, 66, 154, 372, 837, 1930, 4246, 9516, 20618, 45332, 97140, 210664, 447661, 960858, 2028478, 4319100, 9070110, 19188796, 40122028, 84438360, 175913250, 368603716, 765561564, 1598231992, 3310623412, 6889682280, 14238676712, 29551095248

Offset: 0

R. H. Hardin, Aug 19 2007

For n>1, a(n) is also the maximum value of the n-th difference of a permutation of 1..n. - Michel Marcus, Apr 15 2017

			a(1)=1 because 0 1 has a first difference of 1;
a(2)=3 because 2 0 1 has a second difference of 3.

Fung Lam, Table of n, a(n) for n = 0..3000
F. Disanto, A. Frosini, and S. Rinaldi, Square involutions, J. Int. Seq. 14 (2011) # 11.3.5.

Cf. A000346, A033504.

A130783:=n->(n+1)*(2^n-binomial(n,floor(n/2)))/2; seq(A130783(n), n=0..50); # Wesley Ivan Hurt, Nov 25 2013

Table[(n + 1) (2^n - Binomial[n, Floor[n/2]])/2, {n, 0, 50}] (* Wesley Ivan Hurt, Nov 25 2013 *)

a(n)=(n+1)*(2^n-binomial(n,n\2))/2 \\ Charles R Greathouse IV, Jan 30 2012

from math import comb
def A130783(n): return (n+1)*((1<>1))>>1 # Chai Wah Wu, Jun 04 2024

a(n) = (n+1)*(2^(n-1)-binomial(n-1,n/2)) if n is even else ((n+1)/2)*(2^n-binomial(n,(n+1)/2)). - Vladeta Jovovic, Aug 23 2007
a(n) = (n+1)*(2^n-binomial(n,[n/2]))/2, where [x] is floor. - Graeme McRae, Jan 30 2012
G.f.: (1-sqrt((1-2*x)/(1+2*x)))/(2*(1-2*x)^2). - Vladeta Jovovic, Aug 24 2007
Asymptotics: a(n) ~ 2^(n-1)*(n+1-sqrt(2*n/Pi)). - Fung Lam, Mar 28 2014
D-finite with recurrence (n-1)*n*a(n) = 2*(n-1)*(n+1)*a(n-1) + 4*(n-2)*n*a(n-2) - 8*(n-1)*n*a(n-3). - Vaclav Kotesovec, Mar 28 2014
a(2n) = A303602(n). a(2n+1) = A033504(n). - R. J. Mathar, Nov 20 2020

A100511 a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n,j)binomial(n,k)max(j,k).

Original entry on oeis.org

0, 3, 22, 126, 652, 3190, 15060, 69356, 313624, 1398438, 6166660, 26948548, 116888232, 503811516, 2159864392, 9216445080, 39168381488, 165864540934, 700151508324, 2947120122068, 12373581565960, 51831196048212, 216659135089496, 903925011410536

Offset: 0

N. J. A. Sloane, Nov 24 2004

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000
M. Klamkin, ed., Problems in Applied Mathematics: Selections from SIAM Review, SIAM, 1990; see pp. 127-129.

Cf. A000108, A002457, A033504.

[n*(4^n +(n+1)*Catalan(n))/2: n in [0..40]]; // G. C. Greubel, Apr 01 2023

Table[n*(4^n +(n+1)*CatalanNumber[n])/2, {n,0,40}] (* G. C. Greubel, Apr 01 2023 *)

a(n) = n*2^(2*n-1) + (n/2)*binomial(2*n, n); \\ Michel Marcus, Dec 26 2017

[n*(4^n +binomial(2*n,n))/2 for n in range(41)] # G. C. Greubel, Apr 01 2023

a(n) = n*2^(2*n-1) + (n/2)*binomial(2*n, n). [Typo corrected by Ognjen Dragoljevic, Dec 26 2017]
From G. C. Greubel, Apr 01 2023: (Start)
G.f.: x*(2 + sqrt(1-4*x))/(1-4*x)^2.
E.g.f.: x*(2*exp(4*x)+ exp(2*x)*(BesselI(0, 2*x) + BesselI(1, 2*x))). (End)

Rows and columns are numbered starting with 0. Consider a pyramid (triangle) where each element is the mean value of the two elements below. Then the sum of all elements is expressed as linear combination of the elements at the base. This sequence gives the coefficients times the necessary power of 2.

cp's OEIS Frontend

A000346 a(n) = 2^(2*n+1) - binomial(2*n+1, n+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A103943 Number of unrooted two-vertex n-edge maps in the plane (planar with a distinguished outside face).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A130783 Maximum value of the n-th difference of a permutation of 0..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A100511 a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n,j)*binomial(n,k)*max(j,k).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A157933 Triangle T(i,j) such that Sum_{j=0..i} T(i,j)*x(i,j)/2^i = Sum_{k=0..i, j=0..k} x(k,j), if x(k-1,j) = (x(k,j) + x(k,j+1))/2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A000346 a(n) = 2^(2n+1) - binomial(2n+1, n+1).

A100511 a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n,j)binomial(n,k)max(j,k).