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

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.

Links

Table of n, a(n) for n=1..45.

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

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

Example

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

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

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

Sequence in context: A286894 A346911 A225187 * A142473 A132426 A072646

Adjacent sequences: A281482 A281483 A281484 * A281486 A281487 A281488

Keyword

nonn,tabl

Author

Rui Duarte, Jan 22 2017

Status

approved