login
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.
2
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,9
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-2i)!*(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
EXAMPLE
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
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 *)
PROG
(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
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.
Sequence in context: A220779 A347928 A317554 * A034366 A121465 A192396
KEYWORD
easy,nonn,tabl
AUTHOR
Paul Boddington, Nov 17 2003
STATUS
approved