|
| |
|
|
A005425
|
|
a(n) = 2*a(n-1) + (n-1)*a(n-2).
(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 self-inverse partial permutations.
Number of '12-3 and 214-3'-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)+k-m+2. The question is how many such sequences there are. (Note that when we consider only the term k=m-1, this becomes b(m) <= b(m-1)+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. Adams-Watters, 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 upper-triangular 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 k-tuples without repeated entries. Then C [n]^(k) is naturally a complex S_n-representation, 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 n-th Hermite polynomial and i = sqrt(-1). - Emeric Deutsch, Nov 24 2004
a(n) = Sum_{k=0..floor(n/2)} 2^{n-3*k}*n!/((n-2*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_n-1 * ... * 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/(1-2x-x^2/(1-2x-2x^2/(1-2x-3x^2/(1-2x-4x^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[n-1] + (n-1)*a[n-2]; 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[n-1]+(n-1)a[n-2]}, 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(n-1) + (n-1)*Self(n-2):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
|
| |
|
|
