A292804 -id:A292804

A102866

Number of finite languages over a binary alphabet (set of nonempty binary words of total length n).

+10
19

1, 2, 5, 16, 42, 116, 310, 816, 2121, 5466, 13937, 35248, 88494, 220644, 546778, 1347344, 3302780, 8057344, 19568892, 47329264, 114025786, 273709732, 654765342, 1561257968, 3711373005, 8797021714, 20794198581, 49024480880, 115292809910, 270495295636

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

OFFSET

0,2

COMMENTS

Analogous to A034899 (which also enumerates multisets of words)

LINKS

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

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 64

Stefan Gerhold, Counting finite languages by total word length, INTEGERS 11 (2011), #A44.

Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.

FORMULA

G.f.: exp(Sum((-1)^(j-1)/j*(2*z^j)/(1-2*z^j), j=1..infinity)).

Asymptotics (Gerhold, 2011): a(n) ~ c * 2^(n-1)*exp(2*sqrt(n)-1/2) / (sqrt(Pi) * n^(3/4)), where c = exp( Sum_{k>=2} (-1)^(k-1)/(k*(2^(k-1)-1)) ) = 0.6602994483152065685... . - Vaclav Kotesovec, Sep 13 2014

Weigh transform of A000079. - Alois P. Heinz, Jun 25 2018

EXAMPLE

a(2) = 5 because the sets are {a,b}, {aa}, {ab}, {ba}, {bb}.

a(3) = 16 because the sets are {a,aa}, {a,ab}, {a,ba}, {a,bb}, {b,aa}, {b,ab}, {b,ba}, {b,bb}, {aaa}, {aab}, {aba}, {abb}, {baa}, {bab}, {bba}, {bbb}.

MAPLE

series(exp(add((-1)^(j-1)/j*(2*z^j)/(1-2*z^j), j=1..40)), z, 40);

MATHEMATICA

nn = 20; p = Product[(1 + x^i)^(2^i), {i, 1, nn}]; CoefficientList[Series[p, {x, 0, nn}], x] (* Geoffrey Critzer, Mar 07 2012 *)

CoefficientList[Series[E^Sum[(-1)^(k-1)/k*(2*x^k)/(1-2*x^k), {k, 1, 30}], {x, 0, 30}], x] (* Vaclav Kotesovec, Sep 13 2014 *)

CROSSREFS

Cf. A000079, A034899, A256142.

Column k=2 of A292804.

Row sums of A208741 and of A360634.

KEYWORD

nonn

AUTHOR

Philippe Flajolet, Mar 01 2005

STATUS

approved

A319501

Number T(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet such that all k letters occur at least once in the set; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

+10
16

1, 0, 1, 0, 1, 3, 0, 2, 12, 13, 0, 2, 38, 105, 73, 0, 3, 110, 588, 976, 501, 0, 4, 302, 2811, 8416, 9945, 4051, 0, 5, 806, 12354, 59488, 121710, 111396, 37633, 0, 6, 2109, 51543, 375698, 1185360, 1830822, 1366057, 394353, 0, 8, 5450, 207846, 2209276, 10096795, 23420022, 28969248, 18235680, 4596553

(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) * A292804(n,k-i).

EXAMPLE

T(2,2) = 3: {ab}, {ba}, {a,b}.

T(3,2) = 12: {aab}, {aba}, {abb}, {baa}, {bab}, {bba}, {a,ab}, {a,ba}, {a,bb}, {aa,b}, {ab,b}, {b,ba}.

T(4,2) = 38: {aaab}, {aaba}, {aabb}, {abaa}, {abab}, {abba}, {abbb}, {baaa}, {baab}, {baba}, {babb}, {bbaa}, {bbab}, {bbba}, {a,aab}, {a,aba}, {a,abb}, {a,baa}, {a,bab}, {a,bba}, {a,bbb}, {aa,ab}, {aa,ba}, {aa,bb}, {aaa,b}, {aab,b}, {ab,ba}, {ab,bb}, {aba,b}, {abb,b}, {b,baa}, {b,bab}, {b,bba}, {ba,bb}, {a,aa,b}, {a,ab,b}, {a,b,ba}, {a,b,bb}.

Triangle T(n,k) begins:

1;

0, 1;

0, 1, 3;

0, 2, 12, 13;

0, 2, 38, 105, 73;

0, 3, 110, 588, 976, 501;

0, 4, 302, 2811, 8416, 9945, 4051;

0, 5, 806, 12354, 59488, 121710, 111396, 37633;

0, 6, 2109, 51543, 375698, 1185360, 1830822, 1366057, 394353;

MAPLE

h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,

add(h(n-i*j, i-1, k)*binomial(k^i, j), j=0..n/i)))

