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
Keywords
Examples
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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..524
Programs
-
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 *) -
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
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