A264902 Number T(n,k) of defective parking functions of length n and defect k; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

1, 1, 3, 1, 16, 10, 1, 125, 107, 23, 1, 1296, 1346, 436, 46, 1, 16807, 19917, 8402, 1442, 87, 1, 262144, 341986, 173860, 41070, 4320, 162, 1, 4782969, 6713975, 3924685, 1166083, 176843, 12357, 303, 1, 100000000, 148717762, 96920092, 34268902, 6768184, 710314, 34660, 574, 1

Offset: 0

Author

Alois P. Heinz, Nov 28 2015

Keywords

• nonn
• tabf
• easy

Examples

			T(2,0) = 3: [1,1], [1,2], [2,1].
T(2,1) = 1: [2,2].
T(3,1) = 10: [1,3,3], [2,2,2], [2,2,3], [2,3,2], [2,3,3], [3,1,3], [3,2,2], [3,2,3], [3,3,1], [3,3,2].
T(3,2) = 1: [3,3,3].
Triangle T(n,k) begins:
0 :       1;
1 :       1;
2 :       3,       1;
3 :      16,      10,       1;
4 :     125,     107,      23,       1;
5 :    1296,    1346,     436,      46,      1;
6 :   16807,   19917,    8402,    1442,     87,     1;
7 :  262144,  341986,  173860,   41070,   4320,   162,   1;
8 : 4782969, 6713975, 3924685, 1166083, 176843, 12357, 303, 1;
    ...
		

Links

• Alois P. Heinz, Rows n = 0..141, flattened
• Peter J. Cameron, Daniel Johannsen, Thomas Prellberg, Pascal Schweitzer, Counting Defective Parking Functions, arXiv:0803.0302 [math.CO], 2008

Crossrefs

Columns k=0-10 give: A000272(n+1), A140647, A291128, A291129, A291130, A291131, A291132, A291133, A291134, A291135, A291136.

Row sums give A000312.

T(2n,n) gives A264903.

Cf. A036276, A101334, A274279.

Programs

Maple

S:= (n, k)-> `if`(k=0, n^n, add(binomial(n, i)*k*
            (k+i)^(i-1)*(n-k-i)^(n-i), i=0..n-k)):
T:= (n, k)-> S(n, k)-S(n, k+1):
seq(seq(T(n, k), k=0..max(0, n-1)), n=0..10);

Mathematica

S[n_, k_] := If[k==0, n^n, Sum[Binomial[n, i]*k*(k+i)^(i-1)*(n-k-i)^(n-i), {i, 0, n-k}]]; T[n_, k_] := S[n, k]-S[n, k+1]; T[0, 0] = 1; Table[T[n, k], {n, 0, 10}, {k, 0, Max[0, n-1]}] // Flatten (* Jean-François Alcover, Feb 18 2017, translated from Maple *)

Formula

T(n,k) = S(n,k) - S(n,k+1) with S(n,0) = n^n, S(n,k) = Sum_{i=0..n-k} C(n,i) * k*(k+i)^(i-1) * (n-k-i)^(n-i) for k>0.

Sum_{k>0} k * T(n,k) = A036276(n-1) for n>0.

Sum_{k>0} T(n,k) = A101334(n).

Sum_{k>=0} (-1)^k * T(n,k) = A274279(n) for n>=1.