end:

T:= (n, k)-> add((-1)^i*binomial(k, i)*h(n$2, k-i), i=0..k):

seq(seq(T(n, k), k=0..n), n=0..12);

MATHEMATICA

h[n_, i_, k_] := h[n, i, k] = If[n==0, 1, If[i<1, 0, Sum[h[n-i*j, i-1, k]* Binomial[k^i, j], {j, 0, n/i}]]];

T[n_, k_] := Sum[(-1)^i Binomial[k, i] h[n, n, k-i], {i, 0, k}];

Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 05 2020, after Alois P. Heinz *)

CROSSREFS

Columns k=0-10 give: A000007, A000009 (for n>0), A320203, A320204, A320205, A320206, A320207, A320208, A320209, A320210, A320211.

Main diagonal gives A000262.

Row sums give A319518.

T(2n,n) gives A319519.

Cf. A257740, A292804.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Sep 20 2018

STATUS

approved

A144074

Number A(n,k) of multisets of nonempty words with a total of n letters over k-ary alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals.

+10
15

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 7, 3, 0, 1, 4, 15, 20, 5, 0, 1, 5, 26, 64, 59, 7, 0, 1, 6, 40, 148, 276, 162, 11, 0, 1, 7, 57, 285, 843, 1137, 449, 15, 0, 1, 8, 77, 488, 2020, 4632, 4648, 1200, 22, 0, 1, 9, 100, 770, 4140, 13876, 25124, 18585, 3194, 30, 0, 1, 10, 126

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

OFFSET

0,8

COMMENTS

Column k > 1 is asymptotic to k^n * exp(2*sqrt(n) - 1/2 + c(k)) / (2 * sqrt(Pi) * n^(3/4)), where c(k) = Sum_{m>=2} 1/(m*(k^(m-1)-1)). - Vaclav Kotesovec, Mar 14 2015

LINKS

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

Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.

N. J. A. Sloane, Transforms

FORMULA

G.f. of column k: Product_{j>=1} 1/(1-x^j)^(k^j).

Column k is Euler transform of the powers of k.

T(n,k) = Sum_{i=0..k} C(k,i) * A257740(n,k-i). - Alois P. Heinz, May 08 2015

EXAMPLE

A(4,1) = 5: {aaaa}, {aaa,a}, {aa,aa}, {aa,a,a}, {a,a,a,a}.

A(2,2) = 7: {aa}, {a,a}, {bb}, {b,b}, {ab}, {ba}, {a,b}.

A(2,3) = 15: {aa}, {a,a}, {bb}, {b,b}, {cc}, {c,c}, {ab}, {ba}, {a,b}, {ac}, {ca}, {a,c}, {bc}, {cb}, {b,c}.

A(3,2) = 20: {aaa}, {a,aa}, {a,a,a}, {bbb}, {b,bb}, {b,b,b}, {aab}, {aba}, {baa}, {a,ab}, {a,ba}, {aa,b}, {a,a,b}, {bba}, {bab}, {abb}, {b,ba}, {b,ab}, {bb,a}, {b,b,a}.

Square array begins:

1, 1, 1, 1, 1, 1, ...

0, 1, 2, 3, 4, 5, ...

0, 2, 7, 15, 26, 40, ...

0, 3, 20, 64, 148, 285, ...

0, 5, 59, 276, 843, 2020, ...

0, 7, 162, 1137, 4632, 13876, ...

MAPLE

with(numtheory): etr:= proc(p) local b; b:= proc(n) option remember; `if`(n=0, 1, add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n) end end: A:= (n, k)-> etr(j->k^j)(n); seq(seq(A(n, d-n), n=0..d), d=0..14);

MATHEMATICA

