A005442 a(n) = n!*Fibonacci(n+1).

1, 1, 4, 18, 120, 960, 9360, 105840, 1370880, 19958400, 322963200, 5748019200, 111607372800, 2347586841600, 53178757632000, 1290674601216000, 33413695451136000, 919096314200064000, 26768324463648768000

Offset: 0

Author

Simon Plouffe

Keywords

• nonn
• easy

Comments

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

Number of pairs (p,S) where p is a permutation of {1,2,...,n} and S is a subset of {1,2,...,n} such that if s is in S then p(s) is not in S. For example a(2) = 4 because we have (p=(1)(2), s={}); (p=(1,2), s={}); (p=(1,2), s={1}); (p=(1,2), s={2}) where p is given in cycle notation. - Geoffrey Critzer, Jul 01 2013

Another way to state the first comment: a(n) is the number of ways to partition [n] into blocks of size at most 2, order the blocks, and order the elements within each block. For example, a(5)=960 since there are 3 cases: 1) 1,2,3,4,5: 120 such ordered blocks, 1 way to order elements within blocks, hence 120 ways; 2) 12,3,4,5: 240 such ordered blocks, 2 ways to order elements within blocks, hence 480 ways; 3) 12,34,5: 90 such ordered blocks, 4 ways to order elements within blocks, hence 360 ways. - Enrique Navarrete, Sep 01 2023

References

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

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..416
• P. R. J. Asveld & N. J. A. Sloane, Correspondence, 1987
• P. R. J. Asveld, A family of Fibonacci-like sequences, Fib. Quart., 25 (1987), 81-83.
• P. R. J. Asveld, Another family of Fibonacci-like sequences, Fib. Quart., 25 (1987), 361-364.
• P. R. J. Asveld, Fibonacci-like differential equations with a polynomial nonhomogeneous term, Fib. Quart. 27 (1989), 303-309.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 494
• Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
• Index entries for related partition-counting sequences

Crossrefs

Row sums of Fibonacci Jabotinsky-triangle A039692.

Cf. A000045, A000142, A039948, A052585, A080599.

Programs

Magma

[Factorial(n)*Fibonacci(n+1): n in [0..20]]; // G. C. Greubel, Nov 20 2022

Mathematica

Table[Fibonacci[n + 1]*n!, {n, 0, 20}] (* Zerinvary Lajos, Jul 09 2009 *)

PARI

a(n) = n!*fibonacci(n+1) \\ Charles R Greathouse IV, Oct 03 2016

SageMath

[fibonacci(n+1)*factorial(n) for n in range(21)] # G. C. Greubel, Nov 20 2022

Formula

a(n) = A039948(n,0).

E.g.f.: 1/(1-x-x^2).

D-finite with recurrence a(n) = n*a(n-1)+n*(n-1)*a(n-2). - Detlef Pauly (dettodet(AT)yahoo.de), Sep 22 2003

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

Extensions

Comments from Wolfdieter Lang