A227119 Number of ways to select a set partition, P of {1,2,...,n} and then select a subset, S of {1,2,...,n} such that for all i in {1,2,...,n-1} if i and i+1 are in S then i and i+1 are in different blocks of P.

1, 2, 7, 31, 163, 985, 6676, 49918, 406820, 3580011, 33764544, 339222866, 3612046889, 40588278875, 479542299692, 5938050050297, 76848380886090, 1036869475470365, 14553056889254517, 212063804824260167, 3202482669648363619, 50039504959872274840

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Formula

E.g.f.: exp(A''(x) - 1) where A(x) is the e.g.f. for A000045.

Example

a(2) = 7: We can choose the set partition {{1,2}} and then choose the subsets: {}, {1}, {2}; we can choose the set partition {{1},{2}} and then the subsets: {}, {1}, {2}, {1,2}.

Maple

F:= combinat[fibonacci]:
a:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n-1, j-1)*F(j+2)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 06 2017

Mathematica

nn=15; Range[0, nn]!CoefficientList[Series[Exp[-1+Exp[x/2]Cosh[5^(1/2)x/2] +3Exp[x/2]Sinh[5^(1/2)x/2]/5^(1/2)], {x, 0, nn}], x] (* Geoffrey Critzer, Jul 01 2013 *)

Prog

(Python)
from sympy.core.cache import cacheit
from sympy import fibonacci as F, binomial
@cacheit
def a(n): return 1 if n==0 else sum([binomial(n - 1, j - 1)*F(j + 2)*a(n - j) for j in range(1, n + 1)])
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 07 2017, after Maple code

Crossrefs

Sequence in context: A125275 A007446 A277396 * A002872 A105216 A260532

Adjacent sequences: A227116 A227117 A227118 * A227120 A227121 A227122

Keyword

nonn

Author

Geoffrey Critzer, Jul 01 2013

Status

approved