A219694 Triangular array read by rows: T(n,k) is the number of functions f:{1,2,...,n} -> {1,2,...,n} that have exactly k nonrecurrent elements; n>=1, 0<=k<=n-1.

1, 2, 2, 6, 12, 9, 24, 72, 96, 64, 120, 480, 900, 1000, 625, 720, 3600, 8640, 12960, 12960, 7776, 5040, 30240, 88200, 164640, 216090, 201684, 117649, 40320, 282240, 967680, 2150400, 3440640, 4128768, 3670016, 2097152, 362880, 2903040, 11430720, 29393280, 55112400, 79361856, 89282088, 76527504, 43046721

Offset

1,2

Comments

x in {1,2,...,n} is a recurrent element if there is some k such that f^k(x) = x where f^k(x) denotes iterated functional composition. In other words, a recurrent element is in a cycle of the functional digraph. An element that is not recurrent is a nonrecurrent element.

Links

Alois P. Heinz, Rows n = 1..141, flattened

Philippe Flajolet, Peter J. Grabner, Peter Kirschenhofer, and Helmut Prodinger, On Ramanujan's Q-function, Journal of Computational and Applied Mathematics, vol. 58, iss. 1 (1995-03-20), pp. 103-116.

Formula

E.g.f.: 1/(1-x*exp(A(x*y))), where A(x) = Sum_{n>=1} n^(n-1)*x^n/n! is Euler's tree function.

From Natalia L. Skirrow, Mar 03 2026: (Start)

T(n,k) = A066324(n,n-k) = (n-k)*n^k*(n-1)!/k!.

Let Q(n) = Sum_{k=1..n} n!/((n-k)!*n^k) ~ sqrt(Pi*n/2) (Ramanujan's Q function).

With all sums ranging over k=0..n-1:

Sum T(n,k) = A000312(n) = n^n.

Sum T(n,k)*k = A219706(n) = n^n*(n-Q(n)) = Sum T(n,k)*C(n-k,2).

Sum T(n,k)*(k+1) = A369071(n) = n^n*(n-Q(n)+1).

Sum T(n,k)*C(k,2) = n^(n+1)*((n+1)/2-Q(n)).

Sum T(n,k)*(-1)^k = A277458(n)*(-1)^(n-1).

n-th row has mean n - Q(n) and variance 2*n - Q(n)*(1+Q(n)) ~ (2-Pi/2)*n. (End)

Example

T(2,1) = 2 because we have 1->1 2->1; and 1->2 2->2.
  n\k  0     1     2      3      4      5      6
  -+--------------------------------------------
  1|   1     .     .      .      .      .      .
  2|   2     2     .      .      .      .      .
  3|   6    12     9      .      .      .      .
  4|  24    72    96     64      .      .      .
  5| 120   480   900   1000    625      .      .
  6| 720  3600  8640  12960  12960   7776      .
  7|5040 30240 88200 164640 216090 201684 117649

Maple

b:= proc(n) option remember; `if`(n=0, 1, add(
      (j-1)!*b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n-1))(add(
    b(j)*(x*n)^(n-j)*binomial(n-1, j-1), j=0..n)):
seq(T(n), n=1..10);  # Alois P. Heinz, May 22 2016

Mathematica

nn=8; f[list_]:=Select[list, #>0&]; t=Sum[n^(n-1)x^n y^n/n!, {n, 1, nn}]; Drop[Map[f, Range[0, nn]!CoefficientList[Series[1/(1-x Exp[t]), {x, 0, nn}], {x, y}]], 1]//Grid

Prog

(Python)
from math import factorial as fact
A219694=lambda n, k: fact(n-1)//fact(k)*(n-k)*n**k # Natalia L. Skirrow, Mar 03 2026
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def T(n: int, k: int) -> int:
    if n == 1: return 1
    if k == 0: return n * T(n - 1, 0)
    numer = (n ** k) * (n - 1) * T(n - 1, k - 1)
    denom = ((n - 1) ** (k - 1)) * k
    return numer // denom
for n in range(1, 8): print([T(n, k) for k in range(n)]) # Peter Luschny, Mar 05 2026

Crossrefs

Cf. A000312, A063169, A219706, A007778, A262970.

Cf. A066324 (row reversals).

Cf. A216971 (counts nonrecurrent preimages of recurrent nodes).

Sequence in context: A156992 A285529 A305215 * A054481 A262501 A225422

Adjacent sequences: A219691 A219692 A219693 * A219695 A219696 A219697

Keyword

nonn,tabl,easy

Author

Geoffrey Critzer, Nov 25 2012

Status

approved