login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A295259 Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation and reflection (k >= 3). 8
1, 1, 1, 1, 1, 2, 1, 1, 4, 6, 1, 1, 4, 13, 16, 1, 1, 6, 22, 64, 52, 1, 1, 6, 35, 147, 315, 170, 1, 1, 8, 49, 302, 1074, 1727, 579, 1, 1, 8, 67, 518, 2763, 8216, 9658, 1996, 1, 1, 10, 87, 843, 5916, 27168, 64798, 55657, 7021 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,6

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 f.

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.

Wikipedia, Fuss-Catalan number

FORMULA

T(n,k) ~ A295222(n,k)/2 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 |    2      4       4        6         6         8 ...

   4 |    6     13      22       35        49        67 ...

   5 |   16     64     147      302       518       843 ...

   6 |   52    315    1074     2763      5916     11235 ...

   7 |  170   1727    8216    27168     70984    159180 ...

   8 |  579   9658   64798   274360    876790   2319678 ...

   9 | 1996  55657  521900  2837208  11069760  34582800 ...

  10 | 7021 325390 4272967 29828330 142148343 524470485 ...

  ...

MATHEMATICA

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

F[n_, k_] := DivisorSum[GCD[n-1, k], EulerPhi[#]*u[(n-1)/#, k, k/#] &]/k;

T[n_, k_] := (F[n, k] + If[OddQ[k], If[OddQ[n], u[(n-1)/2, k, (k-1)/2], u[n/2-1, k, k-1]], If[OddQ[n], u[(n-1)/2, k, k/2+1], u[n/2-1, k, k]]])/2;

Table[T[n-k-1, k], {n, 1, 14}, {k, n-2, 3, -1}] // Flatten (* Jean-Fran├žois Alcover, Jan 19 2018, translated from PARI *)

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)}

F(n, k) = {sumdiv(gcd(n-1, k), d, eulerphi(d)*u((n-1)/d, k, k/d))/k}

T(n, k) = {(F(n, k) + if(k%2, if(n%2, u((n-1)/2, k, (k-1)/2), u(n/2-1, k, (k-1))), if(n%2, u((n-1)/2, k, k/2+1), u(n/2-1, k, k)) ))/2; }

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 F(n, k): return sum([totient(d)*u((n - 1)//d, k, k//d) for d in divisors(gcd(n - 1, k))])//k

def T(n, k): return (F(n, k) + ((u((n - 1)//2, k, (k - 1)//2) if n%2 else u(n//2 - 1, k, k - 1)) if k%2 else (u((n - 1)//2, k, k//2 + 1) if n%2 else u(n//2 - 1, k, k))))//2

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..5 are A003446, A005035, A005039.

Cf. A033282, A070914, A295222, A295224, A295260.

Sequence in context: A143392 A090668 A307977 * A255009 A156579 A322266

Adjacent sequences:  A295256 A295257 A295258 * A295260 A295261 A295262

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Nov 18 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 August 22 00:43 EDT 2019. Contains 326169 sequences. (Running on oeis4.)