

A001787


a(n) = n*2^(n1).
(Formerly M3444 N1398)


380



0, 1, 4, 12, 32, 80, 192, 448, 1024, 2304, 5120, 11264, 24576, 53248, 114688, 245760, 524288, 1114112, 2359296, 4980736, 10485760, 22020096, 46137344, 96468992, 201326592, 419430400, 872415232, 1811939328, 3758096384, 7784628224, 16106127360, 33285996544
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Number of edges in an ndimensional hypercube.
Number of 132avoiding permutations of [n+2] containing exactly one 123 pattern.  Emeric Deutsch, Jul 13 2001
Number of ways to place n1 nonattacking kings on a 2 X 2(n1) chessboard for n >= 2.  Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 22 2001
Arithmetic derivative of 2^n: a(n) = A003415(A000079(n)).  Reinhard Zumkeller, Feb 26 2002
(1) times determinant of matrix A_{i,j} = ij, 0<=i,j<=n.
a(n) = number of ones in binary numbers 1 to 111...1 (n bits). a(n) = A000337(n)A000337(n1) for n = 2,3,... .  Emeric Deutsch, May 24 2003
The number of 2 X n 01 matrices containing n+1 1's and having no zero row or column. The number of spanning trees of the complete bipartite graph K(2,n). This is the case m = 2 of K(m,n). See A072590.  W. Edwin Clark, May 27 2003
Binomial transform of 0,1,2,3,4,5,... (A001477). Without the initial 0, binomial transform of odd numbers.
With an additional leading zero, [0,0,1,4,...] this is the binomial transform of the integers repeated A004526. Its formula is then (2^n(n1)+0^n)/4.  Paul Barry, May 20 2003
Number of zeros in all different (n+1)bit integers.  Ralf Stephan, Aug 02 2003
Final element of a summation table (as opposed to a difference table) whose first row consists of integers 0 through n (or first n+1 nonnegative integers A001477); illustrating the case n=5:
0...1...2...3...4...5
..1...3...5...7...9
....4...8...12..16
......12..20..28
........32..48
..........80 and final element is a(5)=80.  Lekraj Beedassy, Jun 03 2004
This sequence and A001871 arise in counting ordered trees of height at most k where only the rightmost branch at the root actually achieves this height and the count is by the number of edges, with k = 3 for this sequence and k = 4 for A001871.
Let R be a binary relation on the power set P(A) of a set A having n = A elements such that for all elements x,y of P(A), xRy if x is a proper subset of y and there are no z in P(A) such that x is a proper subset of z and z is a proper subset of y. Then a(n) = R.  Ross La Haye, Sep 21 2004
Number of 2 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1) and (10;1). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1<i2, j1<j2 and these elements are in same relative order as those in the triple (x,y,z).  Sergey Kitaev, Nov 11 2004
Number of subsequences 00 in all binary words of length n+1. Example: a(2)=4 because in 000,001,010,011,100,101,110,111 the sequence 00 occurs 4 times.  Emeric Deutsch, Apr 04 2005
If you expand the nfactor expression (a+1)(b+1)(c+1)...(z+1), there are a(n) variables in the result. For example, the 3factor expression (a+1)(b+1)(c+1) expands to abc+ab+ac+bc+a+b+c+1 with a(3) = 12 variables.  David W. Wilson, May 08 2005
An inverse Chebyshev transform of n^2, where g(x)>(1/sqrt(14*x^2))*g(x*c(x^2)), c(x) the g.f. of A000108.  Paul Barry, May 13 2005
Sequences A018215 and A058962 interleaved.  Graeme McRae, Jul 12 2006
The number of neverdecreasing positive integer sequences of length n with a maximum value of 2*n.  Ben Paul Thurston, Nov 13 2006
Total size of all the subsets of an nelement set. For example, a 2element set has 1 subset of size 0, 2 subsets of size 1 and 1 of size 2.  Ross La Haye, Dec 30 2006
Convolution of the natural numbers [A000027] and A045623 beginning [0,1,2,5...].  Ross La Haye, Feb 03 2007
If M is the matrix (given by rows) [2,1;0,2] then the sequence gives the (1,2) entry in M^n.  Antonio M. OllerMarcén, May 21 2007
If X_1,X_2,...,X_n is a partition of a 2nset X into 2blocks then, for n>0, a(n) is equal to the number of (n+1)subsets of X intersecting each X_i (i=1,2,...,n).  Milan Janjic, Jul 21 2007
Number of npermutations of 3 objects u,v,w, with repetition allowed, containing exactly one u. Example: a(2)=4 because we have uv, vu, uw and wu.  Zerinvary Lajos, Dec 27 2007
A member of the family of sequences defined by a(n) = n*[c(1)*...c(r)]^(n1); c(i) integer. This sequence has c(1)=2, A027471 has c(1)=3.  Ctibor O. Zizka, Feb 23 2008
a(n) is the number of ways to split {1,2,...n1} into two (possibly empty) complementary intervals {1,2,...i} and {i+1,i+2,...n1} and then select a subset from each interval.  Geoffrey Critzer, Jan 31 2009
Equals the Jacobsthal sequence A001045 convolved with A003945: (1, 3, 6, 12,...).  Gary W. Adamson, May 23 2009
Starting with offset 1 = A059570: (1, 2, 6, 14, 34,...) convolved with (1, 2, 2, 2,...).  Gary W. Adamson, May 23 2009
Equals the first left hand column of A167591.  Johannes W. Meijer, Nov 12 2009
The number of tatami tilings of an n X n square with n monomers is n*2^{n1}.  Frank Ruskey, Sep 25 2010
Under T. D. Noe's variant of the hypersigma function, this sequence gives hypersigma(2^n): a(n) = A191161(A000079(n)).  Alonso del Arte, Nov 04 2011
Number of Dyck (n+2)paths with exactly one valley at height 1 and no higher valley.  David Scambler, Nov 07 2011
Equals triangle A059260 * A016777 as a vector, where A016777 = (3n + 1): [1, 4, 7, 10, 13,...].  Gary W. Adamson, Mar 06 2012
Main transitions in systems of n particles with spin 1/2 (see A212697 with b=2).  Stanislav Sykora, May 25 2012
Let T(n,k) be the triangle with (first column) T(n,1)=2*n1 for n>=1, otherwise T(n,k) = T(n,k1) + T(n1,k1), then a(n) = T(n,n).  J. M. Bergot, Jan 17 2013
Sum of all parts of all compositions (ordered partitions) of n. The equivalent sequence for partitions is A066186.  Omar E. Pol, Aug 28 2013
Starting with a(1)=1: powers of 2 (A000079) selfconvolved.  Bob Selcoe, Aug 05 2015
Coefficients of the series expansion of the normalized Schwarzian derivative S{p(x)}/6 of the polynomial p(x) = (xx1)(xx2) with x1 + x2 = 1 (cf. A263646).  Tom Copeland, Nov 02 2015
a(n) is the number of NorthEast lattice paths from (0,0) to (n+1,n+1) that have exactly one east step below y = x1 and no east steps above y = x+1. Details can be found in Pan and Remmel's link.  Ran Pan, Feb 03 2016
Also the number of maximal and maximum cliques in the nhypercube graph for n > 0.  Eric W. Weisstein, Dec 01 2017
Let [n]={1,2,..,n}; then a(n1) is the total number of elements missing in proper subsets of [n] that contain n to form [n]. For example, for n = 3, a(2) = 4 since the proper subsets of [3] that contain 3 are {3}, {1,3}, {2,3} and the total number of elements missing in these subsets to form [3] is 4: 2 in the first subset, 1 in the second, and 1 in the third.  Enrique Navarrete, Aug 08 2020


