Dim[QuotientSpace[diags_List, rels_List], opts___] := Module[
{
debug = Debug /. {opts} /. Debug -> False,
diagtoindex, mat, rel
},
diagtoindex = Dispatch[Thread[Rule[diags, Range[Length[diags]]]]];
mat = SparseArray[
Join @@ Table[
rel=rels[[i]];
{i,# /. diagtoindex} -> Coefficient[rel, #]& /@ Cases[{rel}, diag_P, Infinity],
{i,Length[rels]}
],
{Length[rels], Length[diags]}
];
If[debug, Print[Date[], ": Computed mat..."]];
Length[diags]-MatrixRank[mat]
];

NormalizeP[P[p___]] := P[p] /. Thread[Sort[{p}] -> Range[Length[{p}]]];
Ps[n_] := Permutations[P@@Range[n]];
Rs[k_,n_] := Module[
{j, q},
Join @@ Table[
Sum[
(#/. j-> P@@(j+0.01*Range[q]))
-(# /. j-> P@@(j-0.01*Range[q])),
{q, 2, n-k+1}
]& /@ Ps[k],
{j,k}
] /. p_P :> NormalizeP[Flatten[p]]
];
ASpace[n_] := QuotientSpace[Ps[n], Rs[n-1,n]];
PSpace[n_] := QuotientSpace[
Flatten[Ps /@ Range[n]],
Flatten[Rs[#, n]& /@ Range[n-1]]
];
DimA[m_, opts___] := Dim[ASpace[m,opts], opts];
DimP[m_, opts___] := Dim[PSpace[m,opts], opts];

DimA /@ {2,3,4, 5, 6,7}

Length /@ ASpace[7]

5040-4320

DimP /@ {2,3,4, 5, 6, 7}

Length /@ PSpace[7]

5913-5039

Basis[n_] := DeleteCases[
Permutations[P@@Range[n]],
Alternatives[
P[___,i_,j_,___] /; i==j+1 ,
P[___, i_, j_, k_, ___] /; i==j+2 && k==j+1
]
]

Basis[4]

Length /@ Basis /@ Range[10]

http://www.research.att.com/~njas/sequences/A013999 says:

Sum[n!x^n(1-x)^n+O[x]^11, {n, 0, 10}]

PrimitivesToAll[p_List] := Module[{x},
CoefficientList[Series[
Product[(1-x^i)^(-p[[i]]), {i, Length[p]}],
{x, 0, Length[p]}],x]
];
PrimitivesToAll[{1,0,1,6,34,215,1560,12785,117276,1190309}] // Rest