A256116 Number T(n,k) of length 2n k-ary words, either empty or beginning with the first letter of the alphabet and using each letter at least once, that can be built by repeatedly inserting doublets into the initially empty word; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 2, 0, 1, 9, 10, 0, 1, 34, 112, 84, 0, 1, 125, 930, 1800, 1008, 0, 1, 461, 7018, 26400, 35640, 15840, 0, 1, 1715, 51142, 334152, 816816, 840840, 308880, 0, 1, 6434, 368464, 3944220, 15550080, 27824160, 23063040, 7207200

Offset: 0

Author

Alois P. Heinz, Mar 15 2015

Keywords

• nonn
• tabl

Examples

			T(3,2) = 9: aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba.
T(3,3) = 10: aabbcc, aabccb, aacbbc, aaccbb, abbacc, abbcca, abccba, acbbca, accabb, accbba.
T(4,2) = 34: aaaaaabb, aaaaabba, aaaabaab, aaaabbaa, aaaabbbb, aaabaaba, aaabbaaa, aaabbabb, aaabbbba, aabaaaab, aabaabaa, aabaabbb, aababbab, aabbaaaa, aabbaabb, aabbabba, aabbbaab, aabbbbaa, aabbbbbb, abaaaaba, abaabaaa, abaababb, abaabbba, ababbaba, abbaaaaa, abbaaabb, abbaabba, abbabaab, abbabbaa, abbabbbb, abbbaaba, abbbbaaa, abbbbabb, abbbbbba.
T(4,4) = 84: aabbccdd, aabbcddc, aabbdccd, aabbddcc, aabccbdd, aabccddb, aabcddcb, aabdccdb, aabddbcc, aabddccb, aacbbcdd, aacbbddc, aacbddbc, aaccbbdd, aaccbddb, aaccdbbd, aaccddbb, aacdbbdc, aacddbbc, aacddcbb, aadbbccd, aadbbdcc, aadbccbd, aadcbbcd, aadccbbd, aadccdbb, aaddbbcc, aaddbccb, aaddcbbc, aaddccbb, abbaccdd, abbacddc, abbadccd, abbaddcc, abbccadd, abbccdda, abbcddca, abbdccda, abbddacc, abbddcca, abccbadd, abccbdda, abccddba, abcddcba, abdccdba, abddbacc, abddbcca, abddccba, acbbcadd, acbbcdda, acbbddca, acbddbca, accabbdd, accabddb, accadbbd, accaddbb, accbbadd, accbbdda, accbddba, accdbbda, accddabb, accddbba, acdbbdca, acddbbca, acddcabb, acddcbba, adbbccda, adbbdacc, adbbdcca, adbccbda, adcbbcda, adccbbda, adccdabb, adccdbba, addabbcc, addabccb, addacbbc, addaccbb, addbbacc, addbbcca, addbccba, addcbbca, addccabb, addccbba.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,    2;
  0, 1,    9,    10;
  0, 1,   34,   112,     84;
  0, 1,  125,   930,   1800,   1008;
  0, 1,  461,  7018,  26400,  35640,  15840;
  0, 1, 1715, 51142, 334152, 816816, 840840, 308880;
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Columns k=0-2 give: A000007, A057427, A010763(n-1) for n>0.

Main diagonal gives A065866(n-1) (for n>0).

Row sums give A294603.

Cf. A183135, A256117.

Programs

Maple

A:= proc(n, k) option remember; `if`(n=0, 1, k/n*
      add(binomial(2*n, j) *(n-j) *(k-1)^j, j=0..n-1))
    end:
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k)/
    `if`(k=0, 1, k):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

Unprotect[Power]; 0^0 = 1; A[n_, k_] := A[n, k] = If[n==0, 1, k/n*Sum[ Binomial[2*n, j]*(n-j)*(k-1)^j, {j, 0, n-1}]];
T[n_, k_] := Sum[A[n, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}]/If[k==0, 1, k]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 22 2017, translated from Maple *)

Formula

T(n,k) = (Sum_{i=0..k} (-1)^i * C(k,i) * A183135(n,k-i)) / A028310(k).

T(n,k) = (k-1)! * A256117(n,k) for k > 0.