Middle Trinomial Coefficients:

a(n) = [z^n] (1 + z + z*z)^n


1
1     1     1
1     2     3     2     1
1     3     6     7     6     3     1
1     4    10    16    19    16    10     4     1
1     5    15    30    45    51    45    30    15     5     1
1     6    21    50    90   126   141   126    90    50    21     6     1
1     7    28    77   161   266   357   393   357   266   161    77    28     7     1


In [GKP94 Problem 7.56] you find the following research problem:

Prove that there is no "simple closed form" for the coefficient of z^n in
(1 + z + z^2)^n, as a function of n, in some large class of "simple closed
forms".

They give references showing that there is no such form using
finite hypergeometric series.

Euler showed, incidentally, that this number is also [z^n] 1/sqrt(1-2z-3z^2),
and he gave the formular a(n) = Sum_{k>=0} (n)_2k / k!^2. 

He also discovered a "memorable failure of induction" while examining these
numbers: Although 3*a(n) - a(n+1) is equal to F(n-1)*(F(n-1) + 1) for 0<=n<9,
this empirical law mysteriously breaks down when n is 9 or more!

Recursion:

  (n+1) a(n+1)  =  (2n+1) a(n)  +  3n a(n-1).

Asymptotic:

  a(n) ~ 3^n * sqrt(3/(4*pi*n))

Congruences:

  For each prime number p we have a(p) = 1 (mod p).
  More general for each prime number p

     [z^k] (1 + z + z^2)^p  =  1 (mod p)    if k in {0,p,2p} and 
     [z^k] (1 + z + z^2)^p  =  0 (mod p)    otherwise.



Reference:

- [Com74]  Comtet 74, p 77-78, 163

- [GKP94]  Graham, Knuth, Patashnik; Concrete Mathematics, 1994, 2nd Ed.

- [And90]  George Andrews,
	   Euler's `exemplum memorabile inductionis fallacis' and $q$-trinomial coefficients,
           J. Amer. Math. Soc. 3 (1990) 653-669.

- [EIS]    The Encyclopidia of Integer Sequences

%I A002426 M2673 N1070
%S A002426 1,1,3,7,19,51,141,393,1107,3139,8953,25653,73789,212941,
%T A002426 616227,1787607,5196627,15134931,44152809,128996853,377379369,
%U A002426 1105350729,3241135527,9513228123,27948336381,82176836301
%N A002426 Central trinomial coefficient: largest coefficient of (1+x+x^2 )^n.
%R A002426 EUL (1) 15 59 1927. RCI 74. FQ 7 341 1969. Henr74 1 42. DAM 34 234 1991. GKP 575.
%K A002426 easy,huge,nonn,nice
%O A002426 0,3
%F A002426 G.f.: 1 / ( 1 + x )^1/2 (1 - 3x)^1/2 .
%A A002426 njas,sp
%E A002426 DAM ref added 5/95. Revised description 4/96.
%D A002426 The Euler reference is to his "Exemplum Memorabile Inductionis Fallacis".
%D A002426 See also R. K. Guy, The Second Strong Law of Small Numbers [Math Mag, 63(1990) 3-20, esp. 18-19]
%D A002426 George Andrews, "Euler's `exemplum memorabile inductionis fallacis' and $q$-trinomial coefficients", J. Amer. Math. Soc.  3 (1990) 653-669.