A395672 Number of endofunctions f:{1,2,...,n}-> {1,2,...,n} whose smallest weakly connected component has exactly 3 nodes.

0, 0, 0, 17, 0, 0, 2890, 84490, 1493688, 32186168, 810545040, 23163353400, 720663872500, 24332866501372, 887558454336372, 34810380537375170, 1460425852562219760, 65255195022227232480, 3093688414572173306128, 155103564618621456778168, 8198969255720346583303380

Offset

0,4

Comments

a(n) is always divisible by A001865(3) = 17.

Links

Table of n, a(n) for n=0..20.

Formula

E.g.f.: exp(-x-3*x^2/2)*(1-exp(-17*x^3/6)) / (1+LambertW(-x)).

Limit_{n->oo} a(n) / n^n = exp(-1/e - 3/(2*e^2)) * (1 - exp(-17/(6*e^3))).

a(n) = 17*Sum_{k=0..n} binomial(n,k)*(-1)^(k+1)*(n-k)^(n-k)*Sum_{j=1..floor(k/3)} binomial(k,3*j)*A362278(k-3*j)*17^(j-1)*(3*j)!/(6^j*j!) for n >= 3.

Maple

a := exp(-x-3*x^2/2)*(1-exp(-17*x^3/6)) / (1+LambertW(-x)):
ser := series(a, x = 0, 21): seq(n!*coeff(ser, x, n), n = 0 .. 20);

Prog

(Python)
from functools import lru_cache
from math import comb, factorial as fl
@lru_cache(None)
def b(n): return 1 if n < 2 else b(n-1) - 3*(n-1)*b(n-2)
def a(n):
    return 17*sum(comb(n, k)*(-1)**(k+1)*(n-k)**(n-k)*
        sum(comb(k, 3*j)*b(k-3*j)*17**(j-1)*fl(3*j)//(6**j*fl(j))
            for j in range(1, k//3+1))
        for k in range(n+1))
print([a(n) for n in range(21)])

Crossrefs

Column k=3 of triangle A347999.

Cf. A000169, A001865, A209324, A350134, A362278, A394928.

Sequence in context: A341690 A341689 A243776 * A338801 A198631 A185685

Adjacent sequences: A395669 A395670 A395671 * A395673 A395674 A395675

Keyword

nonn,easy

Author

Mélika Tebni, May 03 2026

Status

approved