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!)
A303912 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled k-ary cacti having n polygons. 8
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 6, 6, 1, 1, 1, 5, 10, 19, 10, 1, 1, 1, 6, 15, 44, 57, 28, 1, 1, 1, 7, 21, 85, 197, 258, 63, 1, 1, 1, 8, 28, 146, 510, 1228, 1110, 190, 1, 1, 1, 9, 36, 231, 1101, 4051, 7692, 5475, 546, 1, 1, 1, 10, 45, 344, 2100, 10632, 33130, 52828, 27429, 1708, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,9

COMMENTS

A k-ary cactus is a planar k-gonal cactus with vertices on each polygon numbered 1..k counterclockwise with shared vertices having the same number. In total there are always exactly k ways to number a given cactus since all polygons are connected. See the reference for a precise definition.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], 1998-1999.

Wikipedia, Cactus graph

Index entries for sequences related to cacti

FORMULA

T(n,k) = (Sum_{d|n} phi(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1)) for n > 0.

T(n,k) ~ A070914(n,k-1)/n for fixed k > 1.

EXAMPLE

Array begins:

===============================================================

n\k| 1   2     3      4       5        6        7         8

---+-----------------------------------------------------------

0  | 1   1     1      1       1        1        1         1 ...

1  | 1   1     1      1       1        1        1         1 ...

2  | 1   2     3      4       5        6        7         8 ...

3  | 1   3     6     10      15       21       28        36 ...

4  | 1   6    19     44      85      146      231       344 ...

5  | 1  10    57    197     510     1101     2100      3662 ...

6  | 1  28   258   1228    4051    10632    23884     47944 ...

7  | 1  63  1110   7692   33130   107062   285390    662628 ...

8  | 1 190  5475  52828  291925  1151802  3626295   9711032 ...

9  | 1 546 27429 373636 2661255 12845442 47813815 147766089 ...

...

MATHEMATICA

T[0, _] = 1;

T[n_, k_] := DivisorSum[n, EulerPhi[n/#] Binomial[k #, #]&]/n - (k-1) Binomial[n k, n]/((k-1) n + 1);

Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* Jean-Fran├žois Alcover, May 22 2018 *)

PROG

(PARI) T(n, k)={if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1))}

CROSSREFS

Columns 2..7 are A054357, A052393, A052394, A054363, A054366, A054369.

Cf. A070914, A303694, A303913.

Sequence in context: A096751 A293551 A099233 * A133815 A305027 A323718

Adjacent sequences:  A303909 A303910 A303911 * A303913 A303914 A303915

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, May 02 2018

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 25 17:36 EDT 2020. Contains 334595 sequences. (Running on oeis4.)