login
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.
3

%I #46 Jan 26 2022 11:11:34

%S 1,1,0,2,2,0,6,18,3,0,24,144,84,4,0,120,1200,1500,300,5,0,720,10800,

%T 23400,10800,930,6,0,5040,105840,352800,294000,63210,2646,7,0,40320,

%U 1128960,5362560,7056000,2857680,324576,7112,8,0,362880,13063680,83825280,160030080,105099120,23496480,1524600,18360,9,0

%N 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.

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

%C 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]

%C Row sums are n^n.

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

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

%F T(n,0) = n!.

%F 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.

%F 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

%F 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

%F From _Alois P. Heinz_, Jan 24 2022: (Start)

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

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

%e Triangle T(n,k) begins:

%e 1;

%e 1, 0;

%e 2, 2, 0;

%e 6, 18, 3, 0;

%e 24, 144, 84, 4, 0;

%e 120, 1200, 1500, 300, 5, 0;

%e 720, 10800, 23400, 10800, 930, 6, 0;

%e ...

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

%o (PARI) row(n) = vector(n+1, k, k--; n!/k! * stirling(n,n-k,2)); \\ _Michel Marcus_, Jan 24 2022

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

%Y Row sums give A000312.

%Y T(2n,n) gives A288312.

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

%K nonn,tabl

%O 0,4

%A _Geoffrey Critzer_, Dec 01 2012