a[n_, k_] := SeriesCoefficient[ Product[1/(1-x^j)^(k^j), {j, 1, n}], {x, 0, n}]; a[0, _] = 1; a[_?Positive, 0] = 0;

Table[a[n-k, k], {n, 0, 14}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Jan 15 2014 *)

etr[p_] := Module[{b}, b[n_] := b[n] = If[n==0, 1, Sum[Sum[d p[d], {d, Divisors[j]}] b[n-j], {j, 1, n}]/n]; b];

A[n_, k_] := etr[k^#&][n];

Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 30 2020, after Alois P. Heinz *)

CROSSREFS

Columns k=0-10 give: A000007, A000041, A034899, A144067, A144068, A144069, A144070, A144071, A144072, A144073, A292837.

Rows n=0-2 give: A000012, A001477, A005449.

Main diagonal gives A252654.

Cf. A004248, A257740, A256142, A292804.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Sep 09 2008

EXTENSIONS

Name changed by Alois P. Heinz, Sep 21 2018

STATUS

approved

A292795

Number A(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet such that within each word every letter of the alphabet is at least as frequent as the subsequent alphabet letter; square array A(n,k), n>=0, k>=0, read by antidiagonals.

+10
14

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 3, 2, 0, 1, 1, 3, 7, 2, 0, 1, 1, 3, 13, 18, 3, 0, 1, 1, 3, 13, 36, 42, 4, 0, 1, 1, 3, 13, 60, 122, 110, 5, 0, 1, 1, 3, 13, 60, 206, 433, 250, 6, 0, 1, 1, 3, 13, 60, 326, 865, 1356, 627, 8, 0, 1, 1, 3, 13, 60, 326, 1345, 3408, 4449, 1439, 10, 0

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

OFFSET

0,13

LINKS

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

FORMULA

G.f. of column k: Product_{j>=1} (1+x^j)^A226873(j,k).

A(n,k) = Sum_{j=0..n} A319498(n,j).

EXAMPLE

A(2,3) = 3: {aa}, {ab}, {ba}.

A(3,2) = 7: {aaa}, {aab}, {aba}, {baa}, {aa,a}, {ab,a}, {ba,a}.

A(3,3) = 13: {aaa}, {aab}, {aba}, {baa}, {abc}, {acb}, {bac}, {bca}, {cab}, {cba}, {aa,a}, {ab,a}, {ba,a}.

Square array A(n,k) begins:

1, 1, 1, 1, 1, 1, 1, 1, 1, ...

0, 1, 1, 1, 1, 1, 1, 1, 1, ...

0, 1, 3, 3, 3, 3, 3, 3, 3, ...

0, 2, 7, 13, 13, 13, 13, 13, 13, ...

0, 2, 18, 36, 60, 60, 60, 60, 60, ...

0, 3, 42, 122, 206, 326, 326, 326, 326, ...

0, 4, 110, 433, 865, 1345, 2065, 2065, 2065, ...

0, 5, 250, 1356, 3408, 6228, 9468, 14508, 14508, ...

0, 6, 627, 4449, 15025, 29845, 51325, 76525, 116845, ...

MAPLE

b:= proc(n, i, t) option remember; `if`(t=1, 1/n!,

add(b(n-j, j, t-1)/j!, j=i..n/t))

end:

g:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), n!*b(n, 0, k)):

h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,

add(h(n-i*j, i-1, k)*binomial(g(i, k), j), j=0..n/i)))

end:

A:= (n, k)-> h(n$2, min(n, k)):

seq(seq(A(n, d-n), n=0..d), d=0..14);

MATHEMATICA

b[n_, i_, t_] := b[n, i, t] = If[t == 1, 1/n!, Sum[b[n - j, j, t - 1]/j!, {j, i, n/t}]];

g[n_, k_] := If[k == 0, If[n == 0, 1, 0], n!*b[n, 0, k]];

h[n_, i_, k_] := h[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[h[n - i*j, i - 1, k]*Binomial[g[i, k], j], {j, 0, n/i}]]];

A[n_, k_] := h[n, n, Min[n, k]];

Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 14}] // Flatten(* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)

CROSSREFS

Columns k=0-10 give: A000007, A000009, A340409, A340410, A340411, A340412, A340413, A340414, A340415, A340416, A340417.

Rows n=0-1 give: A000012, A057427.

