A111752 Number of partitions of {1,..,n} into lists with an even number of lists of size 1, where a list means an ordered subset (cf. A000262).

1, 0, 3, 6, 49, 300, 2491, 22890, 239457, 2782584, 35595091, 496577070, 7499663953, 121855323876, 2118793593099, 39245026343250, 771255810671041, 16025261292247920, 350956070419872547, 8078570913162379734, 194969375055353840241, 4922311437793379501340

Offset

0,3

Comments

a(n) + A111753(n) = A000262(n). - David Wasserman, Feb 11 2009

Links

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

Formula

E.g.f.: cosh(x)*exp(x^2/(1-x)). More generally, e.g.f. for number of partitions of {1, 2, ...n} into lists with an even number of lists of size k is cosh(x^k)*exp(x/(1-x)-x^k).

E.g.f.: cosh(x)*exp(x^2/(1-x)) = 1/2*Q(0); Q(k) = 1+((2*x-1)^k)/(1-x/(x+((2*x-1)^k)*(k+1)*(1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011

a(n) ~ (exp(1)+exp(-1)) * 2^(-3/2) * exp(2*sqrt(n)-n-3/2) * n^(n-1/4) * (1 + (2/(1 + exp(2)) - 5/48)/sqrt(n)). - Vaclav Kotesovec, Jan 21 2017, extended Dec 01 2021

Maple

b:= proc(n, t) option remember; `if`(n=0, t, add(b(n-j,
     `if`(j=1, 1-t, t))*binomial(n-1, j-1)*j!, j=1..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..30);  # Alois P. Heinz, May 10 2016

Mathematica

b[n_, t_] := b[n, t] = If[n == 0, t, Sum[b[n-j, If[j == 1, 1-t, t]] * Binomial[n-1, j-1]*j!, {j, 1, n}]]; a[n_] := b[n, 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 21 2017, after Alois P. Heinz *)

Prog

(Python)
from sympy.core.cache import cacheit
from sympy import binomial, factorial as f
@cacheit
def b(n, t): return t if n==0 else sum(b(n - j, (1 - t if j==1 else t))*binomial(n - 1, j - 1)*f(j) for j in range(1, n + 1))
def a(n): return b(n, 1)
print([a(n) for n in range(51)]) # Indranil Ghosh, Aug 10 2017

Crossrefs

Cf. A000262, A113235, A063083, A062282, A111723, A111724, A111753.

Sequence in context: A279706 A032322 A203765 * A102931 A056447 A056437

Adjacent sequences: A111749 A111750 A111751 * A111753 A111754 A111755

Keyword

easy,nonn

Author

Vladeta Jovovic, Nov 19 2005; corrected Jun 06 2006

Extensions

More terms from David Wasserman, Feb 11 2009

a(0)=1 prepended by Alois P. Heinz, May 10 2016

Status

approved