A392981 Expansion of e.g.f. 1 / (1 - Sum_{k>=1} Fibonacci(k+1)*x^k/k!).

1, 1, 4, 21, 149, 1318, 13999, 173453, 2456208, 39129085, 692615137, 13485806082, 286451044367, 6591526682377, 163345171980964, 4337003912015861, 122829320381469885, 3696095828390155822, 117762761196262798447, 3960534797328060652245, 140209061189106210244520, 5211798642807685609670221

Offset

0,3

Comments

a(n) equals the sum over all set partitions P of {1...n} of (b! * Product_{each block B in P} Fibonacci(|B|+1)), where b is the number of blocks in P and |B| is the size of block B. Thus, a(n) counts ordered set partitions weighted by Fibonacci numbers: a block of size k contributes F(k+1), and the blocks are ordered.

This sequence fits into a family given by the exponential generating function 1/(1 - Sum_{k>=1} c(k)*x^k/k!), where different choices of c(k) yield known sequences: c(k)=1 gives A000670, c(k)=p(k) gives A324236, c(k)=k! gives A002866.

Links

Table of n, a(n) for n=0..21.

Formula

a(n) = Sum_{k=1..n} binomial(n,k) * Fibonacci(k+1) * a(n-k) for n >= 1.

Example

For n = 3, the a(3) = 21 weighted set partitions are:
  Block-size pattern [3]: {123} contributes 1! * Fib(4) = 1 * 3 = 3.
  Block-size pattern [2,1]: three partitions ({12}{3}, {13}{2}, {1}{23}) each contribute 2! * (Fib(3)*Fib(2)) = 2 * (2*1) = 4; total 3 * 4 = 12.
  Block-size pattern [1,1,1]: {1}{2}{3} contributes 3! * (Fib(2)^3) = 6 * (1^3) = 6.
Sum = 3 + 12 + 6 = 21.
For n = 5, a(5) = 1318 is obtained by summing over all 52 set partitions of {1,2,3,4,5}:
  [5] : 1 partition * 1! * Fib(6) = 1 * 8 = 8
  [4,1] : 5 partitions * 2! * (Fib(5)*Fib(2)) = 5 * 2 * (5*1) = 50
  [3,2] : 10 partitions * 2! * (Fib(4)*Fib(3)) = 10 * 2 * (3*2) = 120
  [3,1,1] : 10 partitions * 3! * (Fib(4)*Fib(2)^2) = 10 * 6 * (3*1) = 180
  [2,2,1] : 15 partitions * 3! * (Fib(3)^2*Fib(2)) = 15 * 6 * (4*1) = 360
  [2,1,1,1] : 10 partitions * 4! * (Fib(3)*Fib(2)^3) = 10 * 24 * (2*1) = 480
  [1,1,1,1,1] : 1 partition * 5! * Fib(2)^5 = 1 * 120 * 1 = 120
Total = 8 + 50 + 120 + 180 + 360 + 480 + 120 = 1318.

Mathematica

a[0]=1; a[n_]:=a[n]=Sum[Binomial[n, k]*Fibonacci[k+1]*a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 20}]

Prog

(PARI) a(n)=if(n==0, 1, sum(k=1, n, binomial(n, k)*fibonacci(k+1)*a(n-k)));

Crossrefs

Cf. A000045 (Fibonacci numbers), A000110 (Bell numbers), A000670 (Fubini numbers), A002866 (2^(n-1)*n!), A308940, A324236.

Sequence in context: A183387 A346430 A324236 * A330019 A025164 A335848

Adjacent sequences: A392978 A392979 A392980 * A392982 A392984 A392985

Keyword

nonn,easy

Author

Md. Rad Sarar Anando, Jan 29 2026

Status

approved