A047926 a(n) = (3^(n+1) + 2*n + 1)/4.

1, 3, 8, 22, 63, 185, 550, 1644, 4925, 14767, 44292, 132866, 398587, 1195749, 3587234, 10761688, 32285049, 96855131, 290565376, 871696110, 2615088311, 7845264913, 23535794718, 70607384132, 211822152373, 635466457095, 1906399371260

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Density of regular language L{0}* over {0,1,2,3} (i.e., number of strings of length n in L), where L is described by regular expression with c=3: Sum_{i=1..c} Product_{j=1..i} (j(1+...+j)*), where "Sum" stands for union and "Product" for concatenation. I.e., L = L((11*+11*2(1+2)*+11*2(1+2)*3(1+2+3)*)0*) - Nelma Moreira, Oct 10 2004

Conjecture: Number of representations of 3^(2n) as a sum a^2 + b^2 + c^2 with 0 < a <= b <= c. That is, a(1) = 3 because 3^2 = 1^2 + 2^2 + 2^2, a(2) = 3 because 3^4 = 1^2 + 4^2 + 8^2 = 3^2 + 6^2 + 6^2 = 4^2 + 4^2 + 7^2. - Zak Seidov, Mar 01 2012

References

• M. Aigner, Combinatorial Search, Wiley, 1988, see Exercise 6.4.5.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Nelma Moreira and Rogerio Reis, On the density of languages representing finite set partitions, Technical Report DCC-2004-07, August 2004, DCC-FC& LIACC, Universidade do Porto.
• N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
• Index entries for linear recurrences with constant coefficients, signature (5,-7,3).

Crossrefs

Cf. A007051.

Programs

Magma

[(3^(n+1)+2*n+1)/4: n in [0..40]]; // Vincenzo Librandi, May 02 2011

Mathematica

Table[(3^(n+1)+2n+1)/4,{n,0,30}] (* or *) LinearRecurrence[{5,-7,3},{1,3,8},30] (* Harvey P. Dale, Apr 19 2019 *)

PARI

a(n)=(3^(n+1)+2*n+1)/4 \\ Charles R Greathouse IV, Mar 02 2012

Sage

[(gaussian_binomial(n,1,3)+n)/2 for n in range(1,28)] # Zerinvary Lajos, May 29 2009

Formula

From Paul Barry, Sep 03 2003: (Start)

a(n) = Sum_{k=0..n} (3^k + 1)/2. Partial sums of A007051.

G.f.: (1 - 2*x)/((1 - x)^2*(1 - 3*x)). (End)

For c = 3, a(c,n) = g(1,c)*n + Sum_{k=2..c} g(k,c)*k*(k^n - 1)/(k-1), where g(1,1) = 1, g(1,c) = g(1,c-1) + (-1)^(c-1)/(c-1)! for c > 1, and g(k,c) = g(k-1, c-1)/k, for c > 1 and 2 <= k <= c. - Nelma Moreira, Oct 10 2004

a(n+1) = 3*a(n) - n. - Franklin T. Adams-Watters, Jul 05 2014

E.g.f.: exp(x)*(1 + 2*x + 3*exp(2*x))/4. - Stefano Spezia, Sep 26 2023