A213275 -id:A213275 - cp's OEIS frontend

A213276 Number A(n,k) of n-length words w over a k-ary alphabet such that for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 9, 5, 1, 0, 1, 5, 16, 18, 9, 1, 0, 1, 6, 25, 46, 36, 14, 1, 0, 1, 7, 36, 95, 118, 74, 27, 1, 0, 1, 8, 49, 171, 315, 276, 165, 46, 1, 0, 1, 9, 64, 280, 711, 895, 712, 367, 91, 1, 0, 1, 10, 81, 428, 1414, 2506, 2535, 1805, 869, 162, 1, 0

Offset: 0

Alois P. Heinz, Jun 08 2012

			A(0,k) = 1: the empty word.
A(n,1) = 1: (a)^n for alphabet {a}.
A(1,k) = k: number of words = size of the alphabet.
A(2,k) = k^2: all words with 2 letters from the alphabet.
A(3,2) = 5: aaa, aab, aba, baa, bbb for alphabet {a,b}.
A(3,3) = 18: aaa, aab, aac, aba, abc, aca, acb, baa, bac, bbb, bbc, bca, bcb, caa, cab, cba, cbb, ccc.
A(4,2) = 9: aaaa, aaab, aaba, aabb, abaa, abab, baaa, baab, bbbb.
A(5,2) = 14: aaaaa, aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, baaaa, baaab, baaba, bbbbb.
Square array A(n,k) begins:
  1, 1,  1,   1,    1,    1,     1,     1, ...
  0, 1,  2,   3,    4,    5,     6,     7, ...
  0, 1,  4,   9,   16,   25,    36,    49, ...
  0, 1,  5,  18,   46,   95,   171,   280, ...
  0, 1,  9,  36,  118,  315,   711,  1414, ...
  0, 1, 14,  74,  276,  895,  2506,  6104, ...
  0, 1, 27, 165,  712, 2535,  8151, 23527, ...
  0, 1, 46, 367, 1805, 7280, 25781, 83916, ...

Alois P. Heinz, Antidiagonals n = 0..24, flattened

Columns k=0-10 give: A000007, A000012, A213290, A213291, A213292, A213293, A213294, A213295, A213296, A213297, A213298.
Rows n=0-10 give: A000012, A001477, A000290, A081435(k-1), A213283, A213284, A213285, A213286, A213287, A213288, A213289.
Main diagonal gives A321704.
Cf. A182172, A213275, A257783.

