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,5

Comments

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

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

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

Example

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

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

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.

Sequence in context: A244129 A363907 A342987 * A167001 A108563 A138476

Adjacent sequences: A090654 A090655 A090656 * A090658 A090659 A090660

Keyword

easy,nonn,tabl

Author

Philippe Deléham, Dec 14 2003

Extensions

Revised description from Jan Maciak, Apr 25 2004

Edited by Alois P. Heinz, Jan 17 2011

Status

approved