%I M4161 N1729 #222 Oct 16 2024 21:24:24
%S 0,1,6,24,80,240,672,1792,4608,11520,28160,67584,159744,372736,860160,
%T 1966080,4456448,10027008,22413312,49807360,110100480,242221056,
%U 530579456,1157627904,2516582400,5452595200,11777605632,25367150592,54492397568,116769423360,249644974080,532575944704
%N a(n) = n*(n+1)*2^(n-2).
%C Number of 2-dimensional faces in (n+1)-dimensional hypercube; also number of 4-cycles in the (n+1)-dimensional hypercube. - _Henry Bottomley_, Apr 14 2000
%C Also the number of edges in the (n+1)-halved cube graph. - _Eric W. Weisstein_, Jun 21 2017
%C From _Philippe Deléham_, Apr 28 2004: a(n) is the sum, over all nonempty subsets E of {1, 2, ..., n}, of all elements of E. E.g., a(3) = 24: the nonempty subsets are {1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3} and 1 + 2 + 3 + 1 + 2 + 1 + 3 + 2 + 3 + 1 + 2 + 3 = 24.
%C Equivalently, sum of all nodes (except the last one, equal to n+1) of all integer compositions of n+1. - _Olivier Gérard_, Oct 22 2011
%C The inverse binomial transform of a(n-k) for k=-1..4 gives A001844, A000290, A000217(n-1), A002620(n-1), A008805(n-4), A000217 interspersed with 0's. - _Michael Somos_, Jul 18 2003
%C Take n points on a finite line. They all move with the same constant speed; they instantaneously change direction when they collide with another; and they fall when they quit the line. a(n-1) is the total number of collisions before falling when the initials directions are the 2^n possible. The mean number of collisions is then n(n-1)/8. E.g., a(1)=0 before any collision is possible. a(2)=1 because there is a collision only if the initials directions are, say, right-left. - Emmanuel Moreau, Feb 11 2006
%C Also number of pericondensed hexagonal systems with n hexagons. For example, if n=5 then the number of pericondensed hexagonal systems with n hexagons is 24. - _Parthasarathy Nambi_, Sep 06 2006
%C If X_1,X_2,...,X_n is a partition of a 2n-set X into 2-blocks then, for n>1, a(n-1) is equal to the number of (n+2)-subsets of X intersecting each X_i (i=1,2,...,n). - _Milan Janjic_, Jul 21 2007
%C Number of n-permutations of 3 objects u,v,w, with repetition allowed, containing exactly two u's. Example: a(2)=6 because we have uuw, uuv, uwu, uvu, wuu and vuu. - _Zerinvary Lajos_, Dec 29 2007
%C For n>0 where [0]={}, the empty set, and [n]={1,2,...n} a(n) is the number of ways to separate [n-1] into three non-overlapping intervals (allowed to be empty) and then choose a subset from each interval. - _Geoffrey Critzer_, Feb 07 2009
%C Form an array with m(n,0) = m(0,n) = n^2 and m(i,j) = m(i-1,j-1) + m(i-1,j). Then m(1,n) = A001844(n) and m(n,n) = a(n). - _J. M. Bergot_, Nov 07 2012
%C The sum of the number of inversions of all sequences of zeros and ones with length n+1. - _Evan M. Bailey_, Dec 09 2020
%D 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.
%D 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.
%D A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001788/b001788.txt">Table of n, a(n) for n = 0..500</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H H. J. Brothers, <a href="http://www.brotherstechnology.com/math/pascals-prism.html">Pascal's Prism: Supplementary Material</a>.
%H Geoffrey Critzer, <a href="https://esirc.emporia.edu/handle/123456789/3595">Combinatorics of Vector Spaces over Finite Fields</a>, Master's thesis, Emporia State University, 2018.
%H Robert Davis and Greg Simay, <a href="https://arxiv.org/abs/2001.11089">Further Combinatorics and Applications of Two-Toned Tilings</a>, arXiv:2001.11089 [math.CO], 2020.
%H Herbert Izbicki, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN00247686X">Über Unterbäume eines Baumes</a>, Monatshefte fur Mathematik, Vol. 74 (1970), pp. 56-62.
%H Milan Janjic, <a href="https://pmf.unibl.org/wp-content/uploads/2017/10/enumfor.pdf">Two Enumerative Functions</a>.
%H Milan Janjic and Boris Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv 1301.4550 [math.CO], 2013.
%H C. W. Jones, J. C. P. Miller, J. F. C. Conn, and R. C. Pankhurst, <a href="https://doi.org/10.1017/S0080454100006579">Tables of Chebyshev polynomials</a>, Proc. Roy. Soc. Edinburgh. Sect. A., Vol. 62, No. 2 (1946), pp. 187-203.
%H Han Mao Kiah, Alexander Vardy, and Hanwen Yao, <a href="https://arxiv.org/abs/2212.09952">Efficient Algorithms for the Bee-Identification Problem</a>, arXiv:2212.09952 [cs.IT], 2022.
%H Duško Letić, Nenad Cakić, Branko Davidović, Ivana Berković and Eleonora Desnica, <a href="http://dx.doi.org/10.1186/1687-1847-2011-60">Some certain properties of the generalized hypercubical functions</a>, Advances in Difference Equations, Vol. 2011 (2011), Article 60.
%H Mircea Merca, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Merca2/merca7.html">A Special Case of the Generalized Girard-Waring Formula</a>, J. Integer Sequences, Vol. 15 (2012), Article 12.5.7.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H Lara Pudwell, Nathan Chenette and Manda Riehl, <a href="http://faculty.valpo.edu/lpudwell/slides/JMM2020_Pudwell.pdf">Statistics on Hypercube Orientations</a>, AMS Special Session on Experimental and Computer Assisted Mathematics, Joint Mathematics Meetings (Denver 2020).
%H John Riordan and N. J. A. Sloane, <a href="/A003471/a003471_1.pdf">Correspondence, 1974</a>.
%H R. Tosic, D. Masulovic, I. Stojmenovic, J. Brunvoll, B. N. Cyvin and S. J. Cyvin, <a href="http://dx.doi.org/10.1021/ci00024a002">Enumeration of polyhex hydrocarbons to h = 17</a>, J. Chem. Inf. Comput. Sci., Vol. 35, No. 2 (1995), pp. 181-187.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCount.html">Edge Count</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IdempotentNumber.html">Idempotent Number</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HalvedCubeGraph.html">Halved Cube Graph</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>.
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials</a>.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-12,8).
%F G.f.: x/(1-2*x)^3.
%F E.g.f.: x*(1 + x)*exp(2*x).
%F a(n) = 2*a(n-1) + n*2^(n-1) = 2*a(n-1) + A001787(n).
%F a(n) = A038207(n+1,2).
%F a(n) = A055252(n, 2).
%F a(n) = Sum_{i=1..n} i^2 * binomial(n, i): binomial transform of A000290. - Yong Kong, Dec 26 2000
%F a(n) = Sum_{j=0..n} binomial(n+1,j)*(n+1-j)^2. - _Zerinvary Lajos_, Aug 22 2006
%F If the leading 0 is deleted, the binomial transform of A001844: (1, 5, 13, 25, 41, ...); = double binomial transform of [1, 4, 4, 0, 0, 0, ...]. - _Gary W. Adamson_, Sep 02 2007
%F a(n) = Sum_{1<=i<=k<=n} (-1)^(i+1)*i^2*binomial(n+1,k+i)*binomial(n+1,k-i). - _Mircea Merca_, Apr 09 2012
%F a(0)=0, a(1)=1, a(2)=6, a(n) = 6*a(n-1) - 12*a(n-2) + 8*a(n-3). - _Harvey P. Dale_, Jul 16 2013
%F a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} (k+1) * C(n-1,i). - _Wesley Ivan Hurt_, Sep 20 2017
%F From _Amiram Eldar_, Jan 05 2022: (Start)
%F Sum_{n>=1} 1/a(n) = 4*(1-log(2)).
%F Sum_{n>=1} (-1)^(n+1)/a(n) = 12*log(3/2) - 4. (End)
%e The nodes of an integer composition are the partial sums of its elements, seen as relative distances between nodes of a 1-dimensional polygon. For a composition of 7 such as 1+2+1+3, the nodes are 0,1,3,4,7. Their sum (without the last node) is 8. The sum of all nodes of all 2^(7-1)=64 integer compositions of 7 is 672.
%p A001788 := n->n*(n+1)*2^(n-2);
%p A001788:=-1/(2*z-1)**3; # _Simon Plouffe_ in his 1992 dissertation; gives sequence without initial zero
%t CoefficientList[Series[x/(1-2x)^3, {x,0,30}], x]
%t Table[n*(n+1)*2^(n-2), {n,0,30}]
%t With[{n = 30}, Join[{0}, Times @@@ Thread[{Accumulate[Range[n]], 2^Range[0, n - 1]}]]] (* _Harvey P. Dale_, Jul 16 2013 *)
%t LinearRecurrence[{6, -12, 8}, {0, 1, 6}, 30] (* _Harvey P. Dale_, Jul 16 2013 *)
%o (PARI) a(n)=if(n<0,0,2^n*n*(n+1)/4)
%o (PARI) A001788_upto(n)=Vec(x/(1-2*x)^3+O(x^n),-n) \\ for illustration. - _M. F. Hasler_, Oct 05 2024
%o (Sage) [n if n < 2 else n * (n + 1) * 2**(n - 2) for n in range(28)] # _Zerinvary Lajos_, Mar 10 2009
%o (Haskell)
%o a001788 n = if n < 2 then n else n * (n + 1) * 2 ^ (n - 2)
%o a001788_list = zipWith (*) a000217_list $ 1 : a000079_list
%o -- _Reinhard Zumkeller_, Jul 11 2014
%o (Magma) [n*(n+1)*2^(n-2): n in [0..30]]; // _G. C. Greubel_, Aug 27 2019
%o (GAP) List([0..30], n-> n*(n+1)*2^(n-2)); # _G. C. Greubel_, Aug 27 2019
%Y Cf. A000079, A001787, A001789, A001793 (sum of all nodes of integer compositions, n included).
%Y Cf. A001844, A038207, A290031 (6-cycles).
%Y Row sums of triangle A094305.
%Y Sequences similar to the form q^(n-2)*binomial(n, 2): A000217 (q=1), this sequence (q=2), A027472 (q=3), A038845 (q=4), A081135 (q=5), A081136 (q=6), A027474 (q=7), A081138 (q=8), A081139 (q=9), A081140 (q=10), A081141 (q=11), A081142 (q=12), A027476 (q=15).
%K nonn,easy,nice,changed
%O 0,3
%A _N. J. A. Sloane_