A005033 -id:A005033 - cp's OEIS frontend

A295222 Array read by antidiagonals: T(n,k) is the number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation (k >= 3).

1, 1, 1, 1, 1, 3, 1, 1, 5, 10, 1, 1, 6, 22, 30, 1, 1, 8, 40, 116, 99, 1, 1, 9, 64, 285, 612, 335, 1, 1, 11, 92, 578, 2126, 3399, 1144, 1, 1, 12, 126, 1015, 5481, 16380, 19228, 3978, 1, 1, 14, 166, 1641, 11781, 54132, 129456, 111041, 14000

Offset: 1

Andrew Howroyd, Nov 17 2017

The polygon prior to dissection will have n*(k-2)+2 sides.

In the Harary, Palmer and Read reference these are the sequences called F.

			Array begins:
  ===========================================================
  n\k|     3      4       5        6         7          8
  ---|-------------------------------------------------------
   1 |     1      1       1        1         1          1 ...
   2 |     1      1       1        1         1          1 ...
   3 |     3      5       6        8         9         11 ...
   4 |    10     22      40       64        92        126 ...
   5 |    30    116     285      578      1015       1641 ...
   6 |    99    612    2126     5481     11781      22386 ...
   7 |   335   3399   16380    54132    141778     317860 ...
   8 |  1144  19228  129456   548340   1753074    4638348 ...
   9 |  3978 111041 1043460  5672645  22137570   69159400 ...
  10 | 14000 650325 8544965 59653210 284291205 1048927880 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
Wikipedia, Fuss-Catalan number

Columns k=3..5 are A003441, A005033, A005037.

Cf. A033282, A070914, A295224, A295259, A295260.

u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);
T[n_, k_] := DivisorSum[GCD[n-1, k], EulerPhi[#]*u[(n-1)/#, k, k/#]&]/k;
Table[T[n - k + 3, k], {n, 1, 10}, {k, n + 2, 3, -1}] // Flatten (* Jean-François Alcover, Nov 21 2017, after Andrew Howroyd *)

\\ here u is Fuss-Catalan sequence with p = k+1.
u(n,k,r)={r*binomial((k - 1)*n + r, n)/((k - 1)*n + r)}
T(n,k)=sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d, k, k/d))/k;
for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);

from sympy import binomial, gcd, totient, divisors
def u(n, k, r): return r*binomial((k - 1)*n + r, n)//((k - 1)*n + r)
def T(n, k): return sum([totient(d)*u((n - 1)//d, k, k//d) for d in divisors(gcd(n - 1, k))])//k
for n in range(1, 11): print([T(n, k) for k in range(3, 9)]) # Indranil Ghosh, Dec 13 2017, after PARI

T(n,k) = Sum_{d|gcd(n-1,k)} phi(d)*u((n-1)/d, k, k/d)/k where u(n,k,r) = r*binomial((k - 1)*n + r, n)/((k - 1)*n + r).

T(n,k) ~ n*A070914(n,k-2)/(n*(k-2)+2) for fixed k.

A003454 Number of nonequivalent dissections of an n-gon by nonintersecting diagonals rooted at a cell up to rotation.

Original entry on oeis.org

1, 2, 6, 25, 107, 509, 2468, 12258, 61797, 315830, 1630770, 8498303, 44629855, 235974495, 1255105304, 6710883952, 36050676617, 194478962422, 1053120661726, 5722375202661, 31191334491891, 170504130213135, 934495666529380, 5134182220623958, 28270742653671621

Offset: 3

N. J. A. Sloane

nonn

Total number of dissections of an n-gon into polygons without reflection and rooted at a cell. - Sean A. Irvine, May 14 2015

Say two n-gons are equivalent (or in the same convexity class) if there is a bijection between the edges and vertices which preserves inclusion of vertices and edges, preserves the handedness of the polygon (does not reflect the polygon over a line), maps vertices of the convex hulls to each other, and induces an equivalence on each nontrivially connected component of Hull(X) \ X. This sequence is the number of convexity classes for an n-gon, up to rotation. - Griffin N. Macris, Mar 02 2021

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 3..200
P. Lisonek, Closed forms for the number of polygon dissections, Journal of Symbolic Computation 20 (1995), 595-601.
Ronald C. Read, On general dissections of a polygon, Aequat. math. 18 (1978) 370-388.

Cf. A001004, A003455, A003456, A005033, A295222.

Cf. A003442.

\\ See A003442 for DissectionsModCyclicRooted.
DissectionsModCyclicRooted(apply(i->1, [1..30])) \\ Andrew Howroyd, Nov 22 2017

G.f.: -f(x) - (f(x)^2 + f(x^2))/2 + Sum_{k>=1} (phi(k)/k)*log(1/(1 - f(x^k))), where phi(k) is Euler's Totient function and f(x) = (1 + x - sqrt(1 - 6x + x^2))/4 is related to the o.g.f. for A001003. - Griffin N. Macris, Mar 02 2021

More terms from Sean A. Irvine, May 14 2015

Name clarified by Andrew Howroyd, Nov 22 2017

cp's OEIS Frontend

A295222 Array read by antidiagonals: T(n,k) is the number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation (k >= 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula