A110166 Row sums of Riordan array A110165.

1, 4, 18, 85, 410, 1999, 9807, 48304, 238570, 1180615, 5851253, 29033074, 144190943, 716652070, 3564079250, 17734184365, 88280673770, 439625873215, 2189988826125, 10912480440850, 54389237971285, 271142650382080

Offset: 0

Author

Paul Barry, Jul 14 2005

Keywords

• nonn
• easy

Comments

Number of 5-ary words of length n in which the number of 1's does not exceed the number of 0's. - David Scambler, Aug 14 2012

From Peter Bala, Jan 09 2022: (Start)

Conjectures: for k >= 2, the number of k-ary words of length n such that the number of 1's <= the number of 0's is equal to the coefficient of x^n in the expansion of ( k*x + 1/(1 + x) )^n, and satisfies the recurrence u(0) = 1, u(1) = k-1 and n*u(n) = (k-2)*(2*n-1)*u(n-1) - k*(k-4)*(n-1)* u(n-2) + k^(n-1) for n >= 2.

For cases see A027306 (k = 2), A027914 (k = 3) and A032443 (k = 4). (End)

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200

Crossrefs

Row sums A110165. Cf. A026375, A032443, A246437, A242586.

Programs

Maple

seq( (1/2)*(5^n + add(binomial(n,k)*binomial(2*k,k), k = 0..n)), n = 0..30); # Peter Bala, Jan 08 2022

Mathematica

Table[Sum[Sum[Binomial[n,j]Binomial[2j,j+k],{j,0,n}],{k,0,n}],{n,0,25}] (* Harvey P. Dale, Dec 16 2011 *)

Formula

G.f.: (1/sqrt(1-6*x+5*x^2))/(1-(1-3*x-sqrt(1-6*x+5*x^2))/(2*x)).

a(n) = Sum_{k = 0..n} Sum_{j = 0..n} C(n, j)*C(2*j, j+k).

Recurrence: n*a(n) = (11*n-8)*a(n-1) - 5*(7*n-10)*a(n-2) + 25*(n-2)*a(n-3). - Vaclav Kotesovec, Oct 18 2012

a(n) ~ 5^n/2*(1+sqrt(5)/(2*sqrt(Pi*n))). - Vaclav Kotesovec, Oct 18 2012

From Peter Bala, Jan 08 2022: (Start)

a(n) = (1/2)*(5^n + A026375(n)) = (1/2)*(5^n + Sum_{k = 0..n} binomial(n,k) *binomial(2*k,k)).

a(n) = (1/2)*(5^n)*(1 + Sum_{k = 0..n} binomial(n,k)*binomial(2*k,k)*(-1/5)^k).

a(n) = [x^n] ( 5*x + 1/(1 + x) )^n.

a(0) = 1, a(1) = 4 and n*a(n) = 3*(2*n-1)*a(n-1) - 5*(n-1)*a(n-2) + 5^(n-1) for n >= 2.

The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for prime p and positive integers n and k.

Binomial transform of A032443. (End)