A:= (n, k)-> h(n, k, 0, []):
h:= proc(n, k, m, l) option remember;
      `if`(n=0 and k=0, b(l), `if`(k=0 or n>0 and n1     then for j from i+1 to nops(l) do
      if l[i]<=l[j] then return false
    elif l[j]>0     then break
      fi od fi; true
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

a[n_, k_] := h[n, k, 0, {}];
h[n_, k_, m_, l_] := h[n, k, m, l] = If[n == 0 && k === 0, b[l], If[k == 0 || n > 0 && n < m, 0, Sum[h[n-j, k-1, Max[m, j], Join[{j}, l]], {j, Max[1, m], n}] + h[n, k-1, m, Join[{0}, l]]]];
b[l_] := b[l] = If[Complement[l, {0}] == {}, 1, Sum[If[g[l, i], b[ReplacePart[l, i -> l[[i]]-1]], 0], {i, 1, Length[l]}]];
g[l_, i_] := Module[{j}, If[l[[i]] < 1, Return[False], If[l[[i]] > 1, For[ j = i+1, j <= Length[l], j++, If[l[[i]] <= l[[j]], Return[False], If[l[[j]] > 0, Break[]]]]]]; True];
Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 11 2013, translated from Maple *)

T(n,k) = Sum_{i=0..k} C(k,i) * A257783(n,k-i).

A213863 Number of words w where each letter of the n-ary alphabet occurs 3 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 1, 7, 106, 2575, 87595, 3864040, 210455470, 13681123135, 1035588754375, 89575852312675, 8724157965777400, 945424197750836500, 112891958206958894500, 14733016566584898017500, 2086947723639167040631750, 318968341048949169038143375

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

Also the number of tree-child networks with a maximal number n of reticulations nodes. - Michael Fuchs, Aug 05 2020

			a(0) = 1: the empty word.
a(1) = 1: aaa.
a(2) = 7: aaabbb, aababb, aabbab, abaabb, ababab, baaabb, baabab.

Alois P. Heinz, Table of n, a(n) for n = 0..320
Cyril Banderier and Michael Wallner, Young tableaux with periodic walls: counting with the density method, Séminaire Lotharingien de Combinatoire XX, Proceedings of the 33rd Conference on Formal Power (2021) Article #YY.
Michael Fuchs, Enumeration and Stochastic Properties of Tree-Child Networks, National Chengchi Univ. (Taipei 2023).
Michael Fuchs, Guan-Ru Yu, and Louxin Zhang, On the Asymptotic Growth of the Number of Tree-Child Networks, arXiv:2003.08049 [math.CO], 2020.

Row n=3 of A213275.

a(n) = Sum_{m>=1} b_{n,m} if n>0. Here, b_{n,m} satisfies b_{n,m}=(2*n+m-2)*Sum_{k=1..m} b_{n-1,k} for n>=2 and 1<=m<=n with initial conditions b_{n,m}=0 for nMichael Fuchs, Aug 05 2020

A213873 Number of words w where each letter of the ternary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 6, 15, 106, 1075, 13326, 188196, 2914395, 48349015, 846167608, 15456538890, 292407484590, 5695907466120, 113735416237808, 2319861446805120, 48199341935153655, 1017747539683821855, 21799192392184931700, 472889100118180757550, 10375788309377599231200

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

			a(0) = 1: the empty word.
a(1) = 6: abc, acb, bac, bca, cab, cba, (all permutations of 3 letters).
a(2) = 15: aabbcc, aabcbc, aacbbc, ababcc, abacbc, abcabc, acabbc, acbabc, baabcc, baacbc, bacabc, bcaabc, caabbc, cababc, cbaabc.

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

Column k=3 of A213275.

a:= proc(n) option remember; `if`(n<2, [1, 6][n+1], (6*n-9) *(3*n-4)
      *(3*n-5) *(797*n^4-72*n^3-397*n^2+108*n-4) *a(n-1) / ((n+1)
      *(n+2) *(2*n+1) *(797*n^4-3260*n^3+4601*n^2-2502*n+360)))
    end:
seq(a(n), n=0..20);

Flatten[{1, 6, Table[3*(-4 + 108*n - 397*n^2 - 72*n^3 + 797*n^4) * (3*n-4)! / (2*(2*n-1)*(2*n+1) * (n-2)! * (n+1)! * (n+2)!), {n, 2, 20}]}] (* Vaclav Kotesovec, Sep 02 2014 *)

a(n) ~ 797*sqrt(3)*27^(n-1)/(16*Pi*n^4). - Vaclav Kotesovec, Aug 13 2013

For n > 1, a(n) = 3*(-4 + 108*n - 397*n^2 - 72*n^3 + 797*n^4) * (3*n-4)! / (2*(2*n-1)*(2*n+1) * (n-2)! * (n+1)! * (n+2)!). - Vaclav Kotesovec, Sep 02 2014

A213874 Number of words w where each letter of the 4-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 24, 105, 2575, 115955, 7364321, 586368681, 54862627919, 5795673908453, 673174876488400, 84386541996407430, 11262879538848476760, 1584243362361105791448, 233004893382083549345048, 35610340402841609968092950, 5627093485549459958456588775

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

			a(0) = 1: the empty word.
a(1) = 24: abcd, abdc, ..., dcab, dcba, (all permutations of 4 letters).
a(2) = 105: aabbccdd, aabbcdcd, aabbdccd, ..., dcaabbcd, dcababcd, dcbaabcd.

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

Column k=4 of A213275.

Flatten[{1,24,Table[8*(9297776*n^10 + 17051200*n^9 - 11545329*n^8 - 20688255*n^7 + 7760028*n^6 + 7548270*n^5 - 2879537*n^4 - 619195*n^3 + 326046*n^2 - 30420*n + 216) * (4*n-5)! / (3 * (2*n-1) * (2*n+1) * (2*n+3) * (9*n^2-9*n+2) * (9*n^2+9*n+2) * (n-2)! * (n+1)! * (n+2)! * (n+3)!),{n,2,20}]}] (* Vaclav Kotesovec, Sep 02 2014 *)

For n > 1, a(n) = 8*(9297776*n^10 + 17051200*n^9 - 11545329*n^8 - 20688255*n^7 + 7760028*n^6 + 7548270*n^5 - 2879537*n^4 - 619195*n^3 + 326046*n^2 - 30420*n + 216) * (4*n-5)! / (3 * (2*n-1) * (2*n+1) * (2*n+3) * (9*n^2-9*n+2) * (9*n^2+9*n+2) * (n-2)! * (n+1)! * (n+2)! * (n+3)!). - Vaclav Kotesovec, Sep 02 2014

A213875 Number of words w where each letter of the 5-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 120, 945, 87595, 19558470, 7236515981, 3745777177366, 2468722942369153, 1953740543358042205, 1785201362960729511070, 1831976833971352074708780, 2068976591723429552651743620, 2532392303303120865350779766160, 3319547855302819899374947284511390

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

			a(0) = 1: the empty word.
a(1) = 120: abcde, abced, abdce, ..., edbca, edcab, edcba, (all permutations of 5 letters).
a(2) = 945: aabbccddee, aabbccdede, aabbccedde, ..., edcaabbcde, edcababcde, edcbaabcde.

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

Column k=5 of A213275.

A213862 Number of words w where each letter of the n-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 1, 3, 106, 115955, 7236515981, 40684710729862072, 29745278219128813035415595, 3847028733161627562733350467148495403, 114752550881830601773639529476205016572641397025904, 996942995951678818059423286104073541295789338859855813183302036541

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

			a(0) = 1: the empty word.
a(1) = 1: a.
a(2) = 3: aabb, abab, baab.
a(3) = 106: aaabbbccc, aaabbcbcc, aaabbccbc, ..., cbaababcc, cbaabacbc, cbaabcabc.

Main diagonal of A213275.

A213864 Number of words w where each letter of the n-ary alphabet occurs 4 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 1, 19, 1075, 115955, 19558470, 4622269345, 1428739165560, 551211090935595, 256653852463806955, 140633739174235040170, 88931024447225475920050, 63897452586372538310261555, 51509615229665486538200354125, 46102293227619069563429377126200

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

			a(0) = 1: the empty word.
a(1) = 1: aaaa.
a(2) = 19: aaaabbbb, aaababbb, aaabbabb, aaabbbab, aabaabbb, aabababb, aababbab, aabbaabb, aabbabab, abaaabbb, abaababb, abaabbab, ababaabb, abababab, baaaabbb, baaababb, baaabbab, baabaabb, baababab.

Row n=4 of A213275.

A213865 Number of words w where each letter of the n-ary alphabet occurs 5 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 1, 56, 13326, 7364321, 7236515981, 10915151070941, 23060727168393236, 64157120593526429971, 224909472938181653263446, 961415357313559098150122721, 4886376056824611061263607492146, 28944590736206982153001156958037271, 196631118571992127875305845382720388771

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

			a(0) = 1: the empty word.
a(1) = 1: aaaaa.
a(2) = 56: aaaaabbbbb, aaaababbbb, ..., baababaabb, baabababab.

Row n=5 of A213275.

A213866 Number of words w where each letter of the n-ary alphabet occurs 6 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 1, 174, 188196, 586368681, 3745777177366, 40684710729862072, 668821362774214965294, 15388200323143520006870562, 468682891926540940991787213006, 18131599140232990157442722880124741, 863168115684925396146477660939182979547

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

			a(0) = 1: the empty word.
a(1) = 1: aaaaaa.
a(2) = 174: aaaaaabbbbbb, aaaaababbbbb, ..., baabababaabb, baababababab.

Row n=6 of A213275.

A213867 Number of words w where each letter of the n-ary alphabet occurs 7 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Original entry on oeis.org

1, 1, 561, 2914395, 54862627919, 2468722942369153, 211109968702038259993, 29745278219128813035415595, 6273648300104128965616586081511, 1850042480471503379038420801262526759, 725168149513389307543056971716033431701831

Offset: 0

Alois P. Heinz, Jun 23 2012

nonn

			a(0) = 1: the empty word.
a(1) = 1: aaaaaaa.
a(2) = 561: aaaaaaabbbbbbb, aaaaaababbbbbb, ..., baababababaabb, baabababababab.

Row n=7 of A213275.

cp's OEIS Frontend

A213276 Number A(n,k) of n-length words w over a k-ary alphabet such that for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A213863 Number of words w where each letter of the n-ary alphabet occurs 3 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A213873 Number of words w where each letter of the ternary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A213874 Number of words w where each letter of the 4-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A213875 Number of words w where each letter of the 5-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Links

Crossrefs

A213862 Number of words w where each letter of the n-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Crossrefs

A213864 Number of words w where each letter of the n-ary alphabet occurs 4 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Crossrefs

A213865 Number of words w where each letter of the n-ary alphabet occurs 5 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Crossrefs

A213866 Number of words w where each letter of the n-ary alphabet occurs 6 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Crossrefs

A213867 Number of words w where each letter of the n-ary alphabet occurs 7 times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

Views

Author

Keywords

Examples

Crossrefs