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.
Original entry on oeis.org
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
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 ...
...
Cf.
A295224 (polygon dissections),
A303694 (sets of cycles instead of paths).
-
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 *)
-
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))))
A303839
Number of noncrossing path sets on n nodes up to rotation and reflection with each path having at least two nodes.
Original entry on oeis.org
1, 0, 1, 1, 3, 5, 17, 40, 138, 430, 1546, 5478, 20525, 77310, 298301, 1161692, 4583525, 18239037, 73221198, 296046399, 1205038270, 4933969005, 20311807087, 84029440358, 349201537324, 1457205298510, 6104204225832, 25661191956781, 108231773165825
Offset: 0
Case n=4: There are 3 possibilities:
.
o---o o o o---o
| | /
o---o o---o o---o
.
A303865
Number of noncrossing path sets on 3*n nodes up to rotation with each path having exactly 3 nodes.
Original entry on oeis.org
1, 1, 6, 38, 384, 4425, 57976, 807318, 11828706, 179826245, 2816100678, 45170552490, 739103543356, 12297976924176, 207577047945312, 3547290764931730, 61277684496311364, 1068648890500799799, 18794421104465407618, 333037302131948734566, 5941487005826379359448
Offset: 0
-
seq[n_] := Module[{p, q}, p = 1 + InverseSeries[x/(3*(1 + x)^3) + O[x]^n]; q = x*D[p, x]/p; Integrate[((p - 1)/3 + Sum[EulerPhi[d]*(q /. x -> x^d + O[x]^n), {d, 2, n}])/x, x] + 1];
CoefficientList[seq[21], x] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
-
seq(n)={ my(p=1 + serreverse( x/(3*(1 + x)^3) + O(x*x^n) )); my(q=x*deriv(p)/p);
Vec(intformal(((p-1)/3 + sum(d=2, n, eulerphi(d)*subst(q, x, x^d+O(x*x^n))))/x) + 1)}
A303869
Triangle read by rows: T(n,k) = number of noncrossing path sets on n nodes up to rotation with k paths and isolated vertices allowed.
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 3, 4, 2, 1, 4, 11, 8, 2, 1, 10, 34, 39, 16, 3, 1, 16, 92, 144, 90, 25, 3, 1, 36, 256, 545, 473, 197, 40, 4, 1, 64, 672, 1878, 2184, 1246, 370, 56, 4, 1, 136, 1762, 6296, 9436, 7130, 2910, 658, 80, 5, 1, 256, 4480, 20100, 38025, 36690, 19698, 6090, 1080, 105, 5, 1
Offset: 1
Triangle begins:
1;
1, 1;
1, 1, 1;
3, 4, 2, 1;
4, 11, 8, 2, 1;
10, 34, 39, 16, 3, 1;
16, 92, 144, 90, 25, 3, 1;
36, 256, 545, 473, 197, 40, 4, 1;
64, 672, 1878, 2184, 1246, 370, 56, 4, 1;
136, 1762, 6296, 9436, 7130, 2910, 658, 80, 5, 1;
...
-
\\ See A303732 for NCPathSetsModCyclic
{ my(rows=Vec(NCPathSetsModCyclic(vector(10, k, y))-1));
for(n=1, #rows, for(k=1,n,print1(polcoeff(rows[n],k), ", ")); print;)}
A303836
Number of noncrossing path sets on n nodes up to rotation with isolated vertices allowed.
Original entry on oeis.org
1, 1, 2, 3, 10, 26, 103, 371, 1552, 6475, 28414, 126530, 577188, 2670332, 12538434, 59554199, 285882600, 1384875627, 6763821250, 33276183371, 164789380052, 820923863918, 4111708742153, 20695831549310, 104642143845428, 531295928725508, 2707906874407464
Offset: 0
Case n=4: There are 10 possibilities:
.
o o o o o o o o o---o
/ |
o o o---o o o o---o o---o
.
o o o o o o o---o o---o
/ \ | | / \
o---o o---o o---o o---o o---o
.
Showing 1-5 of 5 results.