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

1, 1, 0, 2, 2, 0, 6, 18, 3, 0, 24, 144, 84, 4, 0, 120, 1200, 1500, 300, 5, 0, 720, 10800, 23400, 10800, 930, 6, 0, 5040, 105840, 352800, 294000, 63210, 2646, 7, 0, 40320, 1128960, 5362560, 7056000, 2857680, 324576, 7112, 8, 0, 362880, 13063680, 83825280, 160030080, 105099120, 23496480, 1524600, 18360, 9, 0

Offset

0,4

Comments

Equivalently, T(n,k) is the number of endofunctions whose functional digraph has exactly k leaves.

Equivalently, T(n,k) is the number of doubly rooted trees with k leaves. Here, a doubly rooted tree is a labeled tree in which two special vertices have been selected and the order of the selection matters. [Bona page 266]

Row sums are n^n.

References

M. Bona, Introduction to Enumerative Combinatorics, McGraw Hill, 2007.

Links

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

Formula

T(n,k) = n!/k! * Stirling2(n,n-k).

T(n,0) = n!.

T(n,k) = A055302(n,k)*(n-k) + A055302(n,k+1)*(k+1). The first term (on rhs of this equation) is the number of such functions in which the preimage of f(n) contains more than one element. The second term is the number of such functions in which the preimage of f(n) contains exactly one element.

T(n,k) = binomial(n,k) Sum_{j=0..n-k}(-1)^j*binomial(n-k,j)*(n-k-j)^n. - Geoffrey Critzer, Aug 20 2013

E.g.f.: 1/(1 - (A(x,y) - y*x + x)) where A(x,y) is the e.g.f. for A055302. - Geoffrey Critzer, Jan 24 2022

From Alois P. Heinz, Jan 24 2022: (Start)

Sum_{k=0..n} k * T(n,k) = A209290(n).

Sum_{k=0..n} (-1)^k * T(n,k) = A344053(n). (End)

Example

Triangle T(n,k) begins:
    1;
    1,     0;
    2,     2,     0;
    6,    18,     3,     0;
   24,   144,    84,     4,   0;
  120,  1200,  1500,   300,   5, 0;
  720, 10800, 23400, 10800, 930, 6, 0;
  ...

Mathematica

Table[Table[n!/k!StirlingS2[n, n-k], {k, 0, n}], {n, 0, 8}]//Grid

Prog

(PARI) row(n) = vector(n+1, k, k--; n!/k! * stirling(n, n-k, 2)); \\ Michel Marcus, Jan 24 2022

Crossrefs

Column k=0-1 give: A000142, A001804.

Row sums give A000312.

T(2n,n) gives A288312.

Cf. A055302, A055314, A090657, A101817, A209290, A344053.

Sequence in context: A292317 A285675 A361488 * A366230 A168615 A334921

Adjacent sequences: A219856 A219857 A219858 * A219860 A219861 A219862

Keyword

nonn,tabl

Author

Geoffrey Critzer, Dec 01 2012

Status

approved