REFERENCES

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 796.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 131.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 282.
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).


LINKS

Franklin T. AdamsWatters, Table of n, a(n) for n = 0..500
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
JeanLuc Baril, Sergey Kirgizov, Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
Douglas W. Bass and I. Hal Sudborough, Hamilton decompositions and (n/2)factorizations of hypercubes, J. Graph Algor. Appl., Vol. 7, No. 1 (2003), pp. 7998.
Harlan J. Brothers, Pascal's Prism: Supplementary Material.
David Callan, A recursive bijective approach to counting permutations containing 3letter patterns, arXiv:math/0211380 [math.CO], 2002.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Frank Ellermann, Illustration of binomial transforms
Mohamed Elkadi and Bernard Mourrain, Symbolicnumeric methods for solving polynomial equations and applications, Chap 3. of A. Dickenstein and I. Z. Emiris, eds., Solving Polynomial Equations, Springer, 2005, pp. 126168. See p. 152.
Alejandro Erickson, Frank Ruskey, Mark Schurch and Jennifer Woodcock, Auspicious Tatami Mat Arrangements, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 1921, Nha Trang, Vietnam. LNCS 6196 (2010) 288297.
Samuele Giraudo, Pluriassociative algebras I: The pluriassociative operad, Advances in Applied Mathematics, Vol. 77 (2016), pp. 142, arXiv preprint, arXiv:1603.01040 [math.CO], 2016.
Frank A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420424.
Frank A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420424. (Annotated scanned copy)
Frank A. Haight, Letter to N. J. A. Sloane, n.d.
V. E. Hoggatt, Jr., Letter to N. J. A. Sloane, Jul 06, 1976
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424434. Case n>n+1, a=0,b=1; p=4, q=4.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 408.
Milan Janjic, Two Enumerative Functions.
Milan Janjic and Boris Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013.
Milan Janjic and Boris Petkovic, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5.
C. W. Jones, J. C. P. Miller, J. F. C. Conn, R. C. Pankhurst, Tables of Chebyshev polynomials Proc. Roy. Soc. Edinburgh. Sect. A. 62, (1946). 187203.
Kenji Kimura and Saburo Higuchi, Monte Carlo estimation of the number of tatami tilings, International Journal of Modern Physics C, Vol. 27, No. 11 (2016), 1650128, arXiv preprint, arXiv:1509.05983 [condmat.statmech], 20152016, eq. (1).
Sergey Kitaev, On multiavoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Sergey Kitaev, On multiavoidance of right angled numbered polyomino patterns, University of Kentucky Research Reports (2004).
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012.
T. Y. Lam, On the diagonalization of quadratic forms, Math. Mag., 72 (1999), 231235 (see page 234).
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408419. See Eq.(3).
Dusko Letic, Nenad Cakic, Branko Davidovic, Ivana Berkovic and Eleonora Desnica, Some certain properties of the generalized hypercubical functions, Advances in Difference Equations, 2011, 2011:60.
Toufik Mansour and Armend Sh. Shabani, Bargraphs in bargraphs, Turkish Journal of Mathematics (2018) Vol. 42, Issue 5, 27632773.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Lara Pudwell, Nathan Chenette and Manda Riehl, Statistics on Hypercube Orientations, AMS Special Session on Experimental and Computer Assisted Mathematics, Joint Mathematics Meetings (Denver 2020).
Lara Pudwell, Connor Scholten, Tyler Schrock and Alexa Serrato, Noncontiguous pattern containment in binary trees, ISRN Comb. 2014, Article ID 316535, 8 p. (2014), chapter 5.2.
Aaron Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Math. and Theoret. Computer Sci., 3 (1999), 151154.
Aaron Robertson, Herbert S. Wilf and Doron Zeilberger, Permutation patterns and continued fractions, Electr. J. Combin. 6, 1999, #R38.
Jeffrey Shallit, Letter to N. J. A. Sloane Mar 14, 1979, concerning A001787, A005209, A005210, A005211.
Eric Weisstein's World of Mathematics, Hypercube.
Eric Weisstein's World of Mathematics, Hypercube Graph.
Eric Weisstein's World of Mathematics, Leibniz Harmonic Triangle.
Eric Weisstein's World of Mathematics, Maximal Clique.
Eric Weisstein's World of Mathematics, Maximum Clique.
Thomas Wieder, The number of certain kcombinations of an nset, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,4).


