login
Total number of different letters summed over all ternary words of length n.
4

%I #61 Feb 17 2024 15:03:32

%S 0,3,15,57,195,633,1995,6177,18915,57513,174075,525297,1582035,

%T 4758393,14299755,42948417,128943555,387027273,1161475035,3485211537,

%U 10457207475,31374768153,94130595915,282404370657,847238277795,2541765165033,7625396158395,22876389801777,68629572058515

%N Total number of different letters summed over all ternary words of length n.

%C These are the numbers d(n,3) studied by J. L. Martin. - _N. J. A. Sloane_, Sep 13 2014

%C For n >= 0, the number of ternary sequences of length n+1, that contain at least one pair of same consecutive digits. - _Armend Shabani_, Apr 10 2019

%H Philippe Flajolet and Robert Sedgewick, <a href="https://ac.cs.princeton.edu/30mgf/">Combinatorial Parameters and MGFs</a>, lecture slides Analytic Combinatorics, 2012.

%H J. L. Martin, <a href="http://www.math.umn.edu/math/slopes.pdf">The slopes determined by n points in the plane</a> [Dead link]

%H Jeremy L. Martin, <a href="https://arxiv.org/abs/math/0302106">The slopes determined by n points in the plane</a>, arXiv:math/0302106 [math.AG], 2003-2006; Duke Math. J. 131 (2006), no. 1, 119-165. See table of d(n,k), but beware errors.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5,-6).

%F E.g.f.: 3*exp(3x) - 3*exp(2x).

%F See Mathematica code for a more transparent version of the e.g.f.

%F Generally for an m-ary word of length n: m*exp(m*x) - m*exp((m-1)*x)

%F From _Alois P. Heinz_, Jan 20 2013: (Start)

%F a(n) = 3*(3^n-2^n) = 3*A001047(n).

%F G.f.: 3*x/((3*x-1)*(2*x-1)).

%F (End)

%F a(n) = A217764(n,5). - _Ross La Haye_, Mar 27 2013

%e a(2) = 15 because the length 2 words on alphabet {0,1,2} are: 00, 01, 02, 10, 11, 12, 20, 21, 22 and we sum respectively 1 + 2 + 2 + 2 + 1 + 2 + 2 + 2 + 1 = 15.

%p a:= n-> 3*(3^n-2^n):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jan 20 2013

%t nn=28; Range[0,nn]!CoefficientList[Series[D[(1+y(Exp[x]-1))^3,y]/.y->1, {x,0,nn}], x]

%t (* Second program: *)

%t LinearRecurrence[{5, -6}, {0, 3}, 30] (* _Jean-François Alcover_, Jan 09 2019 *)

%Y Cf. A000918, A001047, A217764.

%Y A diagonal of the triangle in A079268.

%K nonn,easy

%O 0,2

%A _Geoffrey Critzer_, Jan 20 2013