login
a(n) = (n+1)*a(n-1) + (n+2)*a(n-2) + a(n-3); a(1)=0, a(2)=3, a(3)=13.
(Formerly M2955 N1193)
9

%I M2955 N1193 #105 Jul 28 2024 23:06:09

%S 0,3,13,83,592,4821,43979,444613,4934720,59661255,780531033,

%T 10987095719,165586966816,2660378564777,45392022568023,

%U 819716784789193,15620010933562688,313219935456042955,6593238655510464741

%N a(n) = (n+1)*a(n-1) + (n+2)*a(n-2) + a(n-3); a(1)=0, a(2)=3, a(3)=13.

%C Numbers connected with the ménage problem (cf. A000179).

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A000904/b000904.txt">Table of n, a(n) for n=1..100</a>

%H E. Lucas, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k29021h">Théorie des Nombres</a>, Gauthier-Villars, Paris, 1891, Vol. 1, p. 495.

%H E. Lucas, <a href="/A000904/a000904.pdf">Théorie des Nombres</a>, Gauthier-Villars, Paris, 1891, Vol. 1. [Annotated scan of pages 488-499 only]

%F G.f.: (1/(x+x^2)^2)*Sum_{n>=0} n!*(x/(1+x)^2)^n. - _Vladeta Jovovic_, Jun 29 2007

%F G.f.: (1/E(0)-1+x-x^2)/x^2 where E(k) = (1+x)^2 + k*x - (k+1)*x*(1+x)^2/E(k+1); (continued fraction, Euler's 1st kind, 1-step). - _Sergei N. Gladkovskii_, Sep 17 2012

%F From _Vladimir Shevelev_, Jun 29 - Jul 22 2015: (Start)

%F Using formulas in [Lucas], we have

%F (i) a(1)=0, a(2)=3, for n>=3, a(n) = (n+2)*a(n-1) + a(n-2) + 2*(-1)^n

%F (Note that (i) yields a(3)=13 and, for n>=4,

%F a(n-1) = (n+1)*a(n-2) + a(n-3) - 2*(-1)^n. Summing this with (i), we see that (i) defines A000904);

%F (ii) for n>=1, a(n) = (A000179(n+3) + 2*(-1)^n)/(n+3);

%F (iii) for n>=3, a(n) = a(n-2) + A000179(n+2);

%F (iii)* if n is even, then a(n) = Sum_{i=0..(n+2)/2} A000179(2*i);

%F (iii)** if n is odd, then a(n) = Sum_{i=2..(n+1)/2} A000179(2*i+1).

%F Also

%F (iv) a(n+1) = A000271(n+3) - a(n);

%F (iv)* a(n) = Sum_{i=0..n+2}(-1)^i*A000271(n-i+2);

%F (v) a(n-2) = Sum_{i=0..n}(-1)^i*binomial(2*n-i+1, i)*(n-i)!, n>=3.

%F Note that Lucas considered this sequence with other initials. His formulas (i) - (iii), which he proved on pp. 491-495 of his book [Lucas], we wrote for the current initials.

%F The other 5 formulas, including the explicit formula 5), are new and we give their proofs:

%F (iii)*,(iii)**. Formulas (iii)* and (iii)** are obtained by the direct summation of (iii) over even and odd values respectively, taking into account the initials.

%F (iv). To obtain (iv), write (iii) in the form

%F a(j+1) - a(j) = -(a(j) - a(j-1)) + A000179(j+3), j>=2.

%F Summing Sum_{j=2..n}, we have

%F a(n+1) - a(2) = -a(n) + a(1) + Sum_{j=2..n}A000179(j+3). Since a(1)=0, a(2)=3, we find

%F a(n+1)-3 = -a(n) + Sum_{i=5..n+3}A000179(i). But A000179(3)=1, A000179(4)=2. Therefore, we have

%F a(n+1) = -a(n) + Sum_{i=3..n+3}A000179(i).

%F It is left to note that, by the definition,

%F A000271(n) = Sum{i=3..n}A000179(i). So

%F a(n+1) = A000271(n+3) - a(n).

%F (iv)*. In view of the first four initials 1,0,0,1 of A000271, we have

%F Sum_{i=0..n+2}(-1)^i*A000271(n-i+2) = Sum_{i=0..n-2}(-1)^i*A000271(n-i+2) and, by (iv), the last sum equals

%F Sum_{i=0..n-2}(-1)^i(a(n-i)+a(n-i-1)) = a(n) + (-1)^(n-2)*a(1) = a(n).

%F (v). We use induction for n>=3. In case n=3 (v) gives 6-6*2+10-4=0 = a(1). Set n:=n+2.

%F Suppose for some (now n>=1) we have

%F a(n) = Sum_{i=0..n+2}(-1)^i*binomial(2*n-i+5, i}*(n+2-i)! (*)

%F Further we use (iv). In A259212 we proved an explicit formula for A000271(n-1) such that we have

%F A000271(n+3) = Sum_{j=0..n+3}(-1)^j * binomial(2*n-j+6,j)*(n-j+3)!, n>3.

%F Now, by (iv) and (*) with changing summing j=i+1, we have

%F a(n+1) = Sum_{j=0..n+3}(-1)^j * binomial(2*n-j+6,j)*(n-j+3)! + Sum_{j=1..n+3}(-1)^j* binomial(2*n-j+6, j-1}*(n+3-j)!

%F Since binomial(n,-1)=0, then in the second sum the summing could begin with j=0.

%F So, we have

%F a(n+1) = Sum_{j=0..n+3}}(-1)^j* binomial(2*n-j+7, j}*(n+3-j)! = Sum_{j=0..n+3}(-1)^j* binomial(2*(n+1)-j+5,j)*((n+1)+2-j)!

%F Thus this expression formally is obtained from (*) by replacing n with n+1.

%F QED (End)

%F a(n) ~ n! * n^2 / exp(2). - _Vaclav Kotesovec_, Jul 04 2015

%e G.f. = 3 x^2 + 13 x^3 + 83 x^4 + 592 x^5 + 4821 x^6 + 43979 x^7 + 444613 x^8 + ...

%t max = 19; f[x_] = 1/(x+x^2)^2 * Sum[ n!*(x/(1+x)^2)^n, {n, 0, max+2}]; Series[ f[x]+1/x-1/x^2, {x, 0, max}] // CoefficientList[#, x]& // Rest (* _Jean-François Alcover_, May 16 2013, after _Vladeta Jovovic_ *)

%t RecurrenceTable[{a[1]==0,a[2]==3,a[3]==13,a[n]==(n+1)a[n-1]+(n+2)a[n-2]+a[n-3]},a,{n,20}] (* _Harvey P. Dale_, Aug 03 2016 *)

%o (Haskell)

%o a000904_list = 0 : 3 : 13 : zipWith (+) a000904_list

%o (zipWith (+) (zipWith (*) [6..] $ drop 1 a000904_list)

%o (zipWith (*) [5..] $ drop 2 a000904_list))

%o -- _Reinhard Zumkeller_, Nov 22 2011

%Y Cf. A000179, A000271.

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_

%E More terms from Larry Reeves (larryr(AT)acm.org), Nov 27 2001