A089975 - OEIS

%I #45 May 16 2021 08:03:28

%S 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,

%T 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,

%U 0,1440,2220,1170,336,64,9,1,0,0,0,0,2520,8100,6120,2226,504,81,10,1

%N 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.

%H Dennis Walsh, <a href="http://capone.mtsu.edu/dwalsh/WIDTH_2.pdf">Width-Restricted Finite Functions</a>

%F 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.

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

%F T(n,k) = (-1)^n*n!*2^(-n/2)*GegenbauerC(n, -k, 1/sqrt(2)) for k >= n. - _Robert Israel_, Nov 08 2017

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

%e Array begins:

%e 1, 1, 1,  1,    1,     1,      1,      1,       1,       1,       1, ...

%e 0, 1, 2,  3,    4,     5,      6,      7,       8,       9,      10, ...

%e 0, 1, 4,  9,   16,    25,     36,     49,      64,      81,     100, ...

%e 0, 0, 6, 24,   60,   120,    210,    336,     504,     720,     990, ...

%e 0, 0, 6, 54,  204,   540,   1170,   2226,    3864,    6264,    9630, ...

%e 0, 0, 0, 90,  600,  2220,   6120,  14070,   28560,   52920,   91440, ...

%e 0, 0, 0, 90, 1440,  8100,  29520,  83790,  201600,  430920,  842400, ...

%e 0, 0, 0,  0, 2520, 25200, 128520, 463680, 1345680, 3356640, 7484400, ...

%e ... - _Robert FERREOL_, Nov 03 2017

%p T:=(n,k)->add(n!*k!/(n-2*i)!/i!/(k-n+i)!/2^i,i=max(0,n-k)..n/2):

%p or

%p 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:

%p or

%p T:=(n,k)-> n!*coeff((1 + x + x^2/2)^k, x,n):

%p seq(seq(T(n-k,k),k=0..n),n=0..20);

%p # _Robert FERREOL_, Nov 07 2017

%t T[n_, k_] := Sum[n!*k!/(2^i*(n - 2 i)!*(k - n + i)!*i!), {i, Max[0, n - k], Floor[n/2]}];

%t Table[T[n-k , k], {n, 0, 11}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Dec 05 2017, after _Robert FERREOL_ *)

%o (Python)

%o from math import factorial as f

%o def T(n,k):

%o     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))

%o [T(n-k,k) for n in range(21) for k in range(n+1)]

%o # _Robert FERREOL_, Oct 17 2017

%Y 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).

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

%K easy,nonn,tabl

%O 0,9

%A _Paul Boddington_, Nov 17 2003