A275707 Number of partial functions f:{1,2,...,n}->{1,2,...,n} such that every element in the domain of definition of f is mapped to a fixed point or to an element that is undefined by f.

1, 2, 8, 38, 216, 1402, 10156, 80838, 698704, 6498674, 64579284, 681642238, 7605025720, 89318058858, 1100376445564, 14176837311158, 190498308591264, 2663482511782114, 38667106019619748, 581765160424218606, 9055862445043643656, 145619330650420134362

Offset

0,2

Links

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

Formula

E.g.f.: A(x)^2 = exp(2*B(x)) where A(x) is the e.g.f. for A000248 and B(x) is the e.g.f. for A000027.

E.g.f.: exp(2*x*exp(x)). - Joerg Arndt, Nov 10 2016

a(0) = 1; a(n) = Sum_{k=1..n} 2*k*binomial(n-1,k-1)*a(n-k). - Ilya Gutkovskiy, Nov 24 2017

From Seiichi Manyama, Jul 04 2022: (Start)

G.f.: Sum_{k>=0} (2 * x)^k/(1 - k*x)^(k+1).

a(n) = Sum_{k=0..n} 2^k * k^(n-k) * binomial(n,k). (End)

a(n) ~ n^(n + 1/2) * exp(2*r*exp(r) - r/2 - n) / (sqrt(2*(1 + 3*r + r^2)) * r^(n + 1/2)), where r = 2*w - 1/(2*w) + 5/(8*w^2) - 19/(24*w^3) + 209/(192*w^4) - 763/(480*w^5) + 4657/(1920*w^6) - 6855/(1792*w^7) + 199613/(32256*w^8) + ... and w = LambertW(sqrt(n)/2^(3/2)). - Vaclav Kotesovec, Jul 06 2022

Example

G.f. = 1 + 2*x + 8*x^2 + 38*x^3 + 216*x^4 + 1402*x^5 + 10156*x^6 + ...
a(2) = 8 because there are 9 = A000169(3) partial functions on a set with 2 elements and all of them have the stated property except 1->2,2->1.

Maple

a:= n-> add(binomial(n, k)*add(binomial(n-k, f)*
        (f+k)^(n-k-f), f=0..n-k), k=0..n):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 07 2016

Mathematica

nn = 20; Range[0, nn]! CoefficientList[Series[ Exp[z Exp[z]]^2, {z, 0, nn}], z]
Table[Sum[BellY[n, k, 2 Range[n]], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)

Prog

(PARI) x='x+O('x^33); Vec(serlaplace(exp(2*x*exp(x)))) \\ Joerg Arndt, Nov 10 2016
(PARI) my(N=30, x='x+O('x^N)); Vec(sum(k=0, N, (2*x)^k/(1-k*x)^(k+1))) \\ Seiichi Manyama, Jul 04 2022
(PARI) a(n) = sum(k=0, n, 2^k*k^(n-k)*binomial(n, k)); \\ Seiichi Manyama, Jul 04 2022

Crossrefs

Column 2 of A187105.

Cf. A000027, A000169, A000248, A351762, A355501.

Sequence in context: A020031 A179323 A001340 * A058786 A096654 A371312

Adjacent sequences: A275704 A275705 A275706 * A275708 A275709 A275710

Keyword

nonn

Author

Geoffrey Critzer, Aug 06 2016

Status

approved