A006896 -id:A006896 - cp's OEIS frontend

A006897 a(n) is the number of hierarchical linear models on n unlabeled factors allowing 2-way interactions (but no higher order interactions); or the number of unlabeled simple graphs with <= n nodes.

1, 2, 4, 8, 19, 53, 209, 1253, 13599, 288267, 12293435, 1031291299, 166122463891, 50668153831843, 29104823811067331, 31455590793615376099, 64032471295321173271027, 245999896624828253856990803, 1787823725042236528801735181651, 24639597076850046760911809226614419

Offset: 0

Colin Mallows

a(n) is the number of isolated points over all simple unlabeled graphs with (n+1) nodes. - Geoffrey Critzer, Apr 14 2012

			a(2) = 4 includes the null graph G1 = [], G2 = [o], G3 = [o o], and G4 = [o-o].
a(3) = 8 includes the null graph G1 = [], G2 = [o], G3 = [o o], G4 = [o-o], G5 = [o o o], G6 = [o-o o], G7 = [o-o-o], and G8 = [triangle with three unlabeled nodes]. - _Petros Hadjicostas_, Apr 10 2020

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..87
Max A. Alekseyev and Allan Bickle, Forbidden Subgraphs of Single Graphs, (2024). See p. 13.

Partial sums of A000088.

Cf. A006896 (labeled case).

b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= proc(n) option remember; b(n$2, [])+`if`(n>0, a(n-1), 0) end:
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019

nn = 15; g = Sum[NumberOfGraphs[n] x^n, {n, 0, nn}]; CoefficientList[Series[g/(1 - x), {x, 0, nn}], x]  (* Geoffrey Critzer, Apr 12 2012 *)

O.g.f.: A(x)/(1-x), where A(x) is o.g.f. for A000088. - Geoffrey Critzer, Apr 12 2012

a(n) = Sum_{k=0..n} A000088(k). - Petros Hadjicostas, Apr 19 2020

Name edited by Petros Hadjicostas, Apr 08 2020

A079265 Number of antisymmetric transitive binary relations on n unlabeled points.

Original entry on oeis.org

1, 2, 7, 32, 192, 1490, 15067, 198296, 3398105, 75734592, 2191591226, 82178300654, 3984499220967, 249298391641352, 20089200308020179, 2081351202770089728

Offset: 0

N. J. A. Sloane, Feb 16 2003

Also, number of unconstrained mixed models with n factors.

A. Hess and H. Iyer, Enumeration of mixed linear models and SAS macro for computation of confidence intervals for variance components, presented at Applied Statistics in Agriculture Conference at Kansas State University 2001.

R. Bayon, N. Lygeros and J.-S. Sereni, New progress in enumeration of mixed models, Applied Mathematics E-Notes, 5 (2005), 60-65.
R. Bayon, N. Lygeros and J.-S. Sereni, Nouveaux progrès dans l'énumération des modèles mixtes, in Knowledge discovery and discrete mathematics : JIM'2003, INRIA, Université de Metz, France, 2003, pp. 243-246.
Gunnar Brinkmann and Brendan D. McKay, Counting unlabelled topologies and transitive relations.
Gunnar Brinkmann and Brendan D. McKay, Counting Unlabelled Topologies and Transitive Relations, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.1.
R. Fraïssé and N. Lygeros, Petits posets: dénombrement, représentabilité par cercles et "compenseurs", C. R. Acad. Sci. Paris, Vol. 313, series I, pp. 417-420, 1991.
Ann Marie Hess, Mixed Models Site
G. Pfeiffer, Counting Transitive Relations, preprint, 2004.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Cf. A000112 (partial orders), A091073 (transitive relations), A001930 (quasi-orders), A085628 (labeled antisymmetric transitive relations).

Cf. A079263, A006126, A006602, A006896-A006898.

a(10)-a(12) and new description from Goetz Pfeiffer (goetz.pfeiffer(AT)nuigalway.ie), Jan 21 2004

a(13)-a(15) from Brinkmann's and McKay's paper by Vladeta Jovovic, Jan 04 2006

A006898 a(n) = Sum_{k=0..n} C(n,k)2^(k(k+1)/2).

Original entry on oeis.org

1, 3, 13, 95, 1337, 38619, 2310533, 283841911, 70927591153, 35812691480115, 36383765777442685, 74185239630793429775, 303119284294591169426729, 2479814853198140771706795531, 40599509058360322571947638063605

Offset: 0

Colin Mallows

nonn

First differences of A006896.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A006896, A006897, A135748.

Table[Sum[Binomial[n,k]2^((k(k+1))/2),{k,0,n}],{n,0,20}] (* Harvey P. Dale, Apr 01 2023 *)

a(n)=sum(k=0,n,binomial(n,k)*2^(k*(k+1)/2)) \\ Paul D. Hanna, Apr 10 2009

a(n) ~ 2^(n*(n+1)/2). - Vaclav Kotesovec, Nov 27 2017

Formula and more terms from Vladeta Jovovic, Sep 20 2003

Edited by N. J. A. Sloane, Apr 12 2009 at the suggestion of Vladeta Jovovic

