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,2

Links

Table of n, a(n) for n=1..25.

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]

Prog

(PARI) a(n)=local(y=(x^4-1)/(x-1)); if(n<0, 0, polcoeff(y^n-y^(n-1), n))
(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 */

Crossrefs

Cf. A071976, A005773.

Sequence in context: A275943 A228180 A035929 * A114627 A289591 A148464

Adjacent sequences: A071643 A071644 A071645 * A071647 A071648 A071649

Keyword

nonn,base

Author

John W. Layman, Jun 22 2002

Status

approved