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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005425 a(n) = 2*a(n-1) + (n-1)*a(n-2).
(Formerly M1461)
22
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

John W. Layman observes that computationally this agrees with the binomial transform of A000085.

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

Polynomials in A099174 evaluated at x=2 (see also formula by Deutsch below). - Johannes W. Meijer, Feb 04 2010

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

REFERENCES

K Piejko, Extremal trees with respect to number of of (A, B, 2C)-edge colourings, Journal of Applied Mathematics, Hindawi Publishing Corporation, Volume 2015, Article ID 463650, 5 pages http://dx.doi.org/10.1155/2015/463650

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.

P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Combinatorial field theories via boson normal ordering, arXiv:quant-ph/0405103, 2004-2006.

P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Some useful combinatorial formulas for bosonic operators, J. Math. Phys. 46, 052110 (2005) (6 pages).

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

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

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

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

T. Mansour, Restricted permutations by patterns of type 2-1, arXiv:math/0202219 [math.CO], 2002.

D. Panyushev, On the orbits of a Borel subgroup in abelian ideals, arXiv preprint arXiv:1407.6857, 2014

Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.

R. P. Stanley, On the enumeration of skew Young tableaux, Advances in Applied Mathematics 30 (2003) 283-294, (see corollary 2.4).

FORMULA

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

a(n) = A027412(n+1)/2. - N. J. A. Sloane, Sep 13 2003

a(n) = Sum_{k=0..n} binomial(n, k)*A000085(n-k). - Philippe Deléham, Mar 07 2004

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..[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))*int(exp(-x^2/2)*(x+2)^n,x=-infinity..infinity). - 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

EXAMPLE

From Joerg Arndt, Apr 18 2014: (Start)

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

PROG

(Haskell)

a005425 n = a005425_list !! n

a005425_list = 1 : 2 : zipWith (+)

   (map (* 2) (tail a005425_list)) (zipWith (*) [1..] a005425_list)

-- Reinhard Zumkeller, Dec 18 2011

(PARI) A005425(n)=sum(k=0, n\2, 2^(n-3*k)*n!/(n-2*k)!/k!) \\ M. F. Hasler, Jan 13 2012

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

CROSSREFS

Cf. A085483, A093620, A093620, A100862, A111062, A128227.

Bisections give A093620, A100510.

Sequence in context: A112808 A088927 A110489 * A035349 A155888 A254314

Adjacent sequences:  A005422 A005423 A005424 * A005426 A005427 A005428

KEYWORD

nonn,easy,nice

AUTHOR

Simon Plouffe

EXTENSIONS

Recurrence and formula corrected by Olivier Gérard, Oct 15 1997

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 19 08:51 EST 2017. Contains 294923 sequences.