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

1, 2, 6, 16, 45, 121, 338, 929, 2598, 7261, 20453, 57738, 163799, 465778, 1328697, 3798473, 10883314, 31237935, 89812975, 258595806, 745563123, 2152093734, 6218854285, 17988163439, 52078267380, 150899028305, 437571778542, 1269754686051, 3687025215421

Offset: 0

Author

Christian G. Bower, Dec 25 2006 based on a suggestion from Jonathan Vos Post

Keywords

• nonn

Comments

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

The labeled version is left-shifted A000169. - Franklin T. Adams-Watters, Jan 16 2007

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..750
• R. I. McLachlan, K. Modin, H. Munthe-Kaas, and O. Verdier, What are Butcher series, really? The story of rooted trees and numerical methods for evolution equations, arXiv preprint arXiv:1512.00906 [math.NA], 2015-2017.
• N. J. A. Sloane, Transforms

Crossrefs

Cf. A001372.

Cf. A000169, A000081, A002861.

Programs

Mathematica

nmax = 28;
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)];
A[n_] := A[n] = If[n<2, n, Sum[DivisorSum[j, #*A[#]&]*A[n-j], {j, 1, n-1} ]/(n-1)];
H[t_] := Sum[A[n]*t^n, {n, 0, nmax+2}];
F = 1/Product[1 - H[x^n], {n, 1, nmax+2}] + O[x]^(nmax+2);
A1372 = CoefficientList[F, x];
a[n_] := Sum[a81[k] * A1372[[n-k+2]], {k, 0, n+1}];
Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Aug 18 2018, after Franklin T. Adams-Watters *)

Sage

Pol. = InfinitePolynomialRing(QQ)
@cached_function
def Z(n):
    if n==0: return Pol.one()
    return sum(t[k]*Z(n-k) for k in (1..n))/n
def pmagmas(n,k=1): # number of partial k-magmas on a set of n elements up to isomorphism
    P = Z(n)
    q = 0
    coeffs = P.coefficients()
    count = 0
    for m in P.monomials():
        p = 1
        V = m.variables()
        T = cartesian_product(k*[V])
        for t in T:
            r = [Pol.varname_key(str(u))[1] for u in t]
            j = [m.degree(u) for u in t]
            D = 1
            lcm_r = lcm(r)
            for d in divisors(lcm_r):
                try: D += d*m.degrees()[-d-1]
                except: break
            p *= D^(prod(r)/lcm_r*prod(j))
        q += coeffs[count]*p
        count += 1
    return q
# Philip Turecek, Nov 27 2023

Formula

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.

Convolution of left-shifted A000081 with A001372. - Franklin T. Adams-Watters, Jan 16 2007

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