login
a(n) = 2*(a(n-1) + (n-1)*a(n-2)) for n >= 2 with a(0) = 1.
(Formerly M1648 N0645)
51

%I M1648 N0645 #175 Oct 07 2024 20:27:13

%S 1,2,6,20,76,312,1384,6512,32400,168992,921184,5222208,30710464,

%T 186753920,1171979904,7573069568,50305536256,342949298688,

%U 2396286830080,17138748412928,125336396368896,936222729254912,7136574106003456,55466948299223040,439216305474605056,3540846129311916032

%N a(n) = 2*(a(n-1) + (n-1)*a(n-2)) for n >= 2 with a(0) = 1.

%C Number of solutions to the rook problem on a 2n X 2n board having a certain symmetry group (see Robinson for details).

%C Also the value of the n-th derivative of exp(x^2) evaluated at 1. - N. Calkin, Apr 22 2010

%C For n >= 1, a(n) is also the sum of the degrees of the irreducible representations of the group of n X n signed permutation matrices (described in sequence A066051). The similar sum for the "ordinary" symmetric group S_n is in sequence A000085. - Sharon Sela (sharonsela(AT)hotmail.com), Jan 12 2002

%C It appears that this is also the number of permutations of 1, 2, ..., n+1 such that each term (after the first) is within 2 of some preceding term. Verified for n+1 <= 6. E.g., a(4) = 20 because of the 24 permutations of 1, 2, 3, 4, the only ones not permitted are 1, 4, 2, 3; 1, 4, 3, 2; 4, 1, 2, 3; and 4, 1, 3, 2. - _Gerry Myerson_, Aug 06 2003

%C Hankel transform is A108400. - _Paul Barry_, Feb 11 2008

%C From _Emeric Deutsch_, Jun 19 2010: (Start)

%C Number of symmetric involutions of [2n]. Example: a(2)=6 because we have 1234, 2143, 1324, 3412, 4231, and 4321. See the Egge reference, pp. 419-420.

%C Number of symmetric involutions of [2n+1]. Example: a(2)=6 because we have 12345, 14325, 21354, 45312, 52341, and 54321. See the Egge reference, pp. 419-420.

%C (End)

%C Binomial convolution of sequence A000085: a(n) = Sum_{k=0..n} binomial(n,k)*A000085(k)*A000085(n-k). - _Emanuele Munarini_, Mar 02 2016

%C The sequence can be obtained from the infinite product of 2 X 2 matrices [(1,N); (1,1)] by extracting the upper left terms, where N = (1, 3, 5, ...), the odd integers. - _Gary W. Adamson_, Jul 28 2016

%C Apparently a(n) is the number of standard domino tableaux of size 2n, where a domino tableau is a generalized Young tableau in which all rows and columns are weakly increasing and all regions are dominos. - _Gus Wiseman_, Feb 25 2018

%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.1.4 Exer. 31.

%D L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.

%D R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).

%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="/A000898/b000898.txt">Table of n, a(n) for n=0..200</a>

%H Y. Alp and E. G. Kocer, <a href="https://doi.org/10.1007/s00025-024-02193-5">Exponential Almost-Riordan Arrays</a>, Results Math 79, 173 (2024). See page 10.

%H Arvind Ayyer, Hiranya Kishore Dey, and Digjoy Paul, <a href="https://arxiv.org/abs/2406.06036">How large is the character degree sum compared to the character table sum for a finite group?</a>, arXiv:2406.06036 [math.RT], 2024. See p. 10.

%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating functions for generating trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

%H Paul Barry, <a href="https://arxiv.org/abs/1804.05027">The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays</a>, arXiv:1804.05027 [math.CO], 2018.

%H R. A. Brualdi, Shi-Mie Ma, <a href="https://doi.org/10.1016/j.ejc.2014.08.026">Enumeration of involutions by descents and symmetric matrices</a>, Eur. J. Combin. 43 (2015) 220-228

%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. Vol. 3 (2000), #00.1.5.

%H C.-O. Chow, <a href="http://dx.doi.org/10.1016/j.disc.2006.04.018">Counting involutory, unimodal and alternating signed permutations</a>, Discr. Math. 306 (2006), 2222-2228.

