A071646 Number of base 4 n-digit numbers with digit sum n.
1, 2, 6, 19, 61, 201, 672, 2269, 7723, 26452, 91058, 314766, 1091884, 3798900, 13251136, 46325285, 162268775, 569385098, 2001012474, 7042014879, 24813529581, 87533417037, 309107111536, 1092585807044, 3865270781236
Offset: 1
Programs
-
Maxima
a(n):=sum((sum(binomial(j,n-3*k+2*j)*binomial(k,j),j,0,k))*binomial(n-1,n-k),k,1,n); /* Vladimir Kruchinin, Nov 07 2013 */
-
PARI
a(n)=local(y=(x^4-1)/(x-1)); if(n<0,0,polcoeff(y^n-y^(n-1),n))
Formula
a(n)=[x^n] (1+x+x^2+x^3)^n-(1+x+x^2+x^3)^(n-1). - Michael Somos, Jul 19 2002
a(n)*790*(2*n^2-n) = a(n-1)*(-16328*n^4+137200*n^3-400977*n^2+489925*n-207450)+a(n-2)*(44902*n^4-399751*n^3+1267117*n^2-1672482*n+769980)+a(n-3)*4*(n-3)*(8164*n^3-52272*n^2+115397*n-81223)+a(n-4)*16*(n-4)*(n-3)*(4082*n^2-11849*n+8529), n>2. - Michael Somos, Jul 19 2002
a(n) = sum(k=1..n, (sum(j=0..k, binomial(j,n-3*k+2*j) *binomial(k,j))) *binomial(n-1,n-k)). [Vladimir Kruchinin, Nov 07 2013]