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