A357484 Number of linearity regions of a max-pooling function with a 3 by n input and 2 by 2 pooling windows.

1, 14, 150, 1536, 15594, 158050, 1601356, 16223814, 164366170, 1665216896, 16870539234, 170917714410, 1731590444316, 17542976546494, 177730263461890, 1800609290091936, 18242215773029194, 184814350419581330, 1872379131238643436, 18969325721395559574

Offset

1,2

Comments

a(n) is also the number of vertices of the Minkowski sum of 2*n-2 simplices conv(e_{i,j},e_{i,j+1},e_{i+1,j},e_{i+1,j+1}) for i=0,1 and j=0,...,n-2, viewing R^(3n) having basis {e_{i,j} | i=0,1,2; j=0,...,n-1}.

Links

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

Laura Escobar, Patricio Gallardo, Javier González-Anaya, José L. González, Guido Montúfar, and Alejandro H. Morales, Enumeration of max-pooling responses with generalized permutohedra, arXiv:2209.14978 [math.CO], 2022.

Index entries for linear recurrences with constant coefficients, signature (13,-31,20,-4).

Formula

a(n) = 13*a(n-1) - 31*a(n-2) + 20*a(n-3) - 4*a(n-4) for n>= 5.

G.f.: (x+x^2-x^3)/(1-13*x+31*x^2-20*x^3+4*x^4).

Example

For n = 2 the a(2)=14 vertices are (00,10), (00,11), (00,20), (00,21), (01,10), (01,11), (01,20), (01,21), (10,10), (10, 20), (10,21), (11,11), (11, 20), (11, 21), where (ij,kl) represents e_{i,j}+e_{k,l}. The pair (10,11) does not represent vertices since e_{1,0}+e_{1,1} is a convex combination of the vectors 2e_{1,0} + 2e_{1,1}. Ditto for the pair (11,10).

Maple

a:= proc(n) option remember;
   if n = 1 then
     return(1);
   elif n = 2 then
     return(14);
   elif n = 3 then
     return(150);
   elif n = 4 then
     return(1536);
   else
     return(13*a(n-1) - 31*a(n-2) + 20*a(n-3) - 4*a(n-4));
   end if;
end proc:
seq(a(n), n=1..20);

Mathematica

LinearRecurrence[{13, -31, 20, -4}, {1, 14, 150, 1536}, 20] (* Hugo Pfoertner, Oct 05 2022 *)

Prog

(Sage)
@cached_function
def a(n):
    if n < 5: return [1, 14, 150, 1536][n - 1]
    return 13*a(n-1) - 31*a(n-2) + 20*a(n-3) - 4*a(n-4)
print([a(n) for n in range(1, 21)])

Crossrefs

Cf. A007070, A033303.

Sequence in context: A153598 A180347 A262183 * A037960 A222677 A016163

Adjacent sequences: A357481 A357482 A357483 * A357485 A357486 A357487

Keyword

nonn,easy

Author

Alejandro H. Morales, Sep 30 2022

Status

approved