A373086 Triangle read by rows: T(n, k) is the number of parking functions of length n with preferences restricted to {1, ..., k} for 0 <= k <= n.

1, 0, 1, 0, 1, 3, 0, 1, 7, 16, 0, 1, 15, 61, 125, 0, 1, 31, 206, 671, 1296, 0, 1, 63, 659, 3130, 9031, 16807, 0, 1, 127, 2052, 13686, 54062, 144495, 262144, 0, 1, 255, 6297, 57867, 301321, 1059261, 2685817, 4782969, 0, 1, 511, 19162, 240049, 1616764, 7196785, 23343742, 56953279, 100000000

Offset

0,6

Comments

Equivalently, this is the number of preference lists of n cars on k spots so that only n - k cars are unable to park.

Links

Table of n, a(n) for n=0..54.

P. J. Cameron, D. Johannsen, T. Prellberg, and P. Schweitzer, Counting Defective Parking Functions, Electronic Journal of Combinatorics, Volume 15 (2008).

Formula

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

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

Example

Table begins:
  1;
  0, 1;
  0, 1,   3;
  0, 1,   7,    16;
  0, 1,  15,    61,    125;
  0, 1,  31,   206,    671,    1296;
  0, 1,  63,   659,   3130,    9031,   16807;
  0, 1, 127,  2052,  13686,   54062,  144495,   262144;
  0, 1, 255,  6297,  57867,  301321, 1059261,  2685817,  4782969;
  0, 1, 511, 19162, 240049, 1616764, 7196785, 23343742, 56953279, 100000000;
  ...

Crossrefs

Cf. A000272 (diagonal), A000225 (column 2), A355645 (column 3, with offset 3).

Cf. A260693 (first differences of columns).

Sequence in context: A261764 A216806 A290776 * A172249 A208758 A320161

Adjacent sequences: A373083 A373084 A373085 * A373087 A373088 A373089

Keyword

nonn,tabl

Author

Jayden Thadani and Alan Kappler, May 23 2024

Status

approved