Main diagonal gives A292796.

Cf. A226873, A292712, A292804, A319498.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Sep 23 2017

STATUS

approved

A256142

G.f.: Product_{j>=1} (1+x^j)^(3^j).

+10
12

1, 3, 12, 55, 225, 927, 3729, 14787, 57888, 224220, 860022, 3270744, 12343899, 46264257, 172305837, 638039136, 2350109736, 8613851832, 31428857611, 114187160631, 413222547846, 1489829356657, 5352683946903, 19167988920930, 68427472477338, 243559693397025

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

OFFSET

0,2

COMMENTS

In general, if g.f. = Product_{j>=1} (1+x^j)^(k^j), then a(n) ~ k^n * exp(2*sqrt(n) - 1/2 - c(k)) / (2 * sqrt(Pi) * n^(3/4)), where c(k) = Sum_{m>=2} (-1)^m/(m*(k^(m-1)-1)).

LINKS

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

Vaclav Kotesovec, Asymptotics of sequence A034691

Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.

FORMULA

a(n) ~ 3^n * exp(2*sqrt(n) - 1/2 - c) / (2 * sqrt(Pi) * n^(3/4)), where c = Sum_{m>=2} (-1)^m/(m*(3^(m-1)-1)) = 0.215985336303958581708278160877115129... .

MATHEMATICA

nmax=30; CoefficientList[Series[Product[(1+x^k)^(3^k), {k, 1, nmax}], {x, 0, nmax}], x]

CROSSREFS

Cf. A102866, A144067, A144074.

Column k=3 of A292804.

KEYWORD

nonn

AUTHOR

Vaclav Kotesovec, Mar 16 2015

STATUS

approved

A292805

Number of sets of nonempty words with a total of n letters over n-ary alphabet.

+10
8

1, 1, 5, 55, 729, 12376, 250735, 5904746, 158210353, 4747112731, 157545928646, 5726207734545, 226093266070501, 9632339536696943, 440262935648935344, 21482974431740480311, 1114363790702406540897, 61219233429920494716931, 3550130647865299090804375

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

OFFSET

0,3

LINKS

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

FORMULA

a(n) = [x^n] Product_{j=1..n} (1+x^j)^(n^j).

a(n) ~ n^(n - 3/4) * exp(2*sqrt(n) - 1/2) / (2*sqrt(Pi)). - Vaclav Kotesovec, Aug 26 2019

EXAMPLE

a(0) = 1: {}.

a(1) = 1: {a}.

a(2) = 5: {aa}, {ab}, {ba}, {bb}, {a,b}.

MAPLE

h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,

add(h(n-i*j, i-1, k)*binomial(k^i, j), j=0..n/i)))

end:

a:= n-> h(n$3):

seq(a(n), n=0..20);

MATHEMATICA

h[n_, i_, k_] := h[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[h[n - i*j, i - 1, k]*Binomial[k^i, j], {j, 0, n/i}]]];

a[n_] := h[n, n, n];

Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jun 04 2018, from Maple *)

CROSSREFS

Main diagonal of A292804.

Cf. A252654, A292845.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Sep 23 2017

STATUS

approved

A292838

Number of sets of nonempty words with a total of n letters over quaternary alphabet.

+10
3

1, 4, 22, 132, 729, 4000, 21488, 113760, 594548, 3073392, 15732936, 79846448, 402104884, 2010879968, 9992425872, 49366096352, 242584319710, 1186177166680, 5773569726884, 27982357252632, 135079969593838, 649640609539360, 3113354757088720, 14871179093155424

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

OFFSET

0,2

LINKS

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

FORMULA

G.f.: Product_{j>=1} (1+x^j)^(4^j).

a(n) ~ 4^n * exp(2*sqrt(n) - 1/2 - c) / (2 * sqrt(Pi) * n^(3/4)), where c = Sum_{m>=2} (-1)^m/(m*(4^(m-1)-1)) = 0.147762663788961720137665013823002812172... - Vaclav Kotesovec, Sep 28 2017

MAPLE

h:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

add(h(n-i*j, i-1)*binomial(4^i, j), j=0..n/i)))

end:

a:= n-> h(n$2):

seq(a(n), n=0..30);

MATHEMATICA

