A303731
Number of noncrossing path sets on n nodes up to rotation and reflection with each path having a prime number of nodes.
Original entry on oeis.org
1, 0, 1, 1, 1, 5, 6, 27, 53, 140, 649, 1297, 6355, 18038, 63226, 241741, 744711, 3008107, 10028056, 37270169, 138083464, 488933323, 1872525356, 6763888465, 25498771059, 95467533318, 355595703773, 1353873044078, 5077809606803, 19345857682140, 73533468653115
Offset: 0
-
\\ number of path sets with restricted path lengths
NCPathSetsModDihedral(v)={ my(n=#v);
my(p=serreverse(x/(1 + x*v[1] + sum(k=2, #v, (k*2^(k-3))*x^k*v[k])) + O(x^2*x^n) )/x);
my(vars=variables(p));
my(h=substvec(p + O(x^(n\2+1)),vars,apply(t->t^2, vars)));
my(q=x*deriv(p)/p);
my(R=v[1]*x + sum(i=1, (#v-1)\2, v[2*i+1]*2^(i-1)*x*(x^2*h)^i), Q=sum(i=1, #v\2, v[2*i]*2^(i-1)*(x^2*h)^i), T=intformal((p - 1 + sum(d=2,n, eulerphi(d)*substvec(q + O(x^(n\d+1)), vars, apply(t->t^d, vars))))/x));
O(x*x^n) + (1 + T + (1 + Q + (1+R)^2*h/(1-Q) + v[2]*x^2*h)/2)/2;
}
Vec(NCPathSetsModDihedral(vector(30, k, isprime(k))))
A303732
Number of noncrossing path sets on n nodes up to rotation with each path having a prime number of nodes.
Original entry on oeis.org
1, 0, 1, 1, 1, 7, 8, 45, 96, 258, 1260, 2511, 12594, 35799, 126043, 482640, 1487929, 6012740, 20051360, 74529198, 276148256, 977824914, 3744986184, 13527623583, 50997301218, 190934525258, 711190503929, 2707743977818, 10155615925523, 38691707792278
Offset: 0
-
\\ number of path sets with restricted path lengths
NCPathSetsModCyclic(v)={ my(n=#v);
my(p=serreverse(x/(1 + x*v[1] + sum(k=2, #v, (k*2^(k-3))*x^k*v[k])) + O(x^2*x^n) )/x);
my(vars=variables(p));
my(h=substvec(p + O(x^(n\2+1)),vars,apply(t->t^2, vars)));
my(q=x*deriv(p)/p);
my(Q=sum(i=1, #v\2, v[2*i]*2^(i-1)*(x^2*h)^i));
1 + Q/2 + intformal((p - 1 + sum(d=2, n, eulerphi(d)*substvec(q + O(x^(n\d+1)), vars, apply(t->t^d, vars))))/x)
}
Vec(NCPathSetsModCyclic(vector(30, k, isprime(k))))
A303730
Number of noncrossing path sets on n nodes with each path having at least two nodes.
Original entry on oeis.org
1, 0, 1, 3, 10, 35, 128, 483, 1866, 7344, 29342, 118701, 485249, 2001467, 8319019, 34810084, 146519286, 619939204, 2635257950, 11248889770, 48198305528, 207222648334, 893704746508, 3865335575201, 16761606193951, 72860178774410, 317418310631983, 1385703968792040
Offset: 0
Case n=3: There are 3 possibilities:
.
o o o
/ \ / \
o---o o---o o o
.
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
.
-
InverseSeries[x*(1 - 2*x)^2/(1 - 4*x + 5*x^2 - x^3) + O[x]^30, x] // CoefficientList[#, x]& // Rest (* Jean-François Alcover, Jul 03 2018, from PARI *)
-
Vec(serreverse(x*(1 - 2*x)^2/(1 - 4*x + 5*x^2 - x^3) + O(x^30)))
Showing 1-3 of 3 results.
Comments