login
a(0) = 1; for n > 0, a(n) = 2^(n-1)*n!.
(Formerly M3604 N1463)
76

%I M3604 N1463 #204 Apr 26 2024 06:13:15

%S 1,1,4,24,192,1920,23040,322560,5160960,92897280,1857945600,

%T 40874803200,980995276800,25505877196800,714164561510400,

%U 21424936845312000,685597979049984000,23310331287699456000,839171926357180416000,31888533201572855808000,1275541328062914232320000

%N a(0) = 1; for n > 0, a(n) = 2^(n-1)*n!.

%C Consider the set of n-1 odd numbers from 3 to 2n-1, i.e., {3, 5, ..., 2n-1}. There are 2^(n-1) subsets from {} to {3, 5, 7, ..., 2n-1}; a(n) = the sum of the products of terms of all the subsets. (Product for empty set = 1.) a(4) = 1 + 3 + 5 + 7 + 3*5 + 3*7 + 5*7 + 3*5*7 = 192. - _Amarnath Murthy_, Sep 06 2002

%C Also, a(n-1) is the number of ways to lace a shoe that has n pairs of eyelets such that there is a straight (horizontal) connection between all adjacent eyelet pairs. - _Hugo Pfoertner_, Jan 27 2003

%C This is also the denominator of the integral of ((1-x^2)^(n-1/2))/(Pi/4) where x ranges from 0 to 1. The numerator is (2*x)!/(x!*2^x). In both cases n starts at 1. E.g., the denominator when n=3 is 24 and the numerator is 15. - Al Hakanson (hawkuu(AT)excite.com), Oct 17 2003

%C Number of ways to use the elements of {1,...,n} once each to form a sequence of nonempty lists. - Bob Proctor, Apr 18 2005

%C Row sums of A131222. - _Paul Barry_, Jun 18 2007

%C Number of rotational symmetries of an n-cube. The number of all symmetries of an n-cube is A000165. See Egan for signed cycle notation, other notes, tables and animation. - _Jonathan Vos Post_, Nov 28 2007

%C 1, 4, 24, 192, 1920, ... is the exponential (or binomial) convolution of 1, 1, 3, 15, 105, ... and 1, 3, 15, 105, 945 (A001147). - _David Callan_, Jul 25 2008

%C The n-th term of this sequence is the number of regions into which n-dimensional space is partitioned by the 2n hyperplanes of the form x_i=x_j and x_i=-x_j (for 1 <= i < j <= n). - Edward Scheinerman (ers(AT)jhu.edu), May 04 2008

%C a(n) is the number of ways to seat n churchgoers into pews and then linearly order the nonempty pews. - _Geoffrey Critzer_, Mar 16 2009

%C Equals the row sums of A156992. - _Geoffrey Critzer_, Mar 05 2010

%C From _Gary W. Adamson_, May 17 2010: (Start)

%C Next term in the series = (1, 3, 5, 7, ...) dot (1, 1, 4, 24, ...);

%C e.g., a(5) = 1920 = (1, 3, 5, 7, 9) dot (1, 1, 4, 24, 192) = (1 + 3 + 20 + 168 + 1728). (End)

%C a(n) is the number of ways to represent the permutations of {1,2,...,n} in cycle notation, taking into account that we can permute the order of all cycles and also have k ways to write a length-k cycle.

%C For positive n, a(n) equals the permanent of the n X n matrix with consecutive integers 1 to n along the main diagonal, consecutive integers 2 to n along the subdiagonal, and 1's everywhere else. - _John M. Campbell_, Jul 10 2011

%C From _Dennis P. Walsh_, Nov 26 2011: (Start)

%C Number of ways to arrange n books on consecutive bookshelves.

%C To derive a(n) = n!2^(n-1), we note that there are n! ways to arrange the books in a row. Then there are 2^(n-1) ways to place the arranged books on consecutive shelves since there are 2^(n-1) ordered partitions of n. Hence a(n) = n!2^(n-1).

%C Also, a(n) is the number of ways to stack n different alphabet blocks in contiguous stacks.

%C Furthermore, a(n) is the number of labeled, rooted forests that have (i) each root labeled larger than any nonroot, (ii) each root having exactly one child node, (iii) n non-root nodes, and (iv) each node in the forest with at most one child node.

%C Example: a(3)=24 since there are 24 arrangements of books b1, b2, and b3 on consecutive shelves, namely, |b1 b2 b3|, |b1 b3 b2|, |b2 b1 b3|, |b2 b3 b1|, |b3 b1 b2|, |b3 b2 b1|, |b1 b2||b3|, |b2 b1| |b3|, |b1 b3||b2|, |b3 b1||b2|, |b2 b3||b1|, |b3 b2||b1|, |b1||b2 b3|,|b1||b3 b2|, |b2||b1 b3|, |b2||b3 b1|, |b3||b1 b2|, |b3||b2 b1|, |b1||b2||b3|, |b1||b3||b2|, |b2||b1||b3|, |b2||b3||b1|, |b3||b1||b2|, and |b3||b2||b1|.

%C (End)

%C For n > 3, a(n) is the order of the Coxeter group (also called Weyl group) of type D_n. - _Tom Edgar_, Nov 05 2013

%D N. Bourbaki, Groupes et alg. de Lie, Chap. 4, 5, 6, p. 257.

%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, Eq. (4.2.2.26)

%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="/A002866/b002866.txt">Table of n, a(n) for n = 0..100</a>

%H Ofek Lauber Bonomo and Shlomi Reuveni, <a href="https://arxiv.org/abs/1905.02170">Occupancy correlations in the asymmetric simple inclusion process</a>, arXiv:1905.02170 [cond-mat.stat-mech], 2019.

%H J.-P. Bultel and A. Chouria, J.-G. Luque and O. Mallet, <a href="https://arxiv.org/abs/1302.5815">Word symmetric functions and the Redfield-Polya theorem</a>, Accepted to FPSAC 2013, 2013; arXiv:1302.5815 [math.CO], 2013.

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. 3 (2000), #00.1.5.

%H Greg Egan, <a href="http://gregegan.customer.netspace.net.au/APPLETS/29/HypercubeNotes.html">Hypercube Mathematical Details</a>, revised Apr 22 2007.

%H Joël Gay and Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.

%H W. S. Gray and M. Thitsa, <a href="http://dx.doi.org/10.1109/SSST.2013.6524939">System Interconnections and Combinatorial Integer Sequences</a>, in: 2013 45th Southeastern Symposium on System Theory (SSST).

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]

%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=121">Encyclopedia of Combinatorial Structures 121</a>.

%H Victor Meally, <a href="/A002868/a002868.pdf">Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.</a>

%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

%H Norihiro Nakashima and Shuhei Tsujie, <a href="https://arxiv.org/abs/1904.09748">Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species</a>, arXiv:1904.09748 [math.CO], 2019.

%H J.-C. Novelli and J.-Y. Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv:1403.5962 [math.CO], 2014.

%H OEIS Wiki, <a href="http://oeis.org/wiki/Sorting_numbers">Sorting numbers</a>.

%H Hugo Pfoertner, <a href="http://www.randomwalk.de/shoelace/strlace.txt">Counting straight shoe lacings. FORTRAN program and results</a>.

%H Robert A. Proctor, <a href="http://arxiv.org/abs/math/0606404">Let's Expand Rota's Twelvefold Way For Counting Partitions!</a>, arXiv:math/0606404 [math.CO], 2007.

%H N. J. A. Sloane and Thomas Wieder, <a href="https://arxiv.org/abs/math/0307064">The Number of Hierarchical Orderings</a>, arXiv:math/0307064 [math.CO], 2003.

%H N. J. A. Sloane and Thomas Wieder, <a href="https://doi.org/10.1007/s11083-004-9460-9">The Number of Hierarchical Orderings</a>, Order 21 (2004), 83-89.

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%H <a href="/index/La#lacings">Index entries for sequences related to shoe lacings</a>

%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>

%F E.g.f.: (1 - x)/(1 - 2*x). - _Paul Barry_, May 26 2003, corrected Jun 18 2007

%F a(n) = n! * A011782(n).

%F For n >= 1, a(n) = Sum_{i=0..m/2} (-1)^i * binomial(n, i) * (n-2*i)^n. - Yong Kong (ykong(AT)curagen.com), Dec 28 2000

%F a(n) ~ 2^(1/2) * Pi^(1/2) * n^(3/2) * 2^n * e^(-n) * n^n*{1 + 13/12*n^(-1) + ...}. - Joe Keane (jgk(AT)jgk.org), Nov 23 2001

%F E.g.f. is B(A(x)), where B(x) = 1/(1 - x) and A(x) = x/(1 - x). - _Geoffrey Critzer_, Mar 16 2009

%F a(n) = Sum_{k=1..n} A156992(n,k). - _Dennis P. Walsh_, Nov 26 2011

%F a(n+1) = Sum_{k=0..n} A132393(n,k)*2^(n+k), n>0. - _Philippe Deléham_, Nov 28 2011

%F G.f.: 1 + x/(1 - 4*x/(1 - 2*x/(1 - 6*x/(1 - 4*x/(1 - 8*x/(1 - 6*x/(1 - 10*x/(1 - ... (continued fraction). - _Philippe Deléham_, Nov 29 2011

%F a(n) = 2*n*a(n-1) for n >= 2. - _Dennis P. Walsh_, Nov 29 2011

%F G.f.: (1 + 1/G(0))/2, where G(k)= 1 + 2*x*k - 2*x*(k + 1)/G(k+1); (continued fraction, Euler's 1st kind, 1-step). - _Sergei N. Gladkovskii_, Aug 02 2012

%F G.f.: 1 + x/Q(0), m=4, where Q(k) = 1 - m*x*(2*k + 1) - m*x^2*(2*k + 1)*(2*k + 2)/(1 - m*x*(2*k + 2) - m*x^2*(2*k + 2)*(2*k + 3)/Q(k+1)) ; (continued fraction). - _Sergei N. Gladkovskii_, Sep 23 2013

%F G.f.: 1 + x/(G(0) - x), where G(k) = 1 + x*(k+1) - 4*x*(k + 1)/(1 - x*(k + 2)/G(k+1)); (continued fraction). - _Sergei N. Gladkovskii_, Dec 24 2013

%F a(n) = Sum_{k=0..n} L(n,k)*k!; L(n,k) are the unsigned Lah numbers. - _Peter Luschny_, Oct 18 2014

%F a(n) = round(Sum_{k >= 1} log(k)^n/k^(3/2))/4, for n >= 1, which is related to the n-th derivative of zeta(x) evaluated at x = 3/2. - _Richard R. Forberg_, Jan 02 2015

%F a(n) = n!*hypergeom([-n+1], [], -1)) for n>=1. - _Peter Luschny_, Apr 08 2015

%F From _Amiram Eldar_, Aug 04 2020: (Start)

%F Sum_{n >= 0} 1/a(n) = 2*sqrt(e) - 1.

%F Sum_{n >= 0} (-1)^n/a(n) = 2/sqrt(e) - 1. (End)

%e For the shoe lacing: with the notation introduced in A078602 the a(3-1) = 4 "straight" lacings for 3 pairs of eyelets are: 125346, 125436, 134526, 143526. Their mirror images 134256, 143256, 152346, 152436 are not counted.

%e a(3) = 24 because the 24 rotations of a three-dimensional cube fall into four distinct classes:

%e (i) the identity, which leaves everything fixed;

%e (ii) 9 rotations which leave the centers of two faces fixed, comprising rotations of 90, 180 and 270 degrees for each of 3 pairs of faces;

%e (iii) 6 rotations which leave the centers of two edges fixed, comprising rotations of 180 degrees for each of 6 pairs of edges;

%e (iv) 8 rotations which leave two vertices fixed, comprising rotations of 120 and 240 degrees for each of 4 pairs of vertices. For an n-cube, rotations can be more complex. For example, in 4 dimensions a rotation can either act in a single plane, such as the x-y plane, while leaving any vectors orthogonal to that plane unchanged, or it can act in two orthogonal planes, performing rotations in both and leaving no vectors fixed. In higher dimensions, there will be room for more planes and more choices as to the number of planes in which a given rotation acts.

%p A002866 := n-> `if`(n=0,1,2^(n-1)*n!):

%p with(combstruct); SeqSeqL := [S, {S=Sequence(U,card >= 1), U=Sequence(Z,card >=1)},labeled];

%p seq(ceil(count(Subset(n))*count(Permutation(n))/2),n=0..17); # _Zerinvary Lajos_, Oct 16 2006

%p G(x):=(1-x)/(1-2*x): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1],x) od:x:=0:seq(f[n],n=0..17); # _Zerinvary Lajos_, Apr 04 2009

%t Join[{1},Table[2^(n-1) n!,{n,25}]] (* _Harvey P. Dale_, Sep 27 2013 *)

%t a[n_] := (-1)^n Hypergeometric2F1Regularized[1, -n, 2 - n, 2];

%t Table[a[n], {n, 0, 20}] (* _Peter Luschny_, Apr 26 2024 *)

%o (FORTRAN) See Pfoertner link.

%o (PARI) a(n)=if(n,n!<<(n-1),1) \\ _Charles R Greathouse IV_, Jan 13 2012

%o (PARI) a(n) = if(n == 0, 1, 2^(n-1)*n!);

%o vector(25, n, a(n-1)) \\ _Altug Alkan_, Oct 18 2015

%o (Magma) [1] cat [2^(n-1)*Factorial(n): n in [1..25]]; // _G. C. Greubel_, Jun 13 2019

%o (Sage) [1] + [2^(n-1)*factorial(n) for n in (1..25)] # _G. C. Greubel_, Jun 13 2019

%Y Cf. A028371, A078602, A078698, A078702, A156992.

%Y Bisections give A002671 and A274304.

%Y Appears in A167584 (n >= 1); equals the row sums of A167594 (n >= 1). - _Johannes W. Meijer_, Nov 12 2009

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_