A352971 Moments of the distribution of position of the first occurrence of pattern aa in a random ternary word.

1, 12, 258, 8274, 353742, 18904602, 1212354798, 90706565514, 7756033173342, 746093257148442, 79745110236049038, 9375786203927344554, 1202540991574287431742, 167091435183140588426682, 25003060551369349424359278, 4008624526767825553573112394

Offset: 0

Author

Geoffrey Critzer, Apr 12 2022

Keywords

• nonn

Comments

Let X be the random variable that assigns to each word on alphabet {a,b,c} the number of letters required for the first occurrence of the pattern aa. Then a(n) = E(X^n).

Let X(m,k) be the random variable that assigns to each m-ary word the number of letters required for the first occurrence of the pattern aa...a (k copies of a). The moment generating function for X(m,k) is G(exp(t)) where G(t) = T(t/m), T(z) = z^k/(z^k + c(z)(1- m*z)), c(z) = (1-z^k)/(1-z).

Links

• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 59.

Crossrefs

Cf. A302922.

Programs

Maple

g := exp(2*x)/(9-6*exp(x)-2*exp(2*x)) ;
taylor(g,x=0,40) ;
L := gfun[seriestolist](%) ;
seq( op(i,L)*(i-1)!,i=1..nops(L)) ; # R. J. Mathar, Mar 02 2023

Mathematica

nn = 15; c[z_] := (1 - z^k)/(1 - z);
T[z_] := z^k/(z^k + (1 - m z) c[z]); G[t_] := T[t/m];
Range[0, nn]! CoefficientList[Series[G[Exp[t]] /. {k -> 2, m -> 3}, {t, 0, nn}],t]

PARI

seq(n)=my(p=exp(x + O(x*x^n))); Vec(serlaplace(p^2/(9 - 6*p - 2*p^2))) \\ Andrew Howroyd, May 06 2023

SageMath

# uses[egfExpand from A362718]
def egf(x): return exp(2*x)/(9 - 6*exp(x) - 2*exp(2*x))
print(egfExpand(egf, 1, 15))  # Peter Luschny, May 06 2023

Formula

E.g.f.: exp(2*t)/(9 - 6*exp(t) - 2*exp(2*t)).

a(n) ~ n! * (3 - sqrt(3)) / (12 * (log(3*(sqrt(3) - 1)/2))^(n+1)). - Vaclav Kotesovec, Apr 13 2022

Extensions

Typo in a(7) corrected by Georg Fischer, May 06 2023