A089975 Array read by ascending antidiagonals: T(n,k) is the number of n-letter words from a k-letter alphabet such that no letter appears more than twice.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 4, 3, 1, 0, 0, 6, 9, 4, 1, 0, 0, 6, 24, 16, 5, 1, 0, 0, 0, 54, 60, 25, 6, 1, 0, 0, 0, 90, 204, 120, 36, 7, 1, 0, 0, 0, 90, 600, 540, 210, 49, 8, 1, 0, 0, 0, 0, 1440, 2220, 1170, 336, 64, 9, 1, 0, 0, 0, 0, 2520, 8100, 6120, 2226, 504, 81, 10, 1

Offset: 0

Author

Paul Boddington, Nov 17 2003

Keywords

• easy
• nonn
• tabl

Examples

			Array begins:
  1, 1, 1,  1,    1,     1,      1,      1,       1,       1,       1, ...
  0, 1, 2,  3,    4,     5,      6,      7,       8,       9,      10, ...
  0, 1, 4,  9,   16,    25,     36,     49,      64,      81,     100, ...
  0, 0, 6, 24,   60,   120,    210,    336,     504,     720,     990, ...
  0, 0, 6, 54,  204,   540,   1170,   2226,    3864,    6264,    9630, ...
  0, 0, 0, 90,  600,  2220,   6120,  14070,   28560,   52920,   91440, ...
  0, 0, 0, 90, 1440,  8100,  29520,  83790,  201600,  430920,  842400, ...
  0, 0, 0,  0, 2520, 25200, 128520, 463680, 1345680, 3356640, 7484400, ...
  ... - _Robert FERREOL_, Nov 03 2017
		

Links

• Dennis Walsh, Width-Restricted Finite Functions

Crossrefs

T(1, k) = A001477(k); T(2, k) = A000290(k); T(3, k) = A007531(k); T(n, n) = A012244(n); T(n, n+1) = A036774(n); T(n, n+2) = A003692(n+1); T(2*n, n) = A000680(n); sum(T(n, k), n=0..2*k) = A003011(k); sum(T(r, n-r), r=0..n) = A089976(n).

See A141765 for an irregular triangle version : T(n,k)=A141765(k,n) for n <= 2k.

Programs

Maple

T:=(n,k)->add(n!*k!/(n-2*i)!/i!/(k-n+i)!/2^i,i=max(0,n-k)..n/2):
or
T:=proc(n,k) option remember :if n=0 then 1 elif n=1 then k elif k=0 then 0 else T(n, k-1)+n*T(n-1, k-1)+binomial(n,2)*T(n-2, k-1) fi end:
or
T:=(n,k)-> n!*coeff((1 + x + x^2/2)^k, x,n):
seq(seq(T(n-k,k),k=0..n),n=0..20);
# Robert FERREOL, Nov 07 2017

Mathematica

T[n_, k_] := Sum[n!*k!/(2^i*(n - 2 i)!*(k - n + i)!*i!), {i, Max[0, n - k], Floor[n/2]}];
Table[T[n-k , k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 05 2017, after Robert FERREOL *)

Python

from math import factorial as f
def T(n,k):
    return sum(f(n)*f(k)//f(n-2*i)//f(i)//f(k-n+i)//2**i for i in range(max(0,n-k),n//2+1))
[T(n-k,k) for n in range(21) for k in range(n+1)]
# Robert FERREOL, Oct 17 2017

Formula

T(n, k) = T(n, k-1) + n*T(n-1, k-1) + binomial(n, 2)*T(n-2, k-1) for n >= 2 and k >= 1.

T(n, k) = Sum_{i=max(0,n-k)..floor(n/2)} n!*k!/(2^i*(n-2*i)!*(k-n+i)!*i!). - Robert FERREOL, Oct 30 2017

T(n,k) = (-1)^n*n!*2^(-n/2)*GegenbauerC(n, -k, 1/sqrt(2)) for k >= n. - Robert Israel, Nov 08 2017

G.f.: Sum({n>=0} T(n,k)x^n)=n!(1 + x + x^2/2)^k. See Walsh link. - Robert FERREOL, Nov 14 2017