A231536 Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} whose functional digraph has exactly k nodes such that no nonrecurrent element is mapped into it. n >= 1, 1 <= k <= n.

1, 2, 2, 6, 15, 6, 24, 108, 100, 24, 120, 840, 1340, 705, 120, 720, 7200, 17400, 15150, 5466, 720, 5040, 68040, 231000, 296100, 171402, 46921, 5040, 40320, 705600, 3198720, 5644800, 4687536, 2015272, 444648, 40320, 362880, 7983360, 46569600, 108168480, 121144464, 73191888, 25011576, 4625361, 362880

Offset

1,2

Links

Table of n, a(n) for n=1..45.

Natalia L. Skirrow, counting endofunctions on [n] with j trees and k leaves: interpreting a Lagrange inversion result, Mathematics StackExchange (2026)

Formula

E.g.f.: 1/(1 - A(x,y)) where A(x,y) is the e.g.f. for A055302.

T(n,k) = (n!/k!) * Sum_{j=1..k} (n-1)!/(n-j)! * j * Stirling2(n-j,n-k). - Natalia L. Skirrow, Feb 13 2026

Sum_{k=1..n} k * T(n,k) = n * A089901(n-1). - Natalia L. Skirrow, Feb 13 2026

Example

T(3,3) = 6 because we have: (1,2,3),(2,1,3),(3,2,1),(1,3,2),(2,3,1),(3,1,2).  In these 6 functions represented as a word there are 3 (all) elements with zero nonrecurrent elements mapped to them.
Triangle begins:
nk|  1    2     3     4    5   6
--+-----------------------------
 1|  1
 2|  2    2
 3|  6   15     6
 4| 24  108   100    24
 5|120  840  1340   705  120
 6|720 7200 17400 15150 5466 720
   ...

Mathematica

nn=6; Map[Select[#, #>0&]&, Drop[Range[0, nn]!CoefficientList[Series[1/(1- (-x+x y-ProductLog[-Exp[x (-1+y)] x])), {x, 0, nn}], {x, y}], 1]]//Grid

Prog

(Python)
from math import factorial as fact
from sympy.functions.combinatorial.numbers import stirling
A231536=lambda n, k: fact(n)//fact(k)*sum(fact(n-1)//fact(n-j)*j*stirling(n-j, n-k) for j in range(1, k+1)) # Natalia L. Skirrow, Feb 13 2026

Crossrefs

Row sums give: A000312.

Column k=1 and main diagonal give: A000142.

Sequence in context: A383084 A323233 A071208 * A216242 A330798 A260687

Adjacent sequences: A231533 A231534 A231535 * A231537 A231538 A231539

Keyword

nonn,tabl

Author

Geoffrey Critzer, Nov 10 2013

Status

approved