login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000898 a(n) = 2*(a(n-1) + (n-1)*a(n-2)), a(0) = 1.
(Formerly M1648 N0645)
45
1, 2, 6, 20, 76, 312, 1384, 6512, 32400, 168992, 921184, 5222208, 30710464, 186753920, 1171979904, 7573069568, 50305536256, 342949298688, 2396286830080, 17138748412928, 125336396368896, 936222729254912, 7136574106003456, 55466948299223040, 439216305474605056, 3540846129311916032 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

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

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

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

Hankel transform is A108400. - Paul Barry, Feb 11 2008

From Emeric Deutsch, Jun 19 2010: (Start)

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.

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.

(End)

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

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

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

REFERENCES

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

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

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

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

T. D. Noe, Table of n, a(n) for n=0..200

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

Paul Barry, The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1804.05027 [math.CO], 2018.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

C.-O. Chow, Counting involutory, unimodal and alternating signed permutations, Discr. Math. 306 (2006), 2222-2228.

R. Donaghey, Binomial self-inverse sequences and tangent coefficients, J. Combin. Theory, Series A, 21 (1976), 155-163.

Eric S. Egge, Restricted symmetric permutations, Ann. Combin., 11 (2007), 405-434.

Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From N. J. A. Sloane, Sep 17 2012

T. Halverson and M. Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150 [math.RT], 2013.

Guo-Niu Han, Enumeration of Standard Puzzles

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181. [Annotated scan of pages 180 and 181 only]

Yen-chi R. Lin, Asymptotic Formula for Symmetric Involutions, arXiv:1310.0988 [math.CO], 2013.

E. Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 221.

E. Lucas, Théorie des nombres (annotated scans of a few selected pages)

J. Riordan, Letter to N. J. A. Sloane, Feb 03 1975 (with notes by njas)

D. P. Roberts, A. Venkatesh, Hurwitz monodromy and full number fields, 2014.

Index entries for sequences related to Hermite polynomials

FORMULA

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

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

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

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

Binomial transform of A047974. - Paul Barry, May 09 2003

a(n) = Sum_{k=0..n} Stirling1(n, k)*2^k*Bell(k). - Vladeta Jovovic, Oct 01 2003

a(n) = Sum_{k=0..floor(n/2)} A001498(n-k, k)*2^(n-k); a(n) = Sum_{k=0..n} A001498((n+k)/2, (n-k)/2)*2^((n+k)/2)(1+(-1)^(n-k))/2. - Paul Barry, Aug 29 2005

For asymptotics see the Robinson paper. [This is disputed by Yen-chi R. Lin. See below, Sep 30 2013.]

a(n) = Sum_{k=0..floor(n/2)} 2^(n-2k)*C(n,2k)(2k)!/k!. - Paul Barry, Feb 11 2008

G.f.: 1/(1-2x-2x^2/(1-2x-4x^2/(1-2x-6x^2/(1-2x-8x^2/(1-... (continued fraction). - Paul Barry, Feb 25 2010

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

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

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

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

EXAMPLE

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

The a(3) = 20 domino tableaux:

1 1 2 2 3 3

.

1 2 2 3 3

1

.

1 2 3 3   1 1 3 3   1 1 2 2

1 2       2 2       3 3

.

1 1 3 3   1 1 2 2

2         3

2         3

.

1 2 3   1 2 2   1 1 3

1 2 3   1 3 3   2 2 3

.

1 3 3   1 2 2

1       1

2       3

2       3

.

1 2   1 1   1 1

1 2   2 3   2 2

3 3   2 3   3 3

.

1 3   1 2   1 1

1 3   1 2   2 2

2     3     3

2     3     3

.

1 1

2

2

3

3

.

1

1

2

2

3

3 - Gus Wiseman, Feb 25 2018

MAPLE

For Maple program see A000903.

seq(simplify((-I)^n*HermiteH(n, I)), n=0..25); # Peter Luschny, Oct 23 2015

MATHEMATICA

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 *)

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 *)

Table[Abs[HermiteH[n, I]], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 22 2015 *)

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

PROG

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

(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 */

(Haskell)

a000898 n = a000898_list !! n

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

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

-- Reinhard Zumkeller, Oct 10 2011

(PARI) x='x+O('x^66); Vec(serlaplace(exp(2*x+x^2))) \\ Joerg Arndt, Oct 04 2013

(PARI) {a(n) = sum(k=0, n\2, 2^(n - 2*k) * n! / (k! * (n - 2*k)!))}; /* Michael Somos, Oct 23 2015 */

(Maxima) makelist((%i)^n*hermite(n, -%i), n, 0, 12); /* Emanuele Munarini, Mar 02 2016 */

CROSSREFS

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

Sequence in context: A263903 A263904 A263898 * A213225 A195254 A150173

Adjacent sequences:  A000895 A000896 A000897 * A000899 A000900 A000901

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

Initial condition a(0)=1 added to definition by Jon E. Schoenfield, Oct 01 2013

More terms from Joerg Arndt, Oct 04 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 02:33 EST 2019. Contains 320200 sequences. (Running on oeis4.)