A047974 a(n) = a(n-1) + 2*(n-1)*a(n-2).

1, 1, 3, 7, 25, 81, 331, 1303, 5937, 26785, 133651, 669351, 3609673, 19674097, 113525595, 664400311, 4070168161, 25330978113, 163716695587, 1075631907655, 7296866339961, 50322142646161, 356790528924523, 2570964805355607, 18983329135883665, 142389639792952801, 1091556096587136051

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Related to partially ordered sets. - Detlef Pauly (dettodet(AT)yahoo.de), Sep 25 2003

The number of partial permutation matrices P in GL_n with P^2=0. Alternatively, the number of orbits of the Borel group of upper triangular matrices acting by conjugation on the set of matrices M in GL_n with M^2=0. - Brian Rothbach (rothbach(AT)math.berkeley.edu), Apr 16 2004

Number of ways to use the elements of {1..n} once each to form a collection of sequences, each having length 1 or 2. - Bob Proctor, Apr 18 2005

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

This is also the number of subsets of equivalent ways to arrange the elements of n pairs, when equivalence is defined under the joint operation of (optional) reversal of elements combined with permutation of the labels and the subset maps to itself. - Ross Drewe, Mar 16 2008

Equals inverse binomial transform of A000898. - Gary W. Adamson, Oct 06 2008

a(n) is also the moment of order n for the measure of density exp(-(x-1)^2/4)/(2*sqrt(Pi)) over the interval -oo..oo. - Groux Roland, Mar 26 2011

The n-th term gives the number of fixed-point-free involutions in S_n^B, the group of permutations on the set {-n,...,-1,1,2,...,n}. - Matt Watson, Jul 26 2012

From Peter Bala, Dec 03 2017: (Start)

a(n+k) == a(n) (mod k) for all n and k. Hence for each k, the sequence a(n) taken modulo k is a periodic sequence and the exact period divides k. Cf. A115329.

More generally, the same divisibility property holds for any sequence with an e.g.f. of the form F(x)*exp(x*G(x)), where F(x) and G(x) are power series with integer coefficients and G(0) = 1. See the Bala link for a proof. (End)

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Peter Alspaugh, James Garrett, Nataša Jonoska, and Masahico Saito, Structures of Monoids Motivated by DNA Origami, arXiv:2501.14966 [math.RA], 2025. See p. 22.
• Tewodros Amdeberhan, Valerio De Angelis, Atul Dixit, Victor H. Moll, and Christophe Vignat, From sequences to polynomials and back, via operator orderings, J. Math. Phys. 54, 123502 (2013); Alternative copy
• Peter Bala, Integer sequences that become periodic on reduction modulo k for all k
• Jonathan Burns, Assembly Graph Words - Single Transverse Component (Counts); Alternative copy
• Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination, Discrete Applied Mathematics, Volume 161, Issues 10-11, July 2013, Pages 1378-1394; Alternative copy.
• Jonathan Burns and Tilahun Muche, Counting Irreducible Double Occurrence Words, arXiv preprint arXiv:1105.2926 [math.CO], 2011.
• Samuele Giraudo, Combalgebraic structures on decorated cliques, arXiv:1709.08416 [math.CO], 2017; and also, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 8.
• Tom Halverson and Mike Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150 [math.RT], 2013.
• Andrei Khruzin, Enumeration of chord diagrams, arXiv:math/0008209 [math.CO], 2000.
• G. Latouche and P. G. Taylor, A stochastic fluid model for an ad hoc mobile network, Queueing Syst. 63, No. 1-4, 109-129 (2009), eq. (1).
• Robert A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
• Jocelyn Quaintance and Harris Kwong, Permutations and combinations of colored multisets, JIS 13 (2010) #10.2.6.
• Index entries for related partition-counting sequences
• Index entries for sequences related to Hermite polynomials

Crossrefs

Row sums of A067147.

Column k=2 of A359762.