FORMULA

a(n) = Sum_{k=1..n} k*binomial(n, k).  Benoit Cloitre, Dec 06 2002
E.g.f.: x*exp(2x).  Paul Barry, Apr 10 2003
G.f.: x/(12*x)^2.
G.f.: x / (1  4*x / (1 + x / (1  x))).  Michael Somos, Apr 07 2012
A108666(n) = Sum_{k=0..n} binomial(n, k)^2 * a(n).  Michael Somos, Apr 07 2012
PSumSIGN transform of A053220. PSumSIGN transform is A045883. Binomial transform is A027471(n+1).  Michael Somos, Jul 10 2003
Starting at a(1)=1, INVERT transform is A002450, INVERT transform of A049072, MOBIUS transform of A083413, PSUM transform is A000337, BINOMIAL transform is A081038, BINOMIAL transform of A005408.  Michael Somos, Apr 07 2012
a(n) = 2*a(n1)+2^(n1).
a(2*n) = n*4^n, a(2*n+1) = (2*n+1)4^n.
G.f.: x/det(Ix*M) where M=[1,i;i,1], i=sqrt(1).  Paul Barry, Apr 27 2005
Starting 1, 1, 4, 12, .. this is 0^n + n2^(n1), the binomial transform of the 'pairreversed' natural numbers A004442.  Paul Barry, Jul 24 2003
Convolution of [1, 2, 4, 8, ...] with itself.  Jon Perry, Aug 07 2003
The signed version of this sequence, n(2)^(n1), is the inverse binomial transform of n(1)^(n1) (alternating sign natural numbers).  Paul Barry, Aug 20 2003
a(n1) = (Sum{k=0..n} 2^(nk1)*C(nk, k)*C(1,(k+1)/2)*(1(1)^k)/2)  0^n/4.  Paul Barry, Oct 15 2004
a(n) = Sum{k=0..floor(n/2)} binomial(n, k)(n2k)^2.  Paul Barry, May 13 2005
a(n+2) = A049611(n+2)  A001788(n).
a(n) = n! * Sum{k=0..n} 1/((k  1)!(n  k)!).  Paul Barry, Mar 26 2003
a(n+1) = Sum_{k=0..n} 4^k * A109466(n,k).  Philippe Deléham, Nov 13 2006
Row sums of A130300 starting (1, 4, 12, 32,...).  Gary W. Adamson, May 20 2007
Equals row sums of triangle A134083. Equals A002064(n) + (2^n  1).  Gary W. Adamson, Oct 07 2007
a(n) = 4*a(n1)  4*a(n2), a(0)=0, a(1)=1.  Philippe Deléham, Nov 16 2008
Sum_{n>0} 1/a(n) = 2*log(2).  Jaume Oliver Lafont, Feb 10 2009
a(n) = A000788(A000225(n)) = A173921(A000225(n)).  Reinhard Zumkeller, Mar 04 2010
a(n) = n * A011782(n).  Omar E. Pol, Aug 28 2013
a(n1) = sum(t_1+2*t_2+...+n*t_n=n, (t_1+t_2 +...+t_n1)*multinomial(t_1+t_2 +...+t_n,t_1,t_2,...,t_n)).  Mircea Merca, Dec 06 2013
a(n+1) = Sum_{r=0..n} (2*r+1)*C(n,r).  J. M. Bergot, Apr 07 2014
a(n) = A007283(n)*n/6.  Enxhell Luzhnica, Apr 16 2016
a(n) = (A000225(n) + A000337(n))/2.  Anton Zakharov, Sep 17 2016
Sum_{n>0} (1)^(n+1)/a(n) = 2*log(3/2) = 2*A016578.  Ilya Gutkovskiy, Sep 17 2016
a(n) = Sum_{k=0..n1} Sum_{i=0..n1} (i+1) * C(k,i).  Wesley Ivan Hurt, Sep 21 2017


