login
Number of partial mappings (or mapping patterns) from n points to themselves; number of partial endofunctions.
6

%I #31 Nov 28 2023 08:51:27

%S 1,2,6,16,45,121,338,929,2598,7261,20453,57738,163799,465778,1328697,

%T 3798473,10883314,31237935,89812975,258595806,745563123,2152093734,

%U 6218854285,17988163439,52078267380,150899028305,437571778542,1269754686051,3687025215421

%N Number of partial mappings (or mapping patterns) from n points to themselves; number of partial endofunctions.

%C If an endofunction is partial, then some points may be unmapped (or mapped to "undefined").

%C The labeled version is left-shifted A000169. - _Franklin T. Adams-Watters_, Jan 16 2007

%H Alois P. Heinz, <a href="/A126285/b126285.txt">Table of n, a(n) for n = 0..750</a>

%H R. I. McLachlan, K. Modin, H. Munthe-Kaas, and O. Verdier, <a href="http://arxiv.org/abs/1512.00906">What are Butcher series, really? The story of rooted trees and numerical methods for evolution equations</a>, arXiv preprint arXiv:1512.00906 [math.NA], 2015-2017.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%F Euler transform of A002861 + A000081 = [1, 2, 4, 9, 20, 51, 125, 329, 862, 2311, ... ] + [ 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, ...] = A124682.

%F Convolution of left-shifted A000081 with A001372. - _Franklin T. Adams-Watters_, Jan 16 2007

%F a(n) ~ c * d^n / sqrt(n), where d = 2.95576528565... is the Otter's rooted tree constant (see A051491) and c = 1.309039781943936352117502717... - _Vaclav Kotesovec_, Mar 29 2014

%t nmax = 28;

%t a81[n_] := a81[n] = If[n<2, n, Sum[Sum[d*a81[d], {d, Divisors[j]}]*a81[n-j ], {j, 1, n-1}]/(n-1)];

%t A[n_] := A[n] = If[n<2, n, Sum[DivisorSum[j, #*A[#]&]*A[n-j], {j, 1, n-1} ]/(n-1)];

%t H[t_] := Sum[A[n]*t^n, {n, 0, nmax+2}];

%t F = 1/Product[1 - H[x^n], {n, 1, nmax+2}] + O[x]^(nmax+2);

%t A1372 = CoefficientList[F, x];

%t a[n_] := Sum[a81[k] * A1372[[n-k+2]], {k, 0, n+1}];

%t Table[a[n], {n, 0, nmax}] (* _Jean-François Alcover_, Aug 18 2018, after _Franklin T. Adams-Watters_ *)

%o (Sage)

%o Pol.<t> = InfinitePolynomialRing(QQ)

%o @cached_function

%o def Z(n):

%o if n==0: return Pol.one()

%o return sum(t[k]*Z(n-k) for k in (1..n))/n

%o def pmagmas(n,k=1): # number of partial k-magmas on a set of n elements up to isomorphism

%o P = Z(n)

%o q = 0

%o coeffs = P.coefficients()

%o count = 0

%o for m in P.monomials():

%o p = 1

%o V = m.variables()

%o T = cartesian_product(k*[V])

%o for t in T:

%o r = [Pol.varname_key(str(u))[1] for u in t]

%o j = [m.degree(u) for u in t]

%o D = 1

%o lcm_r = lcm(r)

%o for d in divisors(lcm_r):

%o try: D += d*m.degrees()[-d-1]

%o except: break

%o p *= D^(prod(r)/lcm_r*prod(j))

%o q += coeffs[count]*p

%o count += 1

%o return q

%o # _Philip Turecek_, Nov 27 2023

%Y Cf. A001372.

%Y Cf. A000169, A000081, A002861.

%K nonn

%O 0,2

%A _Christian G. Bower_, Dec 25 2006 based on a suggestion from _Jonathan Vos Post_