\\ PARI program code based on combinatorial definition.
\\ Number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n
\\ such that all but k such pairs are joined by an edge.
\\ Sequences:
\\   A318268 (k=3)
\\   A318269 (k=4)
\\   A318270 (k=5)

\\ The implementation is that of a finite state machine where the number of states is dependent on k, but not on n.
\\ The corresponding sequence is then guaranteed to be a linear recurrence with constant coefficients with an order
\\ not exceeding the number of states. (See for example Flajolet and Sedgewick, Analytic Combinatorics, section
\\ I.4.2, Finite automata, proposition 1.3). By generating at least twice this number of terms the coefficients of
\\ the linear recurrence can be found.



\\ RowStep function
\\ Iterates one row of the ladder graph.
\\ Input is a matrix of (state, count) pairs where the count is the number of ways to reach the state.
\\ Output is a similar matrix but advanced by one row.
\\ Parts of state key
\\  q: 0..2: number of unfilled slots in previous row - these must be linked to next row
\\  u: 0..2: number of slots in previous row that are paired with open non neighboring vertices
\\  v: 0..k: number of remaining non-edge pairs to start
\\  w: 0..k: number of remaining non-edge pairs to finish
RowStep(M)={
  local(S=Map());
  \\ acc adds key [q,u,v,w] to state dictionary with count of t.
  my(acc(t, q, u, v, w)=
      my(key=[q,u,v,w], z); 
      mapput(S, key, if(mapisdefined(S, key, &z), z + t, t)); 
      ); \\ end of acc
  my(put(t, q, u, v, w)=
      for(i=0, min(q, v),
        acc(t*binomial(q,i), q-i, i, v-i, w+i);
        for(j=1, min(q-i, w-u),
           acc(t*binomial(q,i)*binomial(q-i,j)*j!*binomial(w-u, j), q-i-j, i, v-i, w+i-j) ));
      ); \\ end of put
  
  for(i=1, matsize(M)[1], 
      my(t=M[i,2], [q, u, v, w] = M[i,1]);
      if (q==2, put(t, 0, u, v, w),
         if(q==1, put(t, 1, u, v, w),
             \\ otherwise q==0
             \\ pair with neighbor on same row
             put(t, 0, u, v, w);
             \\ forward pair or back pair, but not to previous row 
             put(t, 2, u, v, w);
             \\ also possible to pair with opposite corner of previous row
             if(u==2, put(t, 0, u-2, v, w-2));
             if(u>=1, put(t*u, 1, u-1, v, w-1));
         )));
  Mat(S); 
}


\\ MaxRecurrenceOrder function
\\ Computes the total number of finite state machine states for a given k.
\\ This is an upper bound on the order of the linear recurrence.
\\ For k=1..10 returned values are: 7, 15, 25, 39, 55, 75, 97, 123, 151, 183
MaxRecurrenceOrder(k)={
   my(S=Map(), L=List([[0, 0, k, 0]]), n=0);
   while (n<#L,
      n++;
      my(M=RowStep(Mat([L[n], 1])));
      for(i=1, matsize(M)[1],
         my(key=M[i,1]);
         if (!mapisdefined(S, key), mapput(S,key,1); listput(L,key)) );
   ); \\ end of while
   n;
}

\\ Seq function
\\ Generates terms of the sequence.
\\ Returns vector of values for indexes 1..n.
Seq(n,k)={
  my(v=vector(n));
  my(M=Mat([[0, 0, k, 0], 1]));
  for(n=1, n,
     M = RowStep(M);
     v[n] = sum(i=1, matsize(M)[1], if(M[i,1] == [0,0,0,0], M[i,2], 0)) );
  v
}

A318268(n) = concat([0], Seq(n,3));
A318269(n) = concat([0], Seq(n,4));
A318270(n) = concat([0], Seq(n,5));