cp's OEIS Frontend

The old name (referring to the Chen-Goyal article) was "[Number of] essential complementary partitions of [an] n-set."

This sequence was obtained using the deletion-contraction recursions satisfied by the number of spanning trees for graphs. It is readily seen that the number of spanning trees in K_{n}-e (the complete graph K_{n} with an edge e deleted) is (n-2)*(n^{n-3}). Since the number of spanning trees in K_{n} is n^{n-2}, we see that (n-2)*(n^{n-3})+f(n)=n^{n-2} by the deletion-contraction recursion. Hence it follows that f(n)=2*n^{n-3}. - N. Eaton, W. Kook and L. Thoma (andrewk(AT)math.uri.edu), Jan 17 2004

With offset 0, the number of acyclic functions from {1,...,n} to {1,...,n+2}. See link below. - Dennis P. Walsh, Nov 27 2011

With offset 0, a(n) is the number of forests of rooted labeled trees on n nodes in which some (possibly all or none) of the trees have been specially designated. a(n) = Sum_{k=1..n} A061356(n,k)*2^k. E.g.f. is exp(T(x))^2 where T(x) is the e.g.f for A000169. The expected number of trees in each forest approaches 3 as n gets large. Cf. A225497. - Geoffrey Critzer, May 10 2013

Odd prime p divides a(p-2). For n>1, a(prime(n)-2)/prime(n) = A125074(n) = {1, 29, 3343, 407889491, 298572057493, 454195874136455153, ...}. Prime p divides a((p+5)/2) for p = {19, 23, 61}. - Alexander Adamchuk, Nov 18 2006

From Mathew Englander, Jul 08 2020: (Start)

For all n != 1, a(n) mod 8 = 1.

If n mod 6 = 0, 3, or 5, then a(n) mod 6 = 1. If n mod 6 = 1, then a(n) mod 6 = 3. If n mod 6 = 2 or 4, then a(n) mod 6 = 5.

For all n, a(n)-1 is a multiple of n^2.

For n odd and n >= 3, a(n)-1 is a multiple of (n+1)^2.

For n even and n >= 0, a(n)+1 is a multiple of (n+1)^2.

For proofs, see the Englander link. (End)

There are two size of classes, n or 2n.

n c:n c:2n (c:n)/n (c:2n)/n

0 1

1 1

2 2

3 3 3 1 1

4 8 28 2 7

5 25 300 5 60

6 72 3852 12 642

7 343 58653 49 8379

There are two size of classes, n or 2n.

.

n c:n c:2n (c:2n)/4

0 1

1 1

2 2

3 1 4 1

4 8 28 7

5 1 312 78

6 32 3872 968

7 1 58824 14706

For n odd, only the set of n constant functions can have a member of their class equal to their complement, so c:n size is 1.

For n even, the c:n class is populated by binary words using k for 0 and n+1-k for 1. There are (2^n)/2 such words as the complement operation identifies them by pairs.

For n odd, c:2n(n) = (n^n - 1*n)/(2*n)

For n even, c:2n(n) = (n^n - 2^(n-1)*n)/(2*n)

There are three size of classes : n, 2n, 4n.

n c:n c:2n c:4n

----------------------------------

0 1

1 1

2 2

3 1 2 1

4 4 10 10

5 1 24 144

6 8 148 1868

7 1 342 29241

For n odd, only the set of n constant functions can have a member of their class equal to their complement, so c:n size is 1.

For n even, we have 2^(n/2) binary words which have mirror-symmetry

There are three types of classes of size of 2n (stable by reversal, stable by complement, stable by rc as in A275550).

Because of the interaction between the two symmetries indexed by n, classes can be of size from n up to 2*n^2.

.

n possible class sizes

-------------------------------

1 1

2 2

3 3, 6, 18

4 4, 8, 16, 32

5 5, 10, 50

6 6, 12, 18, 24, 36, 72

7 7, 14, 98

.

but classes of size 2*n^2 account for the bulk of a(n).

n number of classes

-----------------------------------

1 1

2 2

3 1, 1, 1

4 2, 3, 4, 5

5 1, 2, 62

6 2, 4, 2, 2, 48, 622

7 1, 3, 8403

Because of the interaction between the two symmetries indexed by n, classes can be of size from n up to 2*n^2.

n possible class sizes

-----------------------------------

1 1

2 2

3 3, 6, 9

4 4, 8, 16, 32

5 5, 10, 25, 50

6 6, 12, 18, 24, 36, 72

7 7, 14, 49, 98

but classes of size 2*n^2 account for the bulk of a(n).

n number of classes

-----------------------------------

1 1

2 2

3 1, 1, 2

4 2, 3, 8, 3

5 1, 2, 24, 50

6 2, 4, 10, 2, 136, 576

7 1, 3, 342, 8232

Because of the interaction between the two symmetries indexed by n and the two involutions, classes can be of size from n up to 4*n^2.

.

n possible class sizes

------------------------------------

1 1

2 2

3 3, 6, 18

4 4, 8, 16, 32, 64

5 5, 10, 50, 100

6 6, 12, 18, 24, 36, 72, 144

7 7, 14, 98, 196

.

but classes of size 4*n^2 account for the bulk of a(n).

n number of classes

------------------------------------

1 1

2 2

3 1, 1, 1

4 2, 3, 4, 3, 1

5 1, 2, 22, 20

6 2, 4, 2, 2, 28, 116, 258

7 1, 3, 339, 4032

Classes can be of size 1,2,4, n and 2n.

n 1 2 4 n 2n

--------------------------

1 1

2 0 2

3 1 1 4

4 0 4 4 2 28

5 1 2 0 0 312

6 0 6 6 70 3850

7 1 3 0 0 58824

For n odd, the constant function (n+1)/2 is the only stable by rotation and complement. So #c1=1.

For n even, there is no stable function, so #c1=0, but constant functions are grouped two by two making n/2 classes of size 2. Functions alternating a value and its complement are also grouped two by two, making another n/2 classes. This gives #c2=n.