%H R. Donaghey, <a href="http://dx.doi.org/10.1016/0097-3165(76)90060-1">Binomial self-inverse sequences and tangent coefficients</a>, J. Combin. Theory, Series A, 21 (1976), 155-163.

%H Eric S. Egge, <a href="http://dx.doi.org/10.1007/s00026-007-0327-9">Restricted symmetric permutations</a>, Ann. Combin., 11 (2007), 405-434.

%H Adam M. Goyt and Lara K. Pudwell, <a href="http://arxiv.org/abs/1203.3786">Avoiding colored partitions of two elements in the pattern sense</a>, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From _N. J. A. Sloane_, Sep 17 2012

%H T. Halverson and M. Reeks, <a href="http://arxiv.org/abs/1302.6150">Gelfand Models for Diagram Algebras</a>, arXiv preprint arXiv:1302.6150 [math.RT], 2013.

%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 L. C. Larson, <a href="/A000900/a000900_1.pdf">The number of essentially different nonattacking rook arrangements</a>, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181. [Annotated scan of pages 180 and 181 only]

%H Yen-chi R. Lin, <a href="http://arxiv.org/abs/1310.0988">Asymptotic Formula for Symmetric Involutions</a>, arXiv:1310.0988 [math.CO], 2013.

%H E. Lucas, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k29021h">Théorie des Nombres</a>, Gauthier-Villars, Paris, 1891, Vol. 1, p. 221.

%H E. Lucas, <a href="/A000899/a000899.pdf">Théorie des nombres</a> (annotated scans of a few selected pages)

%H J. Riordan, <a href="/A001813/a001813.pdf">Letter to N. J. A. Sloane, Feb 03 1975</a> (with notes by njas)

%H D. P. Roberts and A. Venkatesh, <a href="http://math.stanford.edu/~akshay/research/full.pdf">Hurwitz monodromy and full number fields</a>, 2014.

%H <a href="/index/He#Hermite">Index entries for sequences related to Hermite polynomials</a>

%F a(n) = Sum_{m=0..n} |A060821(n,m)| = H(n,-i)*i^n, with the Hermite polynomials H(n,x); i.e., these are row sums of the unsigned triangle A060821.

%F E.g.f.: exp(x*(x + 2)).

%F a(n) = 2 * A000902(n) for n >= 1.

%F a(n) = Sum_{k=0..n} binomial(n,2k)*binomial(2k,k)*k!*2^(n-2k). - N. Calkin, Apr 22 2010

%F Binomial transform of A047974. - _Paul Barry_, May 09 2003

%F a(n) = Sum_{k=0..n} Stirling1(n, k)*2^k*Bell(k). - _Vladeta Jovovic_, Oct 01 2003

%F From _Paul Barry_, Aug 29 2005: (Start)

%F a(n) = Sum_{k=0..floor(n/2)} A001498(n-k, k) * 2^(n-k).

%F a(n) = Sum_{k=0..n} A001498((n+k)/2, (n-k)/2) * 2^((n+k)/2) * (1+(-1)^(n-k))/2. (End)

%F For asymptotics, see the Robinson paper. [This is disputed by _Yen-chi R. Lin_. See below, Sep 30 2013.]

%F a(n) = Sum_{k=0..floor(n/2)} 2^(n-2*k) * C(n,2*k) * (2*k)!/k!. - _Paul Barry_, Feb 11 2008

