cp's OEIS Frontend

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.

%I A089975 #51 Jan 13 2025 06:37:05
%S A089975 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 A089975 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 A089975 0,1440,2220,1170,336,64,9,1,0,0,0,0,2520,8100,6120,2226,504,81,10,1
%N 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.
%H A089975 Dennis Walsh, <a href="http://capone.mtsu.edu/dwalsh/WIDTH_2.pdf">Width-Restricted Finite Functions</a>
%F A089975 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 A089975 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
%F A089975 T(n,k) = (-1)^n*n!*2^(-n/2)*GegenbauerC(n, -k, 1/sqrt(2)) for k >= n. - _Robert Israel_, Nov 08 2017
%F A089975 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 A089975 Array begins:
%e A089975   1, 1, 1,  1,    1,     1,      1,      1,       1,       1,       1, ...
%e A089975   0, 1, 2,  3,    4,     5,      6,      7,       8,       9,      10, ...
%e A089975   0, 1, 4,  9,   16,    25,     36,     49,      64,      81,     100, ...
%e A089975   0, 0, 6, 24,   60,   120,    210,    336,     504,     720,     990, ...
%e A089975   0, 0, 6, 54,  204,   540,   1170,   2226,    3864,    6264,    9630, ...
%e A089975   0, 0, 0, 90,  600,  2220,   6120,  14070,   28560,   52920,   91440, ...
%e A089975   0, 0, 0, 90, 1440,  8100,  29520,  83790,  201600,  430920,  842400, ...
%e A089975   0, 0, 0,  0, 2520, 25200, 128520, 463680, 1345680, 3356640, 7484400, ...
%e A089975   ... - _Robert FERREOL_, Nov 03 2017
%p A089975 T:=(n,k)->add(n!*k!/(n-2*i)!/i!/(k-n+i)!/2^i,i=max(0,n-k)..n/2):
%p A089975 or
%p A089975 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 A089975 or
%p A089975 T:=(n,k)-> n!*coeff((1 + x + x^2/2)^k, x,n):
%p A089975 seq(seq(T(n-k,k),k=0..n),n=0..20);
%p A089975 # _Robert FERREOL_, Nov 07 2017
%t A089975 T[n_, k_] := Sum[n!*k!/(2^i*(n - 2 i)!*(k - n + i)!*i!), {i, Max[0, n - k], Floor[n/2]}];
%t A089975 Table[T[n-k , k], {n, 0, 11}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Dec 05 2017, after _Robert FERREOL_ *)
%o A089975 (Python)
%o A089975 from math import factorial as f
%o A089975 def T(n,k):
%o A089975     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 A089975 [T(n-k,k) for n in range(21) for k in range(n+1)]
%o A089975 # _Robert FERREOL_, Oct 17 2017
%Y A089975 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 A089975 See A141765 for an irregular triangle version : T(n,k)=A141765(k,n) for n <= 2k.
%K A089975 easy,nonn,tabl
%O A089975 0,9
%A A089975 _Paul Boddington_, Nov 17 2003