

A005425


a(n) = 2*a(n1) + (n1)*a(n2).
(Formerly M1461)


33



1, 2, 5, 14, 43, 142, 499, 1850, 7193, 29186, 123109, 538078, 2430355, 11317646, 54229907, 266906858, 1347262321, 6965034370, 36833528197, 199037675054, 1097912385851, 6176578272782, 35409316648435, 206703355298074, 1227820993510153, 7416522514174082
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Switchboard problem with n subscribers, where a subscriber who is not talking can be of either of two sexes. Subscribers who are talking cannot be distinguished by sex. See also A000085.  Karol A. Penson, Apr 15 2004
Number of selfinverse partial permutations.
Number of '123 and 2143'avoiding permutations.
Number of matchings of the corona K'(n) of the complete graph K(n) and the complete graph K(1); in other words, K'(n) is the graph constructed from K(n) by adding for each vertex v a new vertex v' and the edge vv'. Example: a(3)=14 because in the graph with vertex set {A,B,C,a,b,c} and edge set {AB,AC,BC,Aa,Bb,Cc} we have the following matchings: (i) the empty set (1); (ii) the edges as singletons (6); (iii) {Aa,BC},{Bb,AC},{Cc,AB},{Aa,Bb},{Aa,Cc}, {Bb,Cc} (6); (iv) {Aa,Bb,Cc} (1). Row sums of A100862.  Emeric Deutsch, Jan 10 2005
Consider finite sequences of positive integers <b(m)> of length n with b(1)=1 and with the constraint that b(m) <= max_{0<k<m} b(k)+km+2. The question is how many such sequences there are. (Note that when we consider only the term k=m1, this becomes b(m) <= b(m1)+1 and it is well known that the number of sequences under this constraint is the Catalan numbers.) This sequence starts (from n = 1): 1,2,5,14,43,142,499,1850,7193. This appears to be the present sequence. But I do not see any way to prove it. The number T(n,m) of sequences of length n which will limit the continuation to size n+1 to a maximum value of m+1 appears to be given by A111062.  Franklin T. AdamsWatters, Dec 21 2005, corrected Dec 31 2014
Number of n X n symmetric binary matrices with no row sum greater than 1.  R. H. Hardin, Jun 13 2008
Equals eigensequence of triangle A128227. Example: a(5) = 142 = (1, 1, 2, 5, 14, 43) dot (1, 2, 3, 4, 5, 1) = (1 + 2 + 6 + 20 + 70 + 43); where (1, 2, 3, 4, 5, 1) = row 5 of triangle A128227.  Gary W. Adamson, Aug 27 2010
Number of words [d(1), d(2), ..., d(n)] where d(k) is either =0, or =k (a fixed point), or the only value repeating a previous fixed point, see example.  Joerg Arndt, Apr 18 2014
Stirling transform of this sequence is A002872;
Number of congruence orbits of uppertriangular n X n matrices on symmetric matrices, or the number of Borel orbits in largest sect of the type CI symmetric space Sp_{2n}(C)/GL_n(C).  Aram Bingham, Oct 10 2019
For a refined enumeration of the switchboard scenario presented by Penson above and in Donaghey and its relation to perfect matchings of simplices and an operator calculus, see A344678.  Tom Copeland, May 29 2021
Write [n] for {1, ..., n} and [n]^(k) for ktuples without repeated entries. Then C [n]^(k) is naturally a complex S_nrepresentation, whose length is a(k) provided that n >= 2k. a(k) also gives the length of the countable dimensional Sym(N)representation C N^(k), as remarked by Sam and Snowden (see link).  Jingjie Yang, Dec 28 2023


REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA

