login
Number of valleys in all weighted lattice paths in B(n).
1

%I #10 Jul 22 2022 12:13:14

%S 0,0,0,0,0,0,1,4,14,45,135,391,1105,3067,8404,22806,61428,164495,

%T 438459,1164363,3082717,8141422,21457255,56455195,148323305,389213825,

%U 1020283146,2672225692,6993600748,18291536552,47814575243,124929304664,326280023426

%N Number of valleys in all weighted lattice paths in B(n).

%C The members of B(n) are paths of weight n that start at (0,0), end on but never go below the horizontal axis, and whose steps are of the following four kinds: an (1,0)-step with weight 1, an (1,0)-step with weight 2, a (1,1)-step with weight 2, and a (1,-1)-step with weight 1. The weight of a path is the sum of the weights of its steps. A valley is a (1,-1)-step followed by a (1,1)-step.

%D M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

%F a(n) = Sum(k*A182900(n,k), k>=0).

%F G.f.: G:=z^6*g^4/(1-z^3*g^2), where g=g(z) satisfies g=1+zg+z^2*g+z^3*g^2.

%F Conjecture D-finite with recurrence -3*(n+3)*(n-6)*a(n) +(n+1)*(7*n-34)*a(n-1) +2*(5*n+26)*a(n-2) +(7*n^2-39*n+16)*a(n-3) +4*(-n^2+5*n+2)*a(n-4) +(3*n^2-29*n+64)*a(n-5) -(n-4)*(n-7)*a(n-6)=0. - _R. J. Mathar_, Jul 22 2022

%e a(7) = 4. Indeed, denoting by h (H) the (1,0)-step of weight 1 (2), and U = (1,1), D = (1,-1), among the 82 paths in B(7) only hUDUD, UDUDh, UDUhD, and UhDUD have valleys (1 in each).

%p eq := g = 1+z*g+z^2*g+z^3*g^2: g := RootOf(eq, g): gser := series(z^6*g^4/(1-z^3*g^2), z = 0, 35): seq(coeff(gser, z, n), n = 0 .. 32);

%Y A182900.

%K nonn

%O 0,8

%A _Emeric Deutsch_, Dec 15 2010