h[n_, i_] := h[n, i] = If[n == 0, 1, If[i < 1, 0,

Sum[h[n - i j, i - 1] Binomial[4^i, j], {j, 0, n/i}]]];

a[n_] := h[n, n];

a /@ Range[0, 30] (* Jean-François Alcover, Dec 30 2020, after Alois P. Heinz *)

CROSSREFS

Column k=4 of A292804.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Sep 24 2017

STATUS

approved

A292839

Number of sets of nonempty words with a total of n letters over 5-ary alphabet.

+10
3

1, 5, 35, 260, 1805, 12376, 83175, 550775, 3600400, 23276175, 149012380, 945726575, 5955676150, 37243117575, 231412658225, 1429522303905, 8783382129825, 53700395135475, 326809026132350, 1980383108328950, 11952682268739660, 71870696616619250, 430632502970026125

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

OFFSET

0,2

LINKS

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

FORMULA

G.f.: Product_{j>=1} (1+x^j)^(5^j).

a(n) ~ 5^n * exp(2*sqrt(n) - 1/2 - c) / (2 * sqrt(Pi) * n^(3/4)), where c = Sum_{m>=2} (-1)^m/(m*(5^(m-1)-1)) = 0.112852293193143374268678097722831649456... - Vaclav Kotesovec, Sep 28 2017

MAPLE

h:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

add(h(n-i*j, i-1)*binomial(5^i, j), j=0..n/i)))

end:

a:= n-> h(n$2):

seq(a(n), n=0..30);

MATHEMATICA

h[n_, i_] := h[n, i] = If[n == 0, 1, If[i < 1, 0,

Sum[h[n - i j, i - 1] Binomial[5^i, j], {j, 0, n/i}]]];

a[n_] := h[n, n];

a /@ Range[0, 30] (* Jean-François Alcover, Dec 30 2020, after Alois P. Heinz *)

CROSSREFS

Column k=5 of A292804.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Sep 24 2017

STATUS

approved

A292840

Number of sets of nonempty words with a total of n letters over 6-ary alphabet.

+10
3

1, 6, 51, 452, 3777, 31074, 250735, 1993176, 15640983, 121378650, 932738805, 7105552308, 53709133137, 403124780178, 3006420386499, 22290321581448, 164378277308862, 1206180958964508, 8810022165617086, 64073173243207632, 464122836576398454, 3349321050668452460

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

OFFSET

0,2

LINKS

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

FORMULA

G.f.: Product_{j>=1} (1+x^j)^(6^j).

a(n) ~ 6^n * exp(2*sqrt(n) - 1/2 - c) / (2 * sqrt(Pi) * n^(3/4)), where c = Sum_{m>=2} (-1)^m/(m*(6^(m-1)-1)) = 0.091503304254691843343610606469481430508... - Vaclav Kotesovec, Sep 28 2017

MAPLE

h:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

add(h(n-i*j, i-1)*binomial(6^i, j), j=0..n/i)))

end:

a:= n-> h(n$2):

seq(a(n), n=0..30);

CROSSREFS

Column k=6 of A292804.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Sep 24 2017

STATUS

approved

A292841

Number of sets of nonempty words with a total of n letters over 7-ary alphabet.

+10
3

1, 7, 70, 721, 7042, 67592, 636517, 5904746, 54072137, 489655873, 4390760297, 39030158111, 344244293260, 3014869505704, 26235190722937, 226961433002801, 1952889252127030, 16720135949099562, 142493658202081151, 1209158776638832488, 10219419639669800154

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

OFFSET

0,2

LINKS

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

FORMULA

G.f.: Product_{j>=1} (1+x^j)^(7^j).

a(n) ~ 7^n * exp(2*sqrt(n) - 1/2 - c) / (2 * sqrt(Pi) * n^(3/4)), where c = Sum_{m>=2} (-1)^m/(m*(7^(m-1)-1)) = 0.07704538722753681799661640414751144459... - Vaclav Kotesovec, Sep 28 2017

MAPLE

h:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

add(h(n-i*j, i-1)*binomial(7^i, j), j=0..n/i)))

end:

a:= n-> h(n$2):

seq(a(n), n=0..30);

CROSSREFS

Column k=7 of A292804.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Sep 24 2017

STATUS

approved