A052394 -id:A052394 - cp's OEIS frontend

A303912 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled k-ary cacti having n polygons.

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

Offset: 0

Andrew Howroyd, May 02 2018

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.

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

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

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

Cf. A070914, A303694, A303913.

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

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

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.

A054362 Number of unlabeled 4-gonal cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 3, 11, 52, 307, 1936, 13207, 93496, 683988, 5127163, 39230669, 305299420, 2410624122, 19273255184, 155780437711, 1271253542364, 10462650241996, 86765190816362, 724450039738076, 6086167189623746, 51416796881915019

Offset: 0

Simon Plouffe

nonn

Also, the number of noncrossing partitions up to rotation composed of n blocks of size 4. - Andrew Howroyd, Apr 30 2018

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=4 of A303694.

Cf. A052394, A052395, A303870.

with(combinat): with(numtheory): m := 4: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od: # Zerinvary Lajos, Dec 01 2006

a[0] = 1;
a[n_] := (DivisorSum[n, EulerPhi[n/#] Binomial[4#, #]&] + DivisorSum[GCD[n - 1, 4], EulerPhi[#] Binomial[4n/#, (n-1)/#]&])/(4n) - Binomial[4n, n]/ (3n + 1);
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Jun 29 2018, after Andrew Howroyd *)

a(n) = {if(n==0, 1, (sumdiv(n, d, eulerphi(n/d)*binomial(4*d, d)) + sumdiv(gcd(n-1, 4), d, eulerphi(d)*binomial(4*n/d, (n-1)/d)))/(4*n) - binomial(4*n, n)/(3*n+1))} \\ Andrew Howroyd, Apr 30 2018

a(n) = ((Sum_{d|n} phi(n/d)*binomial(4*d, d)) + (Sum_{d|gcd(n-1, 4)} phi(d)*binomial(4*n/d, (n-1)/d)))/(4*n) - binomial(4*n, n)/(3*n+1) for n > 0. - Andrew Howroyd, Apr 30 2018

More terms from Zerinvary Lajos, Dec 01 2006

A052395 Number of unlabeled asymmetric 4-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 0, 6, 28, 193, 1140, 7688, 52364, 373560, 2732836, 20506254, 156899748, 1221179922, 9642327324, 77092881840, 623120435820, 5085013101160, 41850590485164, 347060754685884, 2897800074184240, 24344668688255109, 205667186830447412, 1746375819789491992

Offset: 0

Simon Plouffe

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=4 of A303913.

Cf. A052394, A054362.

a[0] = 1;
a[n_] := DivisorSum[n, MoebiusMu[n/#] Binomial[4#, #]&]/n - 3 Binomial[4n, n]/(3n + 1);
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Jun 29 2018, after Andrew Howroyd *)

a(n) = if(n==0, 1, sumdiv(n, d, moebius(n/d)*binomial(4*d, d))/n - 3*binomial(4*n, n)/(3*n+1)) \\ Andrew Howroyd, Apr 30 2018

a(n) = (1/n)*(Sum_{d|n} mu(n/d)*binomial(4*d, d)) - 3*binomial(4*n, n)/(3*n+1) for n > 0. - Andrew Howroyd, Apr 30 2018

Terms a(13) and beyond from Andrew Howroyd, May 02 2018

cp's OEIS Frontend

A303912 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled k-ary cacti having n polygons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A054362 Number of unlabeled 4-gonal cacti having n polygons.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A052395 Number of unlabeled asymmetric 4-ary cacti having n polygons.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions