A256117 -id:A256117 - cp's OEIS frontend

A183135 Square array A(n,k) by antidiagonals. A(n,k) is the number of length 2n k-ary words (n,k>=0) that can be built by repeatedly inserting doublets into the initially empty word.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 15, 20, 1, 0, 1, 5, 28, 87, 70, 1, 0, 1, 6, 45, 232, 543, 252, 1, 0, 1, 7, 66, 485, 2092, 3543, 924, 1, 0, 1, 8, 91, 876, 5725, 19864, 23823, 3432, 1, 0, 1, 9, 120, 1435, 12786, 71445, 195352, 163719, 12870, 1, 0

Offset: 0

Alois P. Heinz, Dec 26 2010

A(n,k) is also the number of rooted closed walks of length 2n on the infinite rooted k-ary tree. - Danny Rorabaugh, Oct 31 2017

A(n,2k) is the number of unreduced words of length 2n that reduce to the empty word in the free group with k generators. - Danny Rorabaugh, Nov 09 2017

			A(2,2) = 6, because 6 words of length 4 can be built over 2-letter alphabet {a, b} by repeatedly inserting doublets (words with two equal letters) into the initially empty word: aaaa, aabb, abba, baab, bbaa, bbbb.
Square array A(n,k) begins:
  1,  1,   1,    1,     1,     1,  ...
  0,  1,   2,    3,     4,     5,  ...
  0,  1,   6,   15,    28,    45,  ...
  0,  1,  20,   87,   232,   485,  ...
  0,  1,  70,  543,  2092,  5725,  ...
  0,  1, 252, 3543, 19864, 71445,  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Jason Bell, Marni Mishna, On the Complexity of the Cogrowth Sequence, arXiv:1805.08118 [math.CO], 2018.
Beth Bjorkman et al., k-foldability of words, arXiv preprint arXiv:1710.10616 [math.CO], 2017.

Columns k=0-10 give: A000007, A000012, A000984, A089022, A035610, A130976, A130977, A130978, A130979, A130980, A131521.
Rows n=0-3 give: A000012, A001477, A000384, A027849(k-1) for k>0.
Main diagonal gives A294491.
Coefficients of row polynomials in k, (k-1) are given by A157491, A039599.
Cf. A007318, A183134, A256116, A256117.

