A288312 -id:A288312 - cp's OEIS frontend

A090657 Triangle read by rows: T(n,k) = number of functions from [1,2,...,n] to [1,2,...,n] such that the image contains exactly k elements (0<=k<=n).

1, 0, 1, 0, 2, 2, 0, 3, 18, 6, 0, 4, 84, 144, 24, 0, 5, 300, 1500, 1200, 120, 0, 6, 930, 10800, 23400, 10800, 720, 0, 7, 2646, 63210, 294000, 352800, 105840, 5040, 0, 8, 7112, 324576, 2857680, 7056000, 5362560, 1128960, 40320

Offset: 0

Philippe Deléham, Dec 14 2003

Another version is in A101817. - Philippe Deléham, Feb 16 2013

			Triangle begins:
  1;
  0,  1;
  0,  2,   2;
  0,  3,  18,   6;
  0,  4,  84, 144, 24;
  ...

Alois P. Heinz, Rows n = 0..62, flattened
C. M. Ringel, The Catalan combinatorics of the hereditary artin algebras, arXiv preprint arXiv:1502.06553, 2015

Row sums give: A000312. Columns k=0-2 give: A000007, A001477, A068605. Diagonal, lower diagonal give: A000142, A001804. Cf. A007318, A048993, A019538, A008279.

Cf. A101817, A288312.

T:= proc(n,k) option remember;
      if k=n then n!
    elif k=0 or k>n then 0
    else n * (T(n-1,k-1) + k/(n-k) * T(n-1,k))
      fi
    end:
seq(seq(T(n,k), k=0..n), n=0..10);

Table[Table[StirlingS2[n, k] Binomial[n, k] k!, {k, 0, n}], {n, 0,10}] // Flatten  (* Geoffrey Critzer, Sep 09 2011 *)

T(n,k) = C(n,k) * k! * A048993(n,k).
T(n,k) = A008279(n,k) * A048993(n,k).
T(n,k) = C(n,k) * A019538(n, k).
T(n,k) = C(n,k) * Sum_{j=0..k} (-1)^(k-j) * C(k,j) * j^n.
T(n,k) = n * (T(n-1,k-1) + k/(n-k) * T(n-1,k)) with T(n,n) = n! and T(n,0) = 0 for n>0.
T(2n,n) = A288312(n). - Alois P. Heinz, Jun 07 2017

Revised description from Jan Maciak, Apr 25 2004

Edited by Alois P. Heinz, Jan 17 2011

A101817 Triangle read by rows: T(n,h) = number of functions f:{1,2,...,n}->{1,2,...,n} such that |Image(f)|=h; h=1,2,...,n, n=1,2,3,... . Essentially A090657, but without zeros.

Original entry on oeis.org

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

Offset: 1

Clark Kimberling, Dec 17 2004

Row sums = n^n. T(n,1) = n, T(n,n) = n!.

			First rows:
1;
2,   2;
3,  18,   6;
4,  84, 144,  24;

H. Picquet, Note #124, L'Intermédiaire des Mathématiciens, 1 (1894), pp. 125-127. - N. J. A. Sloane, Feb 28 2022

Cf. A090657, A048993, A101818, A101819, A101821, A288312.

Table[Table[StirlingS2[n, k] Binomial[n, k] k!, {k, 1, n}], {n, 1, 8}] // Grid

T(n, h) = C(n, h)*U(n, h), where U(n, h) is the array in A019538. Thus T(n, h) = C(n, h)*h!*S(n, h), where S(n, h) is a Stirling number of the second kind (given by A048993 with zeros removed).

T(2n,n) = A288312(n). - Alois P. Heinz, Jun 07 2017

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.

Original entry on oeis.org

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

Geoffrey Critzer, Dec 01 2012

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.

			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;
  ...

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

Column k=0-1 give: A000142, A001804.
Row sums give A000312.
T(2n,n) gives A288312.
Cf. A055302, A055314, A090657, A101817, A209290, A344053.

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

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

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)

cp's OEIS Frontend

A090657 Triangle read by rows: T(n,k) = number of functions from [1,2,...,n] to [1,2,...,n] such that the image contains exactly k elements (0<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A101817 Triangle read by rows: T(n,h) = number of functions f:{1,2,...,n}->{1,2,...,n} such that |Image(f)|=h; h=1,2,...,n, n=1,2,3,... . Essentially A090657, but without zeros.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

PARI

Formula