cp's OEIS Frontend

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

%I A005425 M1461 #180 May 19 2025 15:59:29
%S A005425 1,2,5,14,43,142,499,1850,7193,29186,123109,538078,2430355,11317646,
%T A005425 54229907,266906858,1347262321,6965034370,36833528197,199037675054,
%U A005425 1097912385851,6176578272782,35409316648435,206703355298074,1227820993510153,7416522514174082
%N A005425 a(n) = 2*a(n-1) + (n-1)*a(n-2).
%C A005425 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
%C A005425 _John W. Layman_ observes that computationally this agrees with the binomial transform of A000085.
%C A005425 Number of self-inverse partial permutations.
%C A005425 Number of '12-3 and 214-3'-avoiding permutations.
%C A005425 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
%C A005425 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
%C A005425 Number of n X n symmetric binary matrices with no row sum greater than 1. - _R. H. Hardin_, Jun 13 2008
%C A005425 Polynomials in A099174 evaluated at x=2 (see also formula by Deutsch below). - _Johannes W. Meijer_, Feb 04 2010
%C A005425 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
%C A005425 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
%C A005425 From _Robert A. Russell_, Apr 28 2018: (Start)
%C A005425 Stirling transform of this sequence is A002872;
%C A005425 Stirling transform of A005425(n-1) is A080337. (End)
%C A005425 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
%C A005425 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
%C A005425 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
%D A005425 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005425 T. D. Noe, <a href="/A005425/b005425.txt">Table of n, a(n) for n = 0..200</a>
%H A005425 E. Bagno and Y. Cherniavsky, <a href="https://doi.org/10.1016/j.disc.2011.12.018">Congruence B-orbits and the Bruhat poset of involutions of the symmetric group</a>, Discrete Math., 312 (1) (2012), pp. 1289-1299.
%H A005425 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 A005425 A. Bingham and O. Ugurlu, <a href="https://arxiv.org/abs/1903.07229">Sects and lattice paths over the Lagrangian Grassmannian</a>, arXiv preprint arXiv:1903.07229 [math.CO], 2019.
%H A005425 P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, <a href="http://arXiv.org/abs/quant-ph/0405103">Combinatorial field theories via boson normal ordering</a>, arXiv:quant-ph/0405103, 2004-2006. The title of this paper in the arXiv was later changed to "Some useful combinatorial formulas for bosonic operators"
%H A005425 P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, <a href="http://dx.doi.org/10.1063/1.1904161">Some useful combinatorial formulas for bosonic operators</a>, J. Math. Phys. 46, 052110 (2005) (6 pages).
%H A005425 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 A005425 Adam M. Goyt and Lara K. Pudwell, <a href="https://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 A005425 T. Halverson and M. Reeks, <a href="https://arxiv.org/abs/1302.6150">Gelfand Models for Diagram Algebras</a>, arXiv preprint arXiv:1302.6150 [math.RT], 2013-2014.
%H A005425 J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H A005425 Mikhail Khovanov, Victor Ostrik and Yakov Kononov, <a href="https://arxiv.org/abs/2011.14758">Two-dimensional topological theories, rational functions and their tensor envelopes</a>, arXiv:2011.14758 [math.QA], 2020.
%H A005425 T. Mansour, <a href="https://arxiv.org/abs/math/0202219">Restricted permutations by patterns of type 2-1</a>, arXiv:math/0202219 [math.CO], 2002.
%H A005425 D. Panyushev, <a href="https://arxiv.org/abs/1407.6857">On the orbits of a Borel subgroup in abelian ideals</a>, arXiv preprint arXiv:1407.6857 [math.AG], 2014.
%H A005425 Ville H. Pettersson, <a href="https://doi.org/10.37236/4510">Enumerating Hamiltonian Cycles</a>, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
%H A005425 K. Piejko, <a href="http://dx.doi.org/10.1155/2015/463650">Extremal trees with respect to number of (A, B, 2C)-edge colourings</a>, Journal of Applied Mathematics, Hindawi Publishing Corporation, Volume 2015, Article ID 463650, 5 pages.
%H A005425 Steven V Sam and Andrew Snowden, <a href="https://arxiv.org/abs/1302.5859">Stability patterns in representation theory</a>, arXiv:1302.5859 [math.RT], 2013-2015. See (1.3.4) p. 8.
%H A005425 R. P. Stanley, <a href="http://dx.doi.org/10.1016/S0196-8858(02)00537-7">On the enumeration of skew Young tableaux</a>, Advances in Applied Mathematics 30 (2003) 283-294, (see corollary 2.4).
%F A005425 E.g.f.: exp( 2*x + x^2/2 ).
%F A005425 a(n) = A027412(n+1)/2. - _N. J. A. Sloane_, Sep 13 2003
%F A005425 a(n) = Sum_{k=0..n} binomial(n, k)*A000085(n-k). - _Philippe Deléham_, Mar 07 2004
%F A005425 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
%F A005425 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
%F A005425 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
%F A005425 a(n) = (1/sqrt(2*Pi))*Integral_{x=-infinity..infinity} exp(-x^2/2)*(x+2)^n. - _Groux Roland_, Mar 14 2011
%F A005425 G.f.: 1/(1-2x-x^2/(1-2x-2x^2/(1-2x-3x^2/(1-2x-4x^2/(1-... (continued fraction).
%F A005425 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
%F A005425 a(n) ~ exp(2*sqrt(n) - n/2 - 1)*n^(n/2)/sqrt(2). - _Vaclav Kotesovec_, Oct 08 2012
%F A005425 a(n) = 2^(n/2)*exp(-i*n*Pi/2)*KummerU(-n/2, 1/2, -2). - _Peter Luschny_, May 30 2021
%e A005425 From _Joerg Arndt_, Apr 18 2014: (Start)
%e A005425 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):
%e A005425 # :    word        partial involution
%e A005425 01:  [ . . . ]    ()
%e A005425 02:  [ . . 3 ]    (3)
%e A005425 03:  [ . 2 . ]    (2)
%e A005425 04:  [ . 2 2 ]    (2 3)
%e A005425 05:  [ . 2 3 ]    (2) (3)
%e A005425 06:  [ 1 . . ]    (1)
%e A005425 07:  [ 1 . 1 ]    (1 3)
%e A005425 08:  [ 1 . 3 ]    (1) (3)
%e A005425 09:  [ 1 1 . ]    (1 2)
%e A005425 10:  [ 1 1 3 ]    (1 2) (3)
%e A005425 11:  [ 1 2 . ]    (1) (2)
%e A005425 12:  [ 1 2 1 ]    (1 3) (2)
%e A005425 13:  [ 1 2 2 ]    (1) (2 3)
%e A005425 14:  [ 1 2 3 ]    (1) (2) (3)
%e A005425 (End)
%p A005425 with(orthopoly): seq((-I/sqrt(2))^n*H(n,I*sqrt(2)),n=0..25);
%t A005425 a[0] = 1; a[1] = 2; a[n_]:= 2a[n-1] + (n-1)*a[n-2]; Table[ a[n], {n, 0, 25}] (* or *)
%t A005425 Range[0, 25]!CoefficientList[Series[Exp[2 x + x^2/2], {x, 0, 25}], x] (* or *)
%t A005425 f[n_] := Sum[2^(n - 3k)n!/((n - 2k)!k!), {k, 0, n}]; Table[ f[n], {n, 0, 25}] (* or *)
%t A005425 Table[(-I/Sqrt[2])^n*HermiteH[n, I*Sqrt[2]], {n, 0, 25}] (* _Robert G. Wilson v_, Nov 04 2005 *)
%t A005425 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 *)
%t A005425 a[n_] := 2^(n/2) Exp[- I n Pi/2] HypergeometricU[-n/2, 1/2, -2];
%t A005425 Table[a[n], {n, 0, 22}] (* _Peter Luschny_, May 30 2021 *)
%o A005425 (Haskell)
%o A005425 a005425 n = a005425_list !! n
%o A005425 a005425_list = 1 : 2 : zipWith (+)
%o A005425    (map (* 2) (tail a005425_list)) (zipWith (*) [1..] a005425_list)
%o A005425 -- _Reinhard Zumkeller_, Dec 18 2011
%o A005425 (PARI) A005425(n)=sum(k=0,n\2,2^(n-3*k)*n!/(n-2*k)!/k!) \\ _M. F. Hasler_, Jan 13 2012
%o A005425 (Maxima) makelist((%i/sqrt(2))^n*hermite(n,-%i*sqrt(2)),n,0,12); /* _Emanuele Munarini_, Mar 02 2016 */
%o A005425 (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
%o A005425 (SageMath) [(-i/sqrt(2))^n*hermite(n, i*sqrt(2)) for n in range(41)] # _G. C. Greubel_, Nov 19 2022
%Y A005425 Cf. A002872, A080337, A085483, A100862, A111062, A128227.
%Y A005425 Bisections give A093620, A100510.
%Y A005425 Row sums of A344678.
%K A005425 nonn,easy,nice
%O A005425 0,2
%A A005425 _Simon Plouffe_
%E A005425 Recurrence and formula corrected by _Olivier Gérard_, Oct 15 1997