A303864 Array read by antidiagonals: T(n,k) = number of noncrossing path sets on k*n nodes up to rotation with each path having exactly k nodes.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 6, 2, 1, 1, 4, 36, 38, 3, 1, 1, 10, 210, 960, 384, 6, 1, 1, 16, 1176, 18680, 35956, 4425, 14, 1, 1, 36, 6328, 313664, 2280910, 1588192, 57976, 34, 1, 1, 64, 32896, 4683168, 111925464, 323840016, 77381016, 807318, 95, 1

Offset

0,12

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Example

Array begins:
=======================================================
n\k| 1  2     3        4           5              6
---+---------------------------------------------------
0  | 1  1     1        1           1              1 ...
1  | 1  1     1        3           4             10 ...
2  | 1  1     6       36         210           1176 ...
3  | 1  2    38      960       18680         313664 ...
4  | 1  3   384    35956     2280910      111925464 ...
5  | 1  6  4425  1588192   323840016    46552781760 ...
6  | 1 14 57976 77381016 50668922540 21346459738384 ...
...

Mathematica

nmax = 10; seq[n_, k_] := Module[{p, q, h}, p = 1 + InverseSeries[ x/(k*2^If[k == 1, 0, k - 3]*(1 + x)^k) + O[x]^n, x ]; h = p /. x -> x^2 + O[x]^n; q = x*D[p, x]/p; Integrate[((p - 1)/k + Sum[EulerPhi[d]*(q /. x -> x^d + O[x]^n), {d, 2, n}])/x, x] + If[OddQ[k], 0, 2^(k/2 - 2)*x*h^(k/2)] + 1];
Clear[col]; col[k_] := col[k] = CoefficientList[seq[nmax, k], x];
T[n_, k_] := col[k][[n + 1]];
Table[T[n - k, k], {n, 0, nmax}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jul 04 2018, after Andrew Howroyd *)

Prog

(PARI)
seq(n, k)={ \\ gives gf of k'th column
my(p=1 + serreverse( x/(k*2^if(k==1, 0, k-3)*(1 + x)^k) + O(x*x^n) ));
my(h=subst(p, x, x^2+O(x*x^n)), q=x*deriv(p)/p);
intformal( ((p-1)/k + sum(d=2, n, eulerphi(d)*subst(q, x, x^d+O(x*x^n))))/x) + if(k%2, 0, 2^(k/2-2)*x*h^(k/2)) + 1;
}
Mat(vector(6, k, Col(seq(7, k))))

Crossrefs

Columns 2..4 are A002995(n+1), A303865, A303866.

Row n=1 is A051437(k-3).

Cf. A302828, A303844, A303869.

Cf. A295224 (polygon dissections), A303694 (sets of cycles instead of paths).

Sequence in context: A004158 A221705 A332505 * A058178 A058078 A016551

Adjacent sequences: A303861 A303862 A303863 * A303865 A303866 A303867

Keyword

nonn,tabl

Author

Andrew Howroyd, May 01 2018

Status

approved