%I #68 Sep 26 2023 15:32:53
%S 1,3,8,22,63,185,550,1644,4925,14767,44292,132866,398587,1195749,
%T 3587234,10761688,32285049,96855131,290565376,871696110,2615088311,
%U 7845264913,23535794718,70607384132,211822152373,635466457095,1906399371260
%N a(n) = (3^(n+1) + 2*n + 1)/4.
%C 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
%C 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
%D M. Aigner, Combinatorial Search, Wiley, 1988, see Exercise 6.4.5.
%H Vincenzo Librandi, <a href="/A047926/b047926.txt">Table of n, a(n) for n = 0..200</a>
%H Nelma Moreira and Rogerio Reis, <a href="http://www.dcc.fc.up.pt/Pubs/TR04/dcc-2004-07.pdf">On the density of languages representing finite set partitions</a>, Technical Report DCC-2004-07, August 2004, DCC-FC& LIACC, Universidade do Porto.
%H N. Moreira and R. Reis, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Moreira/moreira8.html">On the Density of Languages Representing Finite Set Partitions</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-7,3).
%F From _Paul Barry_, Sep 03 2003: (Start)
%F a(n) = Sum_{k=0..n} (3^k + 1)/2. Partial sums of A007051.
%F G.f.: (1 - 2*x)/((1 - x)^2*(1 - 3*x)). (End)
%F 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
%F a(n+1) = 3*a(n) - n. - _Franklin T. Adams-Watters_, Jul 05 2014
%F E.g.f.: exp(x)*(1 + 2*x + 3*exp(2*x))/4. - _Stefano Spezia_, Sep 26 2023
%t 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 *)
%o (Sage) [(gaussian_binomial(n,1,3)+n)/2 for n in range(1,28)] # _Zerinvary Lajos_, May 29 2009
%o (Magma) [(3^(n+1)+2*n+1)/4: n in [0..40]]; // _Vincenzo Librandi_, May 02 2011
%o (PARI) a(n)=(3^(n+1)+2*n+1)/4 \\ _Charles R Greathouse IV_, Mar 02 2012
%Y Cf. A007051.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_