%F G.f.: 1/(1 - 2*x - 2*x^2/(1 - 2*x - 4*x^2/(1 - 2*x - 6*x^2/(1 - 2*x - 8*x^2/(1 - ... (continued fraction). - _Paul Barry_, Feb 25 2010

%F E.g.f.: exp(x^2 + 2*x) = Q(0); Q(k) = 1 + (x^2 + 2*x)/(2*k + 1 - (x^2 + 2*x)*(2*k + 1)/((x^2 + 2*x) + (2*k + 2)/Q(k+1)))); (continued fraction). - _Sergei N. Gladkovskii_, Nov 24 2011

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

%F a(n) = (2*n/e)^(n/2) * exp(sqrt(2*n)) / sqrt(2*e) * (1 + sqrt(2/n)/3 + O(n^(-1)). - _Yen-chi R. Lin_, Sep 30 2013

%F 0 = a(n)*(2*a(n+1) + 2*a(n+2) - a(n+3)) + a(n+1)*(-2*a(n+1) + a(n+2)) for all n >= 0. - _Michael Somos_, Oct 23 2015

%F a(n) = Sum_{k=0..floor(n/2)} 2^(n-k)*B(n, k), where B are the Bessel numbers A100861. - _Peter Luschny_, Jun 04 2021

%e G.f. = 1 + 2*x + 6*x^2 + 20*x^3 + 76*x^4 + 312*x^5 + 1384*x^6 + 6512*x^7 + ...

%e The a(3) = 20 domino tableaux:

%e 1 1 2 2 3 3

%e .

%e 1 2 2 3 3

%e 1

%e .

%e 1 2 3 3 1 1 3 3 1 1 2 2

%e 1 2 2 2 3 3

%e .

%e 1 1 3 3 1 1 2 2

%e 2 3

%e 2 3

%e .

%e 1 2 3 1 2 2 1 1 3

%e 1 2 3 1 3 3 2 2 3

%e .

%e 1 3 3 1 2 2

%e 1 1

%e 2 3

%e 2 3

%e .

%e 1 2 1 1 1 1

%e 1 2 2 3 2 2

%e 3 3 2 3 3 3

%e .

%e 1 3 1 2 1 1

%e 1 3 1 2 2 2

%e 2 3 3

%e 2 3 3

%e .

%e 1 1

%e 2

%e 2

%e 3

%e 3

%e .

%e 1

%e 1

%e 2

%e 2

%e 3

%e 3 - _Gus Wiseman_, Feb 25 2018

%p # For Maple program see A000903.

%p seq(simplify((-I)^n*HermiteH(n, I)), n=0..25); # _Peter Luschny_, Oct 23 2015

%t a[n_] := Sum[ 2^k*StirlingS1[n, k]*BellB[k], {k, 0, n}]; Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Nov 17 2011, after _Vladeta Jovovic_ *)

%t RecurrenceTable[{a[0]==1,a[1]==2,a[n]==2(a[n-1]+(n-1)a[n-2])},a,{n,30}] (* _Harvey P. Dale_, Aug 04 2012 *)

%t Table[Abs[HermiteH[n, I]], {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 22 2015 *)

%t a[ n_] := Sum[ 2^(n - 2 k) n! / (k! (n - 2 k)!), {k, 0, n/2}]; (* _Michael Somos_, Oct 23 2015 *)

%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp(2*x + x^2 + x * O(x^n)), n))}; /* _Michael Somos_, Fep 08 2004 */

%o (PARI) {a(n) = if( n<2, max(0, n+1), 2*a(n-1) + (2*n - 2) * a(n-2))}; /* _Michael Somos_, Fep 08 2004 */

%o (Haskell)

%o a000898 n = a000898_list !! n

%o a000898_list = 1 : 2 : (map (* 2) $

%o zipWith (+) (tail a000898_list) (zipWith (*) [1..] a000898_list))

%o -- _Reinhard Zumkeller_, Oct 10 2011

%o (PARI) x='x+O('x^66); Vec(serlaplace(exp(2*x+x^2))) \\ _Joerg Arndt_, Oct 04 2013

%o (PARI) {a(n) = sum(k=0, n\2, 2^(n - 2*k) * n! / (k! * (n - 2*k)!))}; /* _Michael Somos_, Oct 23 2015 */

%o (Maxima) makelist((%i)^n*hermite(n,-%i),n,0,12); /* _Emanuele Munarini_, Mar 02 2016 */

%Y Column k=2 of A294042 and A376826.

%Y Row sums of A122832 and A185296.

%Y Cf. A000085, A000712, A004003, A066051, A099390, A100861, A135401, A138178, A153452, A297388, A299699, A299926, A300056, A300060.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_

%E More terms from Larry Reeves (larryr(AT)acm.org), Feb 21 2001

%E Initial condition a(0)=1 added to definition by _Jon E. Schoenfield_, Oct 01 2013

%E More terms from _Joerg Arndt_, Oct 04 2013