A289694 The number of partitions of [n] with exactly 4 blocks without peaks.

0, 0, 0, 1, 4, 16, 64, 236, 818, 2736, 8934, 28622, 90324, 281792, 871556, 2677750, 8184383, 24913238, 75593383, 228793147, 691094857, 2084237036, 6277871658, 18890568921, 56798001639, 170665733660, 512554832309, 1538718547049

Offset: 1

Author

R. J. Mathar, Jul 09 2017

Keywords

• nonn
• easy

Links

• T. Mansour and M. Shattuck, Counting Peaks and Valleys in a Partition of a Set, J. Int. Seq. 13 (2010), 10.6.8, Table 1.
• Index entries for linear recurrences with constant coefficients, signature (10,-45,130,-280,471,-643,734,-701,575,-400,237,-121,49,-18,4,-1).

Crossrefs

Cf. A289692 (2 blocks), A289693 (3 blocks).

Programs

Maple

with(orthopoly) :
nmax := 15:
tpr := 1+x^2/2 :
k := 4:
g := x^k ;
for j from 1 to k do
    if j> 1 then
        g := g*( U(j-1,tpr)-(1+x)*U(j-2,tpr)) / ((1-x)*U(j-1,tpr)-U(j-2,tpr)) ;
    else
        # note that U(-1,.)=0, U(0,.)=1
        g := g* U(j-1,tpr) / ((1-x)*U(j-1,tpr)) ;
    end if;
end do:
simplify(%) ;
taylor(g,x=0,nmax+1) ;
gfun[seriestolist](%) ; # R. J. Mathar, Mar 11 2021

Formula

G.f. x^4*(x^2-x+1)*(x^4-x^3+3*x^2-2*x+1)*(x^6-x^5+5*x^4-4*x^3+6*x^2-3*x+1) / ( (x-1)*(x^5-x^4+4*x^3-3*x^2+3*x-1)*(x^7-x^6+6*x^5-5*x^4+10*x^3-6*x^2+4*x-1)*(x^3-x^2+2*x-1) ). - R. J. Mathar, Mar 11 2021

a(n)= 10*a(n-1) -45*a(n-2) +130*a(n-3) -280*a(n-4) +471*a(n-5) -643*a(n-6) +734*a(n-7) -701*a(n-8) +575*a(n-9) -400*a(n-10) +237*a(n-11) -121*a(n-12) +49*a(n-13) -18*a(n-14) +4*a(n-15) -a(n-16). - R. J. Mathar, Mar 11 2021