login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A295224 Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals up to rotation (k >= 3). 12
1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 1, 2, 7, 6, 1, 1, 3, 12, 25, 19, 1, 1, 3, 19, 57, 108, 49, 1, 1, 4, 26, 118, 366, 492, 150, 1, 1, 4, 35, 203, 931, 2340, 2431, 442, 1, 1, 5, 46, 332, 1989, 7756, 16252, 12371, 1424, 1, 1, 5, 57, 494, 3766, 20254, 68685, 115940, 65169, 4522 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,9

COMMENTS

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

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

LINKS

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.

E. Krasko, A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.

Wikipedia, Fuss-Catalan number

FORMULA

T(n,k) ~ A295222(n,k)/n for fixed k.

EXAMPLE

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 |    1     2      2       3        3         4 ...

   4 |    4     7     12      19       26        35 ...

   5 |    6    25     57     118      203       332 ...

   6 |   19   108    366     931     1989      3766 ...

   7 |   49   492   2340    7756    20254     45448 ...

   8 |  150  2431  16252   68685   219388    580203 ...

   9 |  442 12371 115940  630465  2459730   7684881 ...

  10 | 1424 65169 854981 5966610 28431861 104898024 ...

  ...

MATHEMATICA

u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);

T[n_, k_] := u[n, k, 1] + (If[EvenQ[n], u[n/2, k, 1], 0] - u[n, k, 2])/2 + DivisorSum[GCD[n - 1, k], EulerPhi[#]*u[(n - 1)/#, k, k/#]&]/k;

Table[T[n - k + 1, k], {n, 1, 13}, {k, n, 3, -1}] // Flatten (* Jean-Fran├žois Alcover, Nov 21 2017, after Andrew Howroyd *) *)

PROG

(PARI) \\ 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) = u(n, k, 1) + (if(n%2==0, u(n/2, k, 1))-u(n, k, 2))/2 + 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);

(Python)

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 u(n, k, 1) + ((u(n//2, k, 1) if n%2==0 else 0) - u(n, k, 2))//2 + 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 code

CROSSREFS

Columns k=3..6 are A001683(n+3), A005034, A005038, A221184(n-1).

Cf. A033282, A070914, A295222, A295259, A295260.

Sequence in context: A007738 A186520 A158570 * A074749 A194524 A117136

Adjacent sequences:  A295221 A295222 A295223 * A295225 A295226 A295227

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Nov 17 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 13 06:11 EDT 2021. Contains 343836 sequences. (Running on oeis4.)