OFFSET
1,3
COMMENTS
T(n,k) is the number of n-letter words in a k-letter alphabet with no adjacent letters the same. The factor k represents the number of choices of the first letter, and the n-1 times repeated factor k-1 represents the choices of the next n-1 letters avoiding their predecessor.
The antidiagonal sums are s(d) = 1, 2, 5, 12, 31, 88, 275, 942, 3513, 14158, 61241, 282632, .. for d = n+k >= 2.
LINKS
Robert Israel, Table of n, a(n) for n = 1..10011(first 141 antidiagonals, flattened)
FORMULA
G.f. for column k: k*x/(1-(k-1)*x). - R. J. Mathar, Dec 12 2015
G.f. for array: y/(y-1) - (1+1/x)*y*LerchPhi(y,1,-1/x). - Robert Israel, Dec 13 2018
EXAMPLE
1 2 3 4 5 6 7
0 2 6 12 20 30 42
0 2 12 36 80 150 252
0 2 24 108 320 750 1512
0 2 48 324 1280 3750 9072
0 2 96 972 5120 18750 54432
0 2 192 2916 20480 93750 326592
T(3,3)=12 counts aba, abc, aca, acb, bab, bac, bca, bcb, cab, cac, cba, cbc. Words like aab or cbb are not counted.
MAPLE
MATHEMATICA
T[1, 1] = 1; T[n_, k_] := If[k==1, 0, k*(k-1)^(n-1)]; Table[T[n-k, k], {n, 2, 12}, {k, 1, n-1}] // Flatten (* Amiram Eldar, Dec 13 2018 *)
PROG
(PARI) T(n, k) = if(n==k==1, 1, k*(k-1)^(n-k-1) );
for(n=2, 15, for(k=1, n-1, print1(T(n, k), ", "))) \\ G. C. Greubel, Aug 10 2019
(Magma)
T:= func< n, k | (n eq 1 and k eq 1) select 1 else k*(k-1)^(n-k-1) >;
[T(n, k): k in [1..n-1], n in [2..15]]; // G. C. Greubel, Aug 10 2019
(Sage)
def T(n, k):
if (n==k==1): return 1
else: return k*(k-1)^(n-k-1)
[[T(n, k) for k in (1..n-1)] for n in (2..15)] # G. C. Greubel, Aug 10 2019
(GAP)
T:= function(n, k)
if (n=1 and k=1) then return 1;
else return k*(k-1)^(n-k-1);
fi;
end;
Flat(List([2..15], n-> List([1..n-1], k-> T(n, k) ))); # G. C. Greubel, Aug 10 2019
CROSSREFS
KEYWORD
AUTHOR
R. J. Mathar, Dec 10 2015
STATUS
approved