Just run $k$ from $A+1$ instead of $A+2$. I forgot I made that tweak when simplifying the code. As for efficiency: I do need to correct myself. For a single value, the matrix approach is $O(\lg^3 n)$ so it is better than dp.

It's dynamic programming rather than recursion. It computes the first $N$ values in $O(N)$ time and $O(N)$ memory. Your code takes $\Theta(n^3)$ time in the worst case to calculate a single value.

Python

To be frank, if you want to add code then I think you should use a single loop exploiting the formulae already present in OEIS: a(2n+1) = a(n) for n >= 0 and a(2^m*(2n+1)) = a(2^m*n) + a(2^(m-1)*(2n+1)) + a(2^(m-1)*(4n+1)) for m > 0, n >= 0. That will be both more efficient and more legible.

I basically got there by implementing your algorithm in Sage and then refactoring it to make it more idiomatic Python. The end result is what I link, and the process can be more-or-less read off from it.

My Sage code. I've generalised the binomial coefficients to an arbitrary triangle of coefficients $C_{n,k}$ and it still seems to work. Note that for your final question, $k$ is just $C_{1,0}$. I observe that the process can be rewritten by taking $t$ to be an infinite sequence of $1$s and then for each bit in $n$, most significant first, if it's a $1$ we multiply by the triangular matrix $C$ and if it's a $0$ we shift off the first element of $t$. The result is $t_0$ after the process completes.

I presume in the definition of $L$ that the bound variable should be $k$ rather than $i$, but I'm not sure about the indexing of $T$. Is $L$ the number of $1$s in the binary expansion of $2n$, or the number of $0$s?

$mn$, so there must be something I'm not seeing. Are you actually interested in the assignment of the $nk$ edges which minimises the maximum $pq$?

What does it mean for a graph to "have polynomial bounded number of cycles"? For any given graph the number of cycles is a constant. It makes sense (although in general probably isn't interesting) to pick a specific polynomial $P$ and ask about the class of graphs $(V, E)$ for which the number of cycles is bounded by $P(|V|)$; and it potentially makes sense to ask for which graph classes we can define a polynomial $Q$ such that all graphs $(V, E)$ in that class have number of cycles bounded by $Q(|V|)$, but neither of those appear to be what you're asking about.

For fixed $S$ and $F$ there's always a rational generating function over $n$. Consider a finite state machine whose states are subsets of $S$ whose elements are pairwise related, with a transition from a subset $\sigma_i$ to any superset which adds one element, and a loop from $\sigma_i$ to itself for each reflexive element it contains. Then the g.f. counts Markov chains in this FSM, so is rational.

Yes, even extending back to $f_0(p) = 1, f_1(p) = p^4$ we don't get a clean numerator. $1 + (p^4-2p-4)z + (-p^5 - p^4 - 2p^3 - p^2 + 9p + 6)z^2 + (p^5 + p^4 + 6p^3 - p^2 - 13p - 4)z^3 + (-p^7 + 5p^6 - 7p^5 - p^4 + p^3 - 2p^2 + 9p + 1)z^4 + (p^8 - 4p^7 + 4p^6 + 2p^5 - 5p^4 + 4p^3 - p^2 - 2p)z^5$

I've managed to significantly optimise the calculations to the point that I can get data for $p=13$, $n=21$, and that gives enough polynomials to conjecture a recurrence which implies the desired g.f. I haven't attempted to write the g.f. explicitly because I suspect it's quite large. Edit: although actually the denominator factors nicely as $(z-1)^4 (pz-1)^2$ so maybe not.

The vertices are $2\times 2$ graphs over $\mathbb{Z}/p\mathbb{Z}$, with edges between matrices which anti-commute and loops on matrices which anti-commute with themselves.