A:= proc(n, k) local j;
      if n=0 then 1
             else k/n *add(binomial(2*n,j) *(n-j) *(k-1)^j, j=0..n-1)
      fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[, 1] = 1; A[n, k_] := If[n == 0, 1, k/n*Sum[Binomial[2*n, j]*(n - j)*(k - 1)^j, {j, 0, n - 1}]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

A(n,k) = k/n * Sum_{j=0..n-1} C(2*n,j)*(n-j)*(k-1)^j if n>0, A(0,k) = 1.
A(n,k) = A183134(n,k) if n=0 or k<2, A(n,k) = A183134(n,k)*k otherwise.
G.f. of column k: 1/(1-k*x) if k<2, 2*(k-1)/(k-2+k*sqrt(1-(4*k-4)*x)) otherwise.

A256311 Number T(n,k) of length 3n words such that all letters of the k-ary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting triples of identical letters into the initially empty word; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 1, 18, 12, 0, 1, 97, 198, 55, 0, 1, 530, 2520, 1820, 273, 0, 1, 2973, 29886, 42228, 15300, 1428, 0, 1, 17059, 347907, 859180, 564585, 122094, 7752, 0, 1, 99657, 4048966, 16482191, 17493938, 6577494, 942172, 43263

Offset: 0

Alois P. Heinz, Mar 25 2015

			T(0,0) = 1: (the empty word).
T(1,1) = 1: aaa.
T(2,1) = 1: aaaaaa.
T(2,2) = 3: aaabbb, aabbba, abbbaa.
T(3,1) = 1: aaaaaaaaa.
T(3,2) = 18: aaaaaabbb, aaaaabbba, aaaabbbaa, aaabaaabb, aaabbaaab, aaabbbaaa, aaabbbbbb, aabaaabba, aabbaaaba, aabbbaaaa, aabbbabbb, aabbbbbba, abaaabbaa, abbaaabaa, abbbaaaaa, abbbaabbb, abbbabbba, abbbbbbaa.
T(3,3) = 12: aaabbbccc, aaabbcccb, aaabcccbb, aabbbaccc, aabbbccca, aabbcccba, aabcccbba, abbbaaccc, abbbaccca, abbbcccaa, abbcccbaa, abcccbbaa.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,     3;
  0, 1,    18,     12;
  0, 1,    97,    198,     55;
  0, 1,   530,   2520,   1820,    273;
  0, 1,  2973,  29886,  42228,  15300,   1428;
  0, 1, 17059, 347907, 859180, 564585, 122094, 7752;

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

Columns k=0-10 give: A000007, A057427, A321032, A321033, A321034, A321035, A321036, A321037, A321038, A321039, A321040.
Row sums give A321031.
Main diagonal gives A001764.
T(2n,n) gives A321041.
Cf. A256117, A213028.

A:= (n, k)-> `if`(n=0, 1,
    k/n *add(binomial(3*n, j) *(n-j) *(k-1)^j, j=0..n-1)):
T:= (n, k)-> add((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

T(n,k) = Sum_{i=0..k} (-1)^i * A213028(n,k-i) / (i!*(k-i)!).

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.

Original entry on oeis.org

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

Alois P. Heinz, Mar 15 2015

			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;

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

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.

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

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

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.

A258498 Number of words of length 2n such that the index set of occurring letters is {1, 2, ..., k}, all letters are introduced in ascending order, and the words can be built by repeatedly inserting doublets into the initially empty word.

Original entry on oeis.org

1, 1, 3, 15, 105, 933, 9988, 124449, 1761287, 27813479, 483482018, 9153385959, 187129080977, 4102129113670, 95861136747795, 2376234441556411, 62216635372018209, 1714347701138957189, 49553280367466054768, 1498300016807379304877, 47270249397381096576643

Offset: 0

Alois P. Heinz, May 31 2015

nonn

			a(3) = 15: aaaaaa, aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba, aabbcc, aabccb, abbacc, abbcca, abccba.

Alois P. Heinz, Table of n, a(n) for n = 0..447

Row sums of A256117.

Cf. A294603, A321031.

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((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
a:= n-> add(T(n, k), k=0..n):
seq(a(n), n=0..25);

A[n_, k_] := A[n, k] = If[n == 0, 1, k/n*Sum[Binomial[2*n, j]*(n - j)*If[j == 0, 1, (k - 1)^j], {j, 0, n - 1}]];
T[n_, k_] := Sum[(-1)^i*A[n, k - i]/(i!*(k - i)!), {i, 0, k}];
a[n_] := Sum[T[n, k], {k, 0, n}];
a /@ Range[0, 25] (* Jean-François Alcover, Jan 01 2021, after Alois P. Heinz *)

a(n) = Sum_{k=0..n} A256117(n,k).

a(n) ~ Bell(n-1)*Catalan(n) ~ n^n * exp(n/LambertW(n)-1-n) * 4^n / (sqrt(Pi) * sqrt(1+LambertW(n)) * LambertW(n)^(n-1) * n^(5/2)). - Vaclav Kotesovec, Jun 02 2015

A258499 Number of words of length 4n such that all letters of the n-ary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Original entry on oeis.org

1, 1, 34, 3509, 657370, 182587701, 67773956250, 31600247019120, 17769492060922914, 11710509049983422030, 8855064908059488718600, 7558849413204728468703991, 7190781941414575290014093320, 7544364858457252265315311530675, 8654711454787575656983217747533920

Offset: 0

Alois P. Heinz, May 31 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..250

Cf. A256117.

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((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
a:= n-> T(2*n, n):
seq(a(n), n=0..20);

A[n_, k_] := A[n, k] = If[n==0, 1, (k/n) Sum[Binomial[2n, j] (n-j) If[j==0, 1, (k-1)^j], {j, 0, n-1}]];
T[n_, k_] := Sum[(-1)^i A[n, k-i]/(i! (k-i)!), {i, 0, k}];
a[n_] := T[2n, n];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 21 2020, after Alois P. Heinz *)

a(n) = A256117(2n,n).

a(n) ~ c * d^n * n! / n^(5/2), where d = A256254 = 98.82487375173568573170688..., c = -sqrt(2) * LambertW(-2*exp(-2)) / (16 * Pi^(3/2) * sqrt(1 + LambertW(-2*exp(-2)))) = 0.008372249434869139279228556376854454452398... . - Vaclav Kotesovec, Jun 01 2015, updated Sep 27 2023

A258490 Number of words of length 2n such that all letters of the ternary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Original entry on oeis.org

5, 56, 465, 3509, 25571, 184232, 1325609, 9567545, 69387483, 505915981, 3708195075, 27314663271, 202116910415, 1501769001416, 11200258810265, 83815491037841, 629152465444715, 4735907436066401, 35740538971518155, 270356740041089471, 2049510329494271615

Offset: 3

Alois P. Heinz, May 31 2015

nonn

			a(3) = 5: aabbcc, aabccb, abbacc, abbcca, abccba.

Alois P. Heinz, Table of n, a(n) for n = 3..1000

Column k=3 of A256117.

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((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
a:= n-> T(n, 3):
seq(a(n), n=3..25);

A[n_, k_] := A[n, k] = If[n == 0, 1, k/n*Sum[Binomial[2*n, j]*(n - j)*If[j == 0, 1, (k - 1)^j], {j, 0, n - 1}]];
T[n_, k_] := Sum[(-1)^i*A[n, k - i]/(i!*(k - i)!), {i, 0, k}];
a[n_] := T[n, 3];
Table[a[n], {n, 3, 25}] (* Jean-François Alcover, May 18 2018, translated from Maple *)

a(n) ~ 8^n / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 01 2015

Conjecture: 4*n*(n-1)*(46829*n-161203)*a(n) -(n-1)*(4865671*n^2-22433759*n+19821114)*a(n-1) +6*(7756949*n^3-53792553*n^2+117956226*n-84118712)*a(n-2) +(-200071007*n^3+1677158106*n^2-4623144589*n+4201946850)*a(n-3) +2*(2*n-7)*(93171685*n^2-585009841*n+881711802)*a(n-4) -72*(2*n-7)*(2*n-9)*(744719*n-1901876)*a(n-5)=0. - R. J. Mathar, Aug 07 2015

A258491 Number of words of length 2n such that all letters of the quaternary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Original entry on oeis.org

14, 300, 4400, 55692, 657370, 7488228, 83752760, 928406556, 10254052556, 113186465340, 1250820198264, 13852280754980, 153813849202674, 1712835575525140, 19129590267619304, 214261857777632700, 2406509409480345364, 27100348605141932540, 305944173898725745944

Offset: 4

Alois P. Heinz, May 31 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..900

Column k=4 of A256117.

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((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
a:= n-> T(n, 4):
seq(a(n), n=4..25);

A[n_, k_] := A[n, k] = If[n == 0, 1, (k/n) Sum[Binomial[2n, j] (n - j)* If[j == 0, 1, (k - 1)^j], {j, 0, n - 1}]];
T[n_, k_] := Sum[(-1)^i A[n, k - i]/(i! (k - i)!), {i, 0, k}];
a[n_] := T[n, 4];
a /@ Range[4, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

a(n) ~ 12^n / (8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 01 2015

A258492 Number of words of length 2n such that all letters of the quinary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Original entry on oeis.org

42, 1485, 34034, 647920, 11187462, 182587701, 2880017910, 44477796451, 677940669900, 10250875770135, 154278143783022, 2316262521915440, 34742240691197182, 521131993897607925, 7822497290908844702, 117554364707534272375, 1769075045150700563052

Offset: 5

Alois P. Heinz, May 31 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 5..800

Column k=5 of A256117.

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((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
a:= n-> T(n, 5):
seq(a(n), n=5..25);

A[n_, k_] := A[n, k] = If[n == 0, 1, (k/n) Sum[Binomial[2n, j] (n - j)*If[j == 0, 1, (k - 1)^j], {j, 0, n - 1}]];
T[n_, k_] := Sum[(-1)^i A[n, k - i]/(i! (k - i)!), {i, 0, k}];
a[n_] := T[n, 5];
a /@ Range[5, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

a(n) ~ 16^n / (54*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 01 2015

A258493 Number of words of length 2n such that all letters of the senary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Original entry on oeis.org

132, 7007, 231868, 6191808, 146698848, 3229298919, 67773956250, 1377513928505, 27389291758920, 536341475466069, 10391807506431956, 199869644353809760, 3824918464184384952, 72954292150964887751, 1388571904028052188458, 26397789023379585277557

Offset: 6

Alois P. Heinz, May 31 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..750

Column k=6 of A256117.

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((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
a:= n-> T(n, 6):
seq(a(n), n=6..25);

a(n) ~ 20^n / (384*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 01 2015

A258494 Number of words of length 2n such that all letters of the septenary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Original entry on oeis.org

429, 32032, 1447992, 51647700, 1605746373, 45730269662, 1227377689395, 31600247019120, 789604855530855, 19302666179660304, 464277874912868104, 11032638071392824348, 259801742258903758053, 6076538940891732415102, 141407795779400734204647

Offset: 7

Alois P. Heinz, May 31 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..700

Column k=7 of A256117.

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((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
a:= n-> T(n, 7):
seq(a(n), n=7..25);

a(n) ~ 24^n / (3000*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 01 2015

cp's OEIS Frontend

A183135 Square array A(n,k) by antidiagonals. A(n,k) is the number of length 2n k-ary words (n,k>=0) that can be built by repeatedly inserting doublets into the initially empty word.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A256311 Number T(n,k) of length 3n words such that all letters of the k-ary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting triples of identical letters into the initially empty word; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A258498 Number of words of length 2n such that the index set of occurring letters is {1, 2, ..., k}, all letters are introduced in ascending order, and the words can be built by repeatedly inserting doublets into the initially empty word.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A258499 Number of words of length 4n such that all letters of the n-ary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A258490 Number of words of length 2n such that all letters of the ternary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A258491 Number of words of length 2n such that all letters of the quaternary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A258492 Number of words of length 2n such that all letters of the quinary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word.

Views

Author

Keywords