Cf. A000085, A000680, A000898, A001147, A001813, A100861, A108400, A115329, A132101.

Sequences with e.g.f = exp(x + q*x^2): A158968 (q=-9), A158954 (q=-4), A362177 (q=-3), A362176 (q=-2), A293604 (q=-1), A000012 (q=0), this sequence (q=1), A115329 (q=2), A293720 (q=4).

Programs

MATLAB

N = 18; A = zeros(N,1); for n = 1:N; a = factorial(n); s = 0; k = 0; while k <= floor(n/2); b = factorial(n - 2*k); c = factorial(k); s = s + a/(b*c); k = k+1; end; A(n) = s; end; disp(A); % Ross Drewe, Mar 16 2008

Magma

[n le 2 select 1 else Self(n-1) + 2*(n-2)*Self(n-2): n in [1..40]]; // G. C. Greubel, Jul 12 2024

Maple

seq( add(n!/((n-2*k)!*k!), k=0..floor(n/2)), n=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 15 2001
with(combstruct):seq(count(([S,{S=Set(Union(Z,Prod(Z,Z)))},labeled],size=n)),n=0..30); # Detlef Pauly (dettodet(AT)yahoo.de), Sep 25 2003
A047974 := n -> I^(-n)*orthopoly[H](n, I/2):
seq(A047974(n), n=0..26); # Peter Luschny, Nov 29 2017

Mathematica

Range[0, 23]!*CoefficientList[ Series[ Exp[x*(1-x^2)/(1 - x)], {x, 0,23 }], x] - (* Zerinvary Lajos, Mar 23 2007 *)
Table[I^(-n)*HermiteH[n, I/2], {n, 0, 23}] - (* Alyssa Byrnes and C. Vignat, Jan 31 2013 *)

PARI

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

SageMath

[(-i)^n*hermite(n,i/2) for n in range(41)] # G. C. Greubel, Jul 12 2024

Formula

E.g.f.: exp(x^2+x). - Len Smiley, Dec 11 2001

Binomial transform of A001813 (with interpolated zeros). - Paul Barry, May 09 2003

a(n) = Sum_{k=0..n} C(k,n-k)*n!/k!. - Paul Barry, Mar 29 2007

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

G.f.: 1/(1-x-2*x^2/(1-x-4*x^2/(1-x-6*x^2/(1-x-8*x^2/(1-... (continued fraction). -Paul Barry, Apr 10 2009

E.g.f.: Q(0); Q(k) = 1+(x^2+x)/(2*k+1-(x^2+x)*(2*k+1)/((x^2+x)+(2*k+2)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 24 2011

a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator sqrt(1+4*x)*d/dx. Cf. A000085 and A115329. - Peter Bala, Dec 07 2011

a(n) ~ 2^(n/2 - 1/2)*exp(sqrt(n/2) - n/2 - 1/8)*n^(n/2). - Vaclav Kotesovec, Oct 08 2012

E.g.f.: 1 + x*(E(0)-1)/(x+1) where E(k) = 1 + (1+x)/(k+1)/(1-x/(x+1/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 26 2013

a(n) = i^(-n)*H_{n}(i/2) with i the imaginary unit and H_{n} the Hermite polynomial of degree n. - Alyssa Byrnes and C. Vignat, Jan 31 2013

E.g.f.: -Q(0)/x where Q(k) = 1 - (1+x)/(1 - x/(x - (k+1)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Mar 06 2013

G.f.: 1/Q(0), where Q(k) = 1 + x*2*k - x/(1 - x*(2*k+2)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 17 2013

E.g.f.: E(0)-1-x-x^2, where E(k) = 2 + 2*x*(1+x) - 8*k^2 + x^2*(1+x)^2*(2*k+3)*(2*k-1)/E(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 21 2013

E.g.f.: Product_{k>=1} 1/(1 + (-x)^k)^(mu(k)/k). - Ilya Gutkovskiy, May 26 2019

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