|
|
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.
|
|
5
|
|
|
1, 2, 8, 38, 216, 1402, 10156, 80838, 698704, 6498674, 64579284, 681642238, 7605025720, 89318058858, 1100376445564, 14176837311158, 190498308591264, 2663482511782114, 38667106019619748, 581765160424218606, 9055862445043643656, 145619330650420134362
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
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.
a(0) = 1; a(n) = Sum_{k=1..n} 2*k*binomial(n-1,k-1)*a(n-k). - Ilya Gutkovskiy, Nov 24 2017
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):
|
|
MATHEMATICA
|
nn = 20; Range[0, nn]! CoefficientList[Series[ Exp[z Exp[z]]^2, {z, 0, nn}], z]
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|