E.g.f.: exp( 2*x + x^2/2 ).
a(n) = (i/sqrt(2))^n*H(n, i*sqrt(2)), where H(n, x) is the nth Hermite polynomial and i = sqrt(1).  Emeric Deutsch, Nov 24 2004
a(n) = Sum_{k=0..floor(n/2)} 2^{n3*k}*n!/((n2*k)!*k!).  Huajun Huang (hua_jun(AT)hotmail.com), Oct 10 2005
For all n, a(n) = [M_n]_1,1 = [M_n]_2,1, where M_n = A_n * A_n1 * ... * A_1, being A_k the matrix A_k = [1, k;1, 1].  Simone Severini, Apr 25 2007
a(n) = (1/sqrt(2*Pi))*Integral_{x=infinity..infinity} exp(x^2/2)*(x+2)^n.  Groux Roland, Mar 14 2011
G.f.: 1/(12xx^2/(12x2x^2/(12x3x^2/(12x4x^2/(1... (continued fraction).
E.g.f.: G(0) where G(k) = 1 + x*(4+x)/(4*k + 2  x*(4+x)*(4*k+2)/(x*(4+x) + 4*(k+1)/G(k+1))); (continued fraction).  Sergei N. Gladkovskii, Dec 17 2011
a(n) ~ exp(2*sqrt(n)  n/2  1)*n^(n/2)/sqrt(2).  Vaclav Kotesovec, Oct 08 2012
a(n) = 2^(n/2)*exp(i*n*Pi/2)*KummerU(n/2, 1/2, 2).  Peter Luschny, May 30 2021


EXAMPLE

The a(3) = 14 words [d(1), d(2), d(3)] where d(k) is either =0, or =k (a fixed point), or the only value repeating a previous fixed point are (dots for zeros):
# : word partial involution
01: [ . . . ] ()
02: [ . . 3 ] (3)
03: [ . 2 . ] (2)
04: [ . 2 2 ] (2 3)
05: [ . 2 3 ] (2) (3)
06: [ 1 . . ] (1)
07: [ 1 . 1 ] (1 3)
08: [ 1 . 3 ] (1) (3)
09: [ 1 1 . ] (1 2)
10: [ 1 1 3 ] (1 2) (3)
11: [ 1 2 . ] (1) (2)
12: [ 1 2 1 ] (1 3) (2)
13: [ 1 2 2 ] (1) (2 3)
14: [ 1 2 3 ] (1) (2) (3)
(End)


MAPLE

with(orthopoly): seq((I/sqrt(2))^n*H(n, I*sqrt(2)), n=0..25);


MATHEMATICA

a[0] = 1; a[1] = 2; a[n_]:= 2a[n1] + (n1)*a[n2]; Table[ a[n], {n, 0, 25}] (* or *)
Range[0, 25]!CoefficientList[Series[Exp[2 x + x^2/2], {x, 0, 25}], x] (* or *)
f[n_] := Sum[2^(n  3k)n!/((n  2k)!k!), {k, 0, n}]; Table[ f[n], {n, 0, 25}] (* or *)
Table[(I/Sqrt[2])^n*HermiteH[n, I*Sqrt[2]], {n, 0, 25}] (* Robert G. Wilson v, Nov 04 2005 *)
RecurrenceTable[{a[0]==1, a[1]==2, a[n]==2a[n1]+(n1)a[n2]}, a, {n, 30}] (* Harvey P. Dale, Sep 30 2015 *)
a[n_] := 2^(n/2) Exp[ I n Pi/2] HypergeometricU[n/2, 1/2, 2];


PROG

(Haskell)
a005425 n = a005425_list !! n
a005425_list = 1 : 2 : zipWith (+)
(map (* 2) (tail a005425_list)) (zipWith (*) [1..] a005425_list)
(Maxima) makelist((%i/sqrt(2))^n*hermite(n, %i*sqrt(2)), n, 0, 12); /* Emanuele Munarini, Mar 02 2016 */
(Magma) a:=[2, 5]; [1] cat [n le 2 select a[n] else 2*Self(n1) + (n1)*Self(n2):n in [1..30]]; // Marius A. Burtea, Oct 10 2019
(SageMath) [(i/sqrt(2))^n*hermite(n, i*sqrt(2)) for n in range(41)] # G. C. Greubel, Nov 19 2022


CROSSREFS



KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



