\\ 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));