A281485 Triangular array T(n,k) = k Sum_{j=0..k-1} (-1)^j binomial(k-1,j) (n-1-j)^(n-1), 1<=k<=n, read by rows.

1, 1, 2, 4, 6, 6, 27, 38, 36, 24, 256, 350, 330, 240, 120, 3125, 4202, 3960, 3000, 1800, 720, 46656, 62062, 58506, 45360, 29400, 15120, 5040, 823543, 1087214, 1025388, 806904, 546000, 312480, 141120, 40320, 16777216, 22024830, 20781690, 16524144, 11493720, 6985440, 3598560, 1451520, 362880

Offset: 1

Author

Rui Duarte, Jan 22 2017

Keywords

• nonn
• tabl

Comments

A parking function of size n is a sequence (a_1,...,a_n) of positive integers such that, if b_1 <= b_2 <= ... <= b_n is the increasing rearrangement of the sequence (a_1,..,a_n), then b_i <= i.

Given a:[n]->[n], the center of a is the largest subset Z(a) = { z_1, ..., z_k } of [n] such that z_1 < z_2 < ... < z_k and a_(z_j) <= j, for every j in [k]. The length of the center of a is |Z(a)|.

Then T(n,k)= number of parking functions of size n with center of length k.

Examples

			First seven rows:
      1
      1      2
      4      6      6
     27     38     36     24
    256    350    330    240    120
   3125   4202   3960   3000   1800    720
  46656  62062  58506  45360  29400  15120   5040
		

Links

• Rui Duarte and António Guedes de Oliveira, The number of parking functions with center of a given length, arXiv:1611.03707 (2016).

Crossrefs

T(n,k) = k * A174551(n-1,k-1).

T(n,1) = (n-1)^(n-1) = A000312(n-1).

T(n,n-1) = n!(n-1)/2 = A001286(n), n>=2.

T(n,n) = n! = A000142(n).

Sum_{i=1,...,n} T(n,i) = (n+1)^(n-1) = A000272(n+1).

Programs

Mathematica

Table[Which[n == k == 1, 1, k == 1, (n - 1)^(n - 1), k == n, n!, True, k Sum[(-1)^j*Binomial[k - 1, j] (n - 1 - j)^(n - 1), {j, 0, k - 1}]], {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, Jan 23 2017 *)

Formula

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

T(n,k) = k!*Sum_{j_1+j_2+...+j_k=n-k} (n-1)^(j_1)*(n-2)^(j_2)*...*(n-k)^(j_k).