A256116 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,6

LINKS

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

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.

EXAMPLE

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:

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;

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 *)

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.

Sequence in context: A352372 A219034 A372244 * A185410 A264676 A091803

Adjacent sequences: A256113 A256114 A256115 * A256117 A256118 A256119

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Mar 15 2015

STATUS

approved