EXAMPLE

a(2)=4 since 2314, 2341,3124 and 4123 are the only 132avoiding permutations of 1234 containing exactly one increasing subsequence of length 3.
x + 4*x^2 + 12*x^3 + 32*x^4 + 80*x^5 + 192*x^6 + 448*x^7 + ...
a(5) = 1*0 + 5*1 + 10*2 + 10*3 + 5*4 + 1*5 = 80, with 1,5,10,10,5,1 the 5th row of Pascal's triangle.  J. M. Bergot, Apr 29 2014


MAPLE

spec := [S, {B=Set(Z, 0 <= card), S=Prod(Z, B, B)}, labeled]: seq(combstruct[count](spec, size=n), n=0..29); # Zerinvary Lajos, Oct 09 2006
A001787:=1/(2*z1)^2; # Simon Plouffe in his 1992 dissertation, dropping the initial zero


MATHEMATICA

Table[Sum[Binomial[n, i] i, {i, 0, n}], {n, 0, 30}] (* Geoffrey Critzer, Mar 18 2009 *)
f[n_] := n 2^(n  1); f[Range[0, 40]] (* Vladimir Joseph Stephan Orlovsky, Feb 09 2011 *)
Array[# 2^(#  1) &, 40, 0] (* Harvey P. Dale, Jul 26 2011 *)
Join[{0}, Table[n 2^(n  1), {n, 20}]] (* Eric W. Weisstein, Dec 01 2017 *)
Join[{0}, LinearRecurrence[{4, 4}, {1, 4}, 20]] (* Eric W. Weisstein, Dec 01 2017 *)
CoefficientList[Series[x/(1 + 2 x)^2, {x, 0, 20}], x] (* Eric W. Weisstein, Dec 01 2017 *)


PROG

(PARI) {a(n) = if( n<0, 0, n * 2^(n1))}
(Haskell)
a001787 n = n * 2 ^ (n  1)
a001787_list = zipWith (*) [0..] $ 0 : a000079_list
 Reinhard Zumkeller, Jul 11 2014
(PARI) concat(0, Vec(x/(12*x)^2 + O(x^50))) \\ Altug Alkan, Nov 03 2015
(MAGMA) [n*2^(n1): n in [0..40]]; // Vincenzo Librandi, Feb 04 2016


CROSSREFS

Three other versions, essentially identical, are A085750, A097067, A118442.
Partial sums of A001792.
A058922(n+1) = 4*A001787(n).
Equals A090802(n, 1).
Column k=1 of A038207.
Row sums of A003506, A322427, A322428.
Cf. A053109, A001788, A001789, A000337, A130300, A134083, A002064, A027471, A003945, A059670, A167591, A059260, A016777, A212697, A000079, A263646.
Sequence in context: A097067 A139756 A085750 * A118442 A038592 A048776
Adjacent sequences: A001784 A001785 A001786 * A001788 A001789 A001790


KEYWORD

nonn,easy,nice,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



