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

Author

Philippe Deléham, Dec 14 2003

Keywords

• easy
• nonn
• tabl

Comments

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

Examples

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

Links

• 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

Crossrefs

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.

Programs

Maple

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

Mathematica

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

Formula

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

Extensions

Revised description from Jan Maciak, Apr 25 2004

Edited by Alois P. Heinz, Jan 17 2011