A011266 -id:A011266 - cp's OEIS frontend

A134531 G.f.: Sum_{n>=0} a(n)x^n/(n!2^(n(n-1)/2)) = log( Sum_{n>=0} x^n/(n!2^(n*(n-1)/2)) ).

0, 1, -1, 5, -79, 3377, -362431, 93473345, -56272471039, 77442176448257, -239804482525402111, 1650172344732021412865, -24981899010711376986398719, 825164608171793476724052668417, -59053816996641612758331731690504191, 9102696765174239045811746247171452452865

Offset: 0

Paul D. Hanna, Oct 30 2007

			Let g.f. G(x) = Sum_{n>=0} a(n)*x^n/[ n! * 2^(n*(n-1)/2) ]
then exp(G(x)) = Sum_{n>=0} x^n/[ n! * 2^(n*(n-1)/2) ];
G.f.: G(x) = x - x^2/4 + 5x^3/48 - 79x^4/1536 + 3377x^5/122880 + ...
exp(G(x)) = 1 + x + x^2/4 + x^3/48 + x^4/1536 + x^5/122880 + ...

Seiichi Manyama, Table of n, a(n) for n = 0..77
Kimmo Berg, Complexity of solution structures in nonlinear pricing, Ann. Oper. Res. 206, 23-37 (2013).
Sergei Chmutov, Maxim Kazarian and Sergey Lando, Polynomial graph invariants and the KP hierarchy, arXiv:1803.09800 [math.CO], 2018.

Cf. related triangles: A134530, A111636.

Cf. A003025, A011266, A118197 (variant).

a[0] = 0;
a[n_] := a[n] = 1 - Sum[2^(k(n-k)) Binomial[n-1, k-1] a[k], {k, 1, n-1}];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jul 26 2018 *)

{a(n)=n!*2^(n*(n-1)/2)*polcoeff(log(sum(k=0,n,x^k/(k!*2^(k*(k-1)/2)))+x*O(x^n)),n)}

Equals column 0 of triangle A134530, which is the matrix log of triangle A111636, where A111636(n,k) = (2^k)^(n-k)*C(n,k).
From Peter Bala, Apr 01 2013: (Start)
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence (but with a different offset) is E(x)/E(2*x) = Sum_{n >= 0} a(n-1)*x^n/(n!*2^C(n,2)) = 1 - x + 5*x^2/(2!*2) - 79*x^3/(3!*2^3) + 3377*x^4/(4!*2^6) - ....
Recurrence equation:
a(n) = 1 - Sum_{k = 1..n-1} 2^(k*(n-k))*C(n-1,k-1)*a(k) with a(1) = 1. (End)
a(n) = (-1)^(n-1)*A003025(n)/n. - Andrew Howroyd, Jan 07 2022

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Original entry on oeis.org

1, 1, 5, 73, 2849, 277921, 65067905, 35545840513, 44384640206849, 124697899490480641, 778525887500557625345, 10693248499002776513697793, 320453350845793018626300755969, 20807125028666778079876193487790081, 2909872870574162514727072641529432735745

Offset: 0

Geoffrey Critzer, Apr 21 2020

nonn

Also 1 together with the row sums of A046860.

A binary relation R on [n] is periodic iff there is a d>=2 such that R^d = R. Let A be the class of non-arcless strongly connected periodic relations (A000629). Then a(n) is the number of binary relations on [n] whose strongly connected components are in A. - Geoffrey Critzer, Dec 12 2023

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

Cf. A046860, A322280, A011266, A361560, A003024, A365534, A365590.

b:= proc(n, k) option remember; `if`([n, k]=[0$2], 1,
      add(binomial(n, r)*2^(r*(n-r))*b(r, k-1), r=0..n-1))
    end:
a:= n-> add(b(n,k), k=0..n):
seq(a(n), n=0..15);  # Alois P. Heinz, Apr 21 2020

nn = 15; e2[x_] := Sum[x^n/(n! 2^Binomial[n, 2]), {n, 0, nn}];
Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/(1 - (e2[x] - 1)), {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(n!*2^C(n,2)) = 1/(2-Sum_{n>=0} x^n/(n!*2^C(n,2))).

A111636 Triangle read by rows: T(n,k) (0<=k<=n) is the number of labeled graphs having k blue nodes and n-k green ones and only nodes of different colors can be joined by an edge.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 12, 12, 1, 1, 32, 96, 32, 1, 1, 80, 640, 640, 80, 1, 1, 192, 3840, 10240, 3840, 192, 1, 1, 448, 21504, 143360, 143360, 21504, 448, 1, 1, 1024, 114688, 1835008, 4587520, 1835008, 114688, 1024, 1, 1, 2304, 589824, 22020096, 132120576, 132120576, 22020096, 589824, 2304, 1

Offset: 0

Emeric Deutsch, Aug 09 2005

Row sums yield A047863. T(2*n,n) = A111637(n). T(n,1) = A001787(n).

			T(2,1)=4 because we have B G, B--G, G B and G--B, where B (G) stands for a blue (green) node and -- denotes an edge.
Triangle starts:
  1;
  1,  1;
  1,  4,  1;
  1, 12, 12,  1;
  1, 32, 96, 32, 1;
  ...

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.

S. R. Finch, Bipartite, k-colorable and k-colored graphs
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
W. Wang and T. Wang, Generalized Riordan array, Discrete Mathematics, Vol. 308, No. 24, 6466-6500.

Cf. A047863, A111637, A001787.
Cf. A134530 (matrix log), A134531.
Cf. A000684, A011266, A038845, A140802, A224069 (matrix inverse).

T:=(n,k)->binomial(n,k)*2^(k*(n-k)): for n from 0 to 9 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

nn=6;f[x_,y_]:=Sum[Exp[x 2^n](y x)^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[Series[f[x,y],{x,0,nn}],{x,y}]//Grid (* Geoffrey Critzer, Sep 07 2013 *)

T(n, k)=2^[k(n-k)]*C(n, k).
Matrix log yields triangle A134530, where A134530(n,k) = A134531(n-k)*(2^k)^(n-k)*C(n,k). - Paul D. Hanna, Nov 11 2007
From Peter Bala, Aug 13 2012: (Start)
Let f(n) = n!*2^binomial(n,2) = A011266(n). Then T(n,k) = f(n)/(f(k)*f(n-k)).
E.g.f.: Sum_{n >= 0} exp(2^n*t*x)*x^n/n! = 1 + (1+t)*x + (1+4*t+t^2)*x^2/2! + ....
O.g.f.: Sum_{n >= 0} x^n/(1-2^n*t*x)^(n+1) = 1 + (1+t)*x + (1+4*t+t^2)*x^2 + .... O.g.f. for column k: 1/(1-2^k*x)^(k+1).
Recurrence equation: T(n,k) = 2^k*T(n-1,k) + 2^(n-k)*T(n-1,k-1).
Column k = 2: A038845. Column k = 3: A140802. Sum_{k = 0..n} k*T(n,k) = n*A000684(n). (End)
From Peter Bala, Apr 09 2013: (Start)
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function for this sequence is E(z)*E(x*z) = 1 + (1 + x)*z + (1 + 4*x + x^2)*z^2/(2!*2) + (1 + 12*x + 12*x^2 + x^3)*z^3/(3!*2^3) + .... Cf. Pascal's triangle A007318 with an e.g.f. of exp(z)*exp(x*z).
This is a generalized Riordan array (E(x), x) with respect to the sequence n!*2^C(n,2), as defined by Wang and Wang.
The n-th power of this triangle has a generating function E(z)^n*E(x*z). See A224069 for the inverse array (n = -1).
The n-th row is a log-concave sequence and hence unimodal.
The row polynomials satisfy the recurrence equation R(n+1,x) = 2^n*x*R(n,x/2) + R(n,2*x) with R(0,x) = 1, as well as R'(n,2*x) = n*2^(n-1)*R(n-1,x) (the ' denotes differentiation w.r.t. x). The row polynomials appear to have only real zeros.
Sum_{k = 0..n} (-1)^k*T(2*n+1,k) = 0;
Sum_{k = 0..n} (-1)^k*2^k*T(2*n,k) = 0;
Sum_{k = 0..n} 2^k*T(n,k) = A000684(n). (End)
T(n,k+1) = Product_{i=0..k} (T(n-i,1)/T(i+1,1)) for 0 <= k < n. - Werner Schulte, Nov 13 2018

A046860 Triangle giving a(n,k) = number of k-colored labeled graphs with n nodes.

Original entry on oeis.org

1, 1, 4, 1, 24, 48, 1, 160, 1152, 1536, 1, 1440, 30720, 122880, 122880, 1, 18304, 1152000, 10813440, 29491200, 23592960, 1, 330624, 65630208, 1348730880, 7707033600, 15854469120, 10569646080, 1, 8488960, 5858721792, 261070258176, 2853804441600, 11499774935040, 18940805775360, 10823317585920

Offset: 1

N. J. A. Sloane

			Triangle begins:
  1;
  1,     4;
  1,    24,      48;
  1,   160,    1152,     1536;
  1,  1440,   30720,   122880,   122880;
  1, 18304, 1152000, 10813440, 29491200, 23592960;
  ...

Alois P. Heinz, Rows n = 1..50, flattened
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.

Column #1 gives A000683.
Main diagonal gives A011266.
Row sums give A334282.
Cf. A000683, A006201, A006202.

a:= proc(n, k) option remember; `if`([n, k]=[0$2], 1,
      add(binomial(n, r)*2^(r*(n-r))*a(r, k-1), r=0..n-1))
    end:
seq(seq(a(n,k), k=1..n), n=1..8);  # Alois P. Heinz, Apr 21 2020

a[n_ /; n >= 1, k_ /; k >= 1] := a[n, k] = Sum[ Binomial[n, r]*2^(r*(n - r))*a[r, k - 1], {r, 1, n - 1}]; a[, 0] = 1; Flatten[ Table[ a[n, k], {n, 1, 8}, {k, 0, n - 1}]] (* _Jean-François Alcover, Dec 12 2011, after formula *)

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

1 + Sum_{n>=1} Sum_{k=1..n} a(n,k)*y^k*x^n/(n!*2^C(n,2)) = 1/(1-y(E(x)-1)) where E(x) = Sum_{n>=0} x^n/(n!*2^C(n,2)). - Geoffrey Critzer, May 06 2020

More terms from Vladeta Jovovic, Feb 04 2000

A086206 Number of n X n matrices with entries in {0,1} with no zero row and with zero main diagonal.

Original entry on oeis.org

0, 1, 27, 2401, 759375, 887503681, 3938980639167, 67675234241018881, 4558916353692287109375, 1213972926354344043087129601, 1284197945649659948122178573052927, 5412701932445852698371002894178179850241, 91054366938067173656011584805755385081787109375

Offset: 1

Vladeta Jovovic, Aug 27 2003

Equivalently a(n) is the number of labeled digraphs on [n] with no out-nodes. Cf. A362013. - Geoffrey Critzer, Apr 13 2023

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A055601, A086193, A092477, A362013.

a(n) = {(2^(n-1)-1)^n} \\ Andrew Howroyd, Jan 05 2020

a(n) = (2^(n-1)-1)^n = Sum_{k=0..n} (-1)^k*binomial(n, k)*2^((n-k)*(n-1)).
a(n) = A092477(n, n-1).
Sum_{n>=0} a(n)*x^n/A011266(n) = (Sum_{n>=0} (-x)^n/A011266(n))*(Sum_{n>=0} 2^(n(n-1))*x^n/A011266(n)). - Geoffrey Critzer, Apr 13 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 05 2020

A134530 Matrix log of triangle A111636, where A111636(n,k) = (2^k)^(n-k)*C(n,k) for n>=k>=0.

Original entry on oeis.org

0, 1, 0, -1, 4, 0, 5, -12, 12, 0, -79, 160, -96, 32, 0, 3377, -6320, 3200, -640, 80, 0, -362431, 648384, -303360, 51200, -3840, 192, 0, 93473345, -162369088, 72619008, -11325440, 716800, -21504, 448, 0, -56272471039, 95716705280, -41566486528, 6196822016, -362414080, 9175040, -114688, 1024, 0

Offset: 0

Paul D. Hanna, Oct 30 2007

			Triangle begins:
0,
1, 0;
-1, 4, 0;
5, -12, 12, 0;
-79, 160, -96, 32, 0;
3377, -6320, 3200, -640, 80, 0;
-362431, 648384, -303360, 51200, -3840, 192, 0;
93473345, -162369088, 72619008, -11325440, 716800, -21504, 448, 0; ...
Matrix exponentiation yields triangle A111636, which begins:
1;
1, 1;
1, 4, 1;
1, 12, 12, 1;
1, 32, 96, 32, 1;
1, 80, 640, 640, 80, 1; ...

Cf. A134531 (column 0); related triangles: A111636, A117401; A011266.

{T(n,k)=local(M=matrix(n+1,n+1,r,c,if(r>=c,2^((c-1)*(r-c))*binomial(r-1,c-1))),L); L=sum(i=1,#M,-(M^0-M)^i/i);L[n+1,k+1]}

T(n,k) = A134531(n-k)*(2^k)^(n-k)*C(n,k), where A134531 is column 0 and satisfies: G.f.: Sum_{n>=0} A134531(n)*x^n/[n!*2^(n*(n-1)/2)] = log(Sum_{n>=0}x^n/[n!*2^(n*(n-1)/2)]).

A197927 The number of isolated nodes in all labeled directed graphs (with self loops allowed) on n nodes.

Original entry on oeis.org

0, 1, 4, 48, 2048, 327680, 201326592, 481036337152, 4503599627370496, 166020696663385964544, 24178516392292583494123520, 13944156602510523416463735259136, 31901471898837980949691369446728269824, 289909687580898100839964337544428699577745408

Offset: 0

Geoffrey Critzer, Oct 19 2011

nonn

Here, isolated means indegree = outdegree = 0.

a(n) is also the number of directed graphs on [n] (no self loops allowed, A053763) with a distinguished vertex of indegree 0. - Geoffrey Critzer, Apr 01 2023

Cf. A011266, A053763, A002416.

a = Sum[2^(n^2)x^n/n!, {n,0,20}]; Range[0,12]! CoefficientList[Series[x a, {x,0,12}], x]

E.g.f.: x*A(x) where A(x) = Sum_{n>=0} 2^(n^2)*x^n/n!.
a(n) = n * 2^((n-1)^2) = n*A002416(n-1).
Sum_{n>=0} a(n)*z^n/B(n) = z*Sum_{n>=0} A053763(n)*z^n/B(n) where B(n) = n!*2^binomial(n,2). - Geoffrey Critzer, Apr 01 2023

A361560 Number of labeled digraphs on [n] all of whose strongly connected components are complete digraphs.

Original entry on oeis.org

1, 1, 4, 47, 1471, 115042, 21591817, 9455689609, 9464951556046, 21316993121024757, 106689322228222150243, 1174731578884501228621956, 28221161668500867009724237123, 1468937207982284446757761131062629, 164682046577167683717133576752582349216, 39562388056404531283767850863430043742371123

Offset: 0

Geoffrey Critzer, Mar 15 2023

nonn

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
Wikipedia, Strongly connected component

Cf. A011266 (all strong components are cycles), A361527, A003024 (all strong components are singletons).

nn = 15; B[n_] := n! 2^Binomial[n, 2]; a[x_] := Exp[x] - 1; Table[B[n], {n, 0, nn}] CoefficientList[Series[1/Normal[Series[Exp[-(Exp[x] - 1)], {x, 0, nn}]] /.
    Table[x^i -> z^i/2^Binomial[i, 2], {i, 0, nn}], {z, 0, nn}], z]

A361584 Number of digraphs on n unlabeled nodes whose strongly connected components are directed cycles or single vertices.

Original entry on oeis.org

1, 1, 3, 12, 88, 1239, 36540, 2226595, 277421616, 69974281748, 35535207035048, 36224521019293188, 74004483908461354689, 302712665772844097945072, 2477999475270966827490305948, 40583406022745170376459610683073, 1329552679157905406495248763876363056

Offset: 0

Andrew Howroyd, Mar 16 2023

nonn

The labeled version is A011266.

Cf. A350794, A361583, A361585 (without single vertex components).

A361584seq(16) \\ See PARI link in A350794 for program code.

a(n) >= A361583(n).

A381192 Irregular triangle read by rows. Properly color the vertices of a simple labeled graph on [n] using exactly n colors c_1=0, 0<=k<=binomial(n,2).

Original entry on oeis.org

1, 1, 3, 1, 21, 19, 7, 1, 315, 516, 419, 208, 65, 12, 1, 9765, 24186, 31445, 27488, 17538, 8420, 3050, 816, 153, 18, 1, 615195, 2080323, 3769767, 4754751, 4592847, 3555479, 2257723, 1188595, 519745, 187705, 55237, 12941, 2325, 301, 25, 1

Offset: 0

Geoffrey Critzer, Feb 16 2025

A descent in a labeled directed graph is an edge s->t such that s>t.
T(n,0) = A005329(n).
Sum_{k>=0} T(n,k)*k = A005329(n)*n(n-1)/8.

			     1;
     1;
     3,     1;
    21,    19,     7,     1;
   315,   516,   419,   208,    65,   12,   1;
  9765, 24186, 31445, 27488, 17538, 8420, 3050, 816, 153, 18, 1;
  ...

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020.

CF. A005329, A381058, A011266 (row sums), A381102.

nn = 6; B[n_] :=FunctionExpand[QFactorial[n, (1 + u y)/(1 + y)]] (1 + y)^Binomial[n, 2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}];Map[CoefficientList[#, u] &,Table[B[n], {n, 0, nn}] CoefficientList[Series[1/(1 - z), {z, 0, nn}], z] /. y -> 1] // Grid

cp's OEIS Frontend

A134531 G.f.: Sum_{n>=0} a(n)*x^n/(n!*2^(n*(n-1)/2)) = log( Sum_{n>=0} x^n/(n!*2^(n*(n-1)/2)) ).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A111636 Triangle read by rows: T(n,k) (0<=k<=n) is the number of labeled graphs having k blue nodes and n-k green ones and only nodes of different colors can be joined by an edge.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A046860 Triangle giving a(n,k) = number of k-colored labeled graphs with n nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A086206 Number of n X n matrices with entries in {0,1} with no zero row and with zero main diagonal.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A134530 Matrix log of triangle A111636, where A111636(n,k) = (2^k)^(n-k)*C(n,k) for n>=k>=0.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A197927 The number of isolated nodes in all labeled directed graphs (with self loops allowed) on n nodes.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A361560 Number of labeled digraphs on [n] all of whose strongly connected components are complete digraphs.

Views

Author

A134531 G.f.: Sum_{n>=0} a(n)x^n/(n!2^(n(n-1)/2)) = log( Sum_{n>=0} x^n/(n!2^(n*(n-1)/2)) ).