A135756 a(n) = Sum_{k=0..n} C(n,k) * 2^(k*(k-1)).

Original entry on oeis.org

1, 2, 7, 80, 4381, 1069742, 1080096067, 4405584869660, 72092808533798521, 4723015159635987920282, 1237987266193328694390243007, 1298087832233881093828346620725800

Offset: 0

Paul D. Hanna, Nov 27 2007

nonn

The square root of the g.f. of this sequence is an integer series (cf. A261594).

			G.f.: A(x) = 1 + 2*x + 7*x^2 + 80*x^3 + 4381*x^4 + 1069742*x^5 +...

G. C. Greubel, Table of n, a(n) for n = 0..50
Ville Salo, Decidability and Universality of Quasiminimal Subshifts, arXiv:1411.6644 [math.DS], 2014-2015.

Cf. A261594; variants: A006896, A135755.

Table[Sum[Binomial[n, k]*2^(2*Binomial[k, 2]), {k,0,n}], {n,0,25}] (* G. C. Greubel, Nov 07 2016 *)

{a(n)=sum(k=0,n,binomial(n,k)*2^(k*(k-1)))}

a(n) ~ 2^(n*(n-1)). - Vaclav Kotesovec, Nov 27 2017

A004140 Number of nonempty labeled simple graphs on nodes chosen from an n-set.

Original entry on oeis.org

0, 1, 4, 17, 112, 1449, 40068, 2350601, 286192512, 71213783665, 35883905263780, 36419649682706465, 74221659280476136240, 303193505953871645562969, 2480118046704094643352358500, 40601989176407026666590990422105, 1329877330167226219547875498464516480

Offset: 0

N. J. A. Sloane, Colin Mallows, James D. Klein

We are given n labeled points, we choose k (1 <= k <= n) of them and construct a simple (but not necessarily connected) graph on these k nodes in 2^C(k,2) ways.

a(n) is the number of (non-null) subgraphs of the complete graph with n vertices. - Maharshee K. Shah, Sep 08 2024

			n=2: there are 4 graphs: {o}, {o}, {o o}, {o-o}
......................... 1 .. 2 .. 1 2 .. 1 2

Alois P. Heinz, Table of n, a(n) for n = 0..50

Cf. A006896.

a:= n-> add (binomial(n, k)*2^(k*(k-1)/2), k=1..n):
seq (a(n), n=0..20);  # Alois P. Heinz, Oct 09 2012

nn=20;s=Sum[2^Binomial[n,2]x^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[ Series[(s-1) Exp[x],{x,0,nn}],x]  (* Geoffrey Critzer, Oct 09 2012 *)

a(n)=sum(k=1,n,binomial(n,k)*2^((k^2-k)/2))

a(n) = Sum_{k=1..n} binomial(n, k)*2^(k(k-1)/2).
E.g.f.: exp(x)*(A(x)-1), where A(x) is e.g.f. for A006125. - Geoffrey Critzer, Oct 09 2012
a(n) ~ 2^(n*(n-1)/2). - Vaclav Kotesovec, Nov 15 2014

A079263 Number of constrained mixed models with n factors.

Original entry on oeis.org

2, 6, 22, 101, 576, 4162, 38280, 451411, 6847662, 133841440

Offset: 1

N. J. A. Sloane, Feb 16 2003

A. Hess and H. Iyer, Enumeration of mixed linear models and SAS macro for computation of confidence intervals for variance components, presented at Applied Statistics in Agriculture Conference at Kansas State University 2001.

R. Bayon, N. Lygeros and J.-S. Sereni, New progress in enumeration of mixed models, Applied Mathematics E-Notes, 5 (2005), 60-65.
R. Bayon, N. Lygeros and J.-S. Sereni, Nouveaux progrès dans l'énumération des modèles mixtes, in Knowledge discovery and discrete mathematics : JIM'2003, INRIA, Université de Metz, France, 2003, pp. 243-246.
R. Fraïssé and N. Lygeros, Petits posets: dénombrement, représentabilité par cercles et "compenseurs", C. R. Acad. Sci. Paris, Vol. 313, series I, pp. 417-420, 1991.
Ann Marie Hess, Mixed Models Site

Cf. A000112, A079265, A006126, A006602, A006896-A006898.

a(10) from Bayon, Lygeros, and Sereni (2005) added by Sean A. Irvine, Aug 05 2025

A135755 a(n) = Sum_{k=0..n} C(n,k)3^[k(k-1)/2].

Original entry on oeis.org

1, 2, 6, 40, 860, 63000, 14714728, 10562062112, 22960880409360, 150300904214651680, 2955814683617734854752, 174481716707875308905153664, 30905247968182392588500030233024

Offset: 0

Paul D. Hanna, Nov 27 2007

nonn

G. C. Greubel, Table of n, a(n) for n = 0..49

Cf. variants: A006896, A135756.

Table[Sum[Binomial[n, k]*3^(Binomial[k, 2]), {k,0,n}], {n,0,10}] (* G. C. Greubel, Nov 07 2016 *)

{a(n)=sum(k=0,n,binomial(n,k)*3^(k*(k-1)/2))}

a(n) ~ 3^(n*(n-1)/2). - Vaclav Kotesovec, Nov 27 2017

A360604 Triangle read by rows. T(n, k) = 2^binomial(n - k, 2) * binomial(n - 1, k - 1).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 8, 6, 3, 1, 0, 64, 32, 12, 4, 1, 0, 1024, 320, 80, 20, 5, 1, 0, 32768, 6144, 960, 160, 30, 6, 1, 0, 2097152, 229376, 21504, 2240, 280, 42, 7, 1, 0, 268435456, 16777216, 917504, 57344, 4480, 448, 56, 8, 1

Offset: 0

Peter Luschny, Feb 23 2023

			Triangle T(n, k) starts:
[0] 1;
[1] 0,       1;
[2] 0,       1,      1;
[3] 0,       2,      2,     1;
[4] 0,       8,      6,     3,    1;
[5] 0,      64,     32,    12,    4,   1;
[6] 0,    1024,    320,    80,   20,   5,  1;
[7] 0,   32768,   6144,   960,  160,  30,  6, 1;
[8] 0, 2097152, 229376, 21504, 2240, 280, 42, 7, 1;

Cf. A006125 (column 1), A002378 (T(n+2,n)), A130809 (T(n+3,n)), A006896 (row sums).

T := (n, k) -> 2^binomial(n - k, 2) * binomial(n-1, k-1):
for n from 0 to 9 do seq(T(n, k), k = 0..n) od;

A167939 The number of connected subgraphs of the complete graph with n nodes.

Original entry on oeis.org

1, 3, 10, 64, 973, 31743, 2069970, 267270040, 68629753649, 35171000942707, 36024807353574290, 73784587576805254664, 302228602363365451957805, 2475873310144021668263093215, 40564787336902311168400640561098, 1329227697997490307154018925966130320

Offset: 1

Peter Divianszky (divip(AT)aszt.inf.elte.hu), Nov 15 2009

nonn

The problem originated from Attila Szabss.

			For n = 3, consider the complete graph with nodes A, B and C. a(3) = 10, the 10 connected subgraphs being: A, B, C, AB, AC, BC, AB+AC, AB+BC, AC+BC, AB+AC+BC.

G. C. Greubel, Table of n, a(n) for n = 1..80

Cf. A006125, A006896.

import Data.Function (fix)
import Data.List (transpose)
a :: [Integer]
a = scanl1 (+) . (!! 1) . transpose . fix $ map ((1:) . zipWith (*) (scanl1 (*) l) . zipWith poly (scanl1 (+) l)) . scanl (flip (:)) [] . zipWith (zipWith (*)) pascal where l = iterate (2*) 1
-- the Pascal triangle
pascal :: [[Integer]]
pascal = iterate (\l -> zipWith (+) (0: l) l) (1: repeat 0)
-- evaluate a polynomial at a given value
poly :: (Num a) => a -> [a] -> a
poly t = foldr (\e i -> e + t*i) 0

m:=35;
f:= func< x | (&+[2^Binomial(j,2)*x^j/Factorial(j): j in [0..m+2]]) >;
R:=PowerSeriesRing(Rationals(), m);
Coefficients(R!(Laplace( Exp(x)*Log(f(x)) ))); // G. C. Greubel, Sep 08 2023

nn = 25;
g[z_]:= Sum[2^Binomial[n, 2] z^n/n!, {n, 0, nn}];
Drop[CoefficientList[Series[Exp[z]*Log[g[z]], {z,0,nn}], z]*Range[0, nn]!, 1] (* Geoffrey Critzer, Nov 23 2016 *)

m=35
def f(x): return sum(2^binomial(j,2)*x^j/factorial(j) for j in range(m+3))
def A167939_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( exp(x)*log(f(x)) ).egf_to_ogf().list()
a=A167939_list(m); a[1:] # G. C. Greubel, Sep 08 2023

E.g.f.: exp(x)*log(A(x)) where A(x) is the e.g.f. for A006125. - Geoffrey Critzer, Nov 23 2016

cp's OEIS Frontend

A006897 a(n) is the number of hierarchical linear models on n unlabeled factors allowing 2-way interactions (but no higher order interactions); or the number of unlabeled simple graphs with <= n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A079265 Number of antisymmetric transitive binary relations on n unlabeled points.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A006898 a(n) = Sum_{k=0..n} C(n,k)*2^(k*(k+1)/2).

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A135756 a(n) = Sum_{k=0..n} C(n,k) * 2^(k*(k-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A004140 Number of nonempty labeled simple graphs on nodes chosen from an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A079263 Number of constrained mixed models with n factors.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A135755 a(n) = Sum_{k=0..n} C(n,k)*3^[k*(k-1)/2].

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A360604 Triangle read by rows. T(n, k) = 2^binomial(n - k, 2) * binomial(n - 1, k - 1).

A006898 a(n) = Sum_{k=0..n} C(n,k)2^(k(k+1)/2).

A135755 a(n) = Sum_{k=0..n} C(n,k)3^[k(k-1)/2].