A111636 -id:A111636 - cp's OEIS frontend

A224069 Matrix inverse of A111636.

1, -1, 1, 3, -4, 1, -25, 36, -12, 1, 543, -800, 288, -32, 1, -29281, 43440, -16000, 1920, -80, 1, 3781503, -5621952, 2085120, -256000, 11520, -192, 1, -1138779265, 1694113344, -629658624, 77844480, -3584000, 64512, -448, 1, 783702329343, -1166109967360, 433693016064, -53730869248, 2491023360, -45875200, 344064, -1024, 1

Offset: 0

Peter Bala, Apr 09 2013

Let Q be the class of labeled directed acyclic graphs (dags) with some designated source nodes. Here, a source node is a node of indegree 0 and some means possibly all or none. |a(n,k)| is the number of dags in Q containing n nodes with exactly k designated source nodes. - Geoffrey Critzer, Apr 02 2023

			Triangle begins
n\k.|......0......1......2......3......4......5
= = = = = = = = = = = = = = = = = = = = = = = =
.0..|......1
.1..|.....-1......1
.2..|......3.....-4......1
.3..|....-25.....36....-12......1
.4..|....543...-800....288....-32......1
.5..|.-29281..43440.-16000...1920....-80......1
...
The sequence of zeros of R(10,x) begins 1, 3.280147..., 9.112469..., 23.366923..., 57.084317....
The sequence of zeros of R(20,x) begins 1, 3.280163..., 9.112696..., 23.369274..., 57.105379....

Vincenzo Librandi, Rows n = 0..50, flattened
W. Wang and T. Wang, Generalized Riordan array, Discrete Mathematics, Vol. 308, No. 24, 6466-6500, (2008).

Cf. A003024 (first column), A111636 (matrix inverse).

max = 8; A111636 = Table[ Binomial[n, k]*2^(k*(n - k)), {n, 0, max}, {k, 0, max}]; t = Inverse[ A111636 ]; Table[ t[[n, k]], {n, 1, max+1}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 10 2013 *)

T(n,k) = (-1)^(n-k)*A003024(n-k)*A111636(n,k) = (-1)^(n-k)*A003024(n-k)*2^(k*(n-k))*binomial(n,k).
Sum_{k = 1..n} k*2^k*T(n,k) = 0 for n >= 1.
Let E(x) = Sum_{n >= 0} x^n/(n!*2^binomial(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function for this triangle is E(x*z)/E(z) = 1 + (x - 1)*z + (x^2 - 4*x + 3)*z^2/(2!*2) + (x^3 - 12*x^2 + 36*x - 25)*z^3/(3!*2^3) + ....
This triangle is a generalized Riordan array (1/E(x), x) with respect to the sequence n!*2^C(n,2), as defined by Wang and Wang.
The row polynomials R(n,x) satisfy the recurrence equation R(n,x) = x^n - Sum_{k = 0..n-1} binomial(n,k)*2^(k*(n-k))*R(k,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 positive real zeros of multiplicity 1. Moreover, if r(n,1) < r(n,2) < ... < r(n,n) denotes the zeros of R(n,x) arranged in increasing order then it appears that lim_{n -> oo} r(n,i) exists for each fixed 1 <= i <= n. An example is given below.

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

A047863 Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

Original entry on oeis.org

1, 2, 6, 26, 162, 1442, 18306, 330626, 8488962, 309465602, 16011372546, 1174870185986, 122233833963522, 18023122242478082, 3765668654914699266, 1114515608405262434306, 467221312005126294077442, 277362415313453291571118082, 233150477220213193598856331266

Offset: 0

N. J. A. Sloane

Row sums of A111636. - Peter Bala, Sep 30 2012
Column 2 of Table 2 in Read. - Peter Bala, Apr 11 2013
It appears that 5 does not divide a(n), that a(n) is even for n>0, that 3 divides a(2n) for n>0, that 7 divides a(6n+5), and that 13 divides a(12n+3). - Ralf Stephan, May 18 2013

			For n=2, {1,2 black, not connected}, {1,2 white, not connected}, {1 black, 2 white, not connected}, {1 black, 2 white, connected}, {1 white, 2 black, not connected}, {1 white, 2 black, connected}.
G.f. = 1 + 2*x + 6*x^2 + 26*x^3 + 162*x^4 + 1442*x^5 + 18306*x^6 + ...

H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 79, Eq. 3.11.2.

T. D. Noe, Table of n, a(n) for n = 0..50
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
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]
A. Gainer-Dewar and I. M. Gessel, Enumeration of bipartite graphs and bipartite blocks, arXiv:1304.0139 [math.CO], 2013.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Martin Svatoš, Peter Jung, Jan Tóth, Yuyi Wang, and Ondřej Kuželka, On Discovering Interesting Combinatorial Integer Sequences, arXiv:2302.04606 [cs.LO], 2023, p. 17.
Eric Weisstein's World of Mathematics, k-Colorable Graph
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.

Column k=2 of A322280.
Cf. A135079 (variant).
Cf. A000683, A001831, A002031, A033995, A047864, A052332, A111636, A191371, A223887.

A047863:= func< n | (&+[Binomial(n,k)*2^(k*(n-k)): k in [0..n]]) >;
[A047863(n): n in [0..40]]; // G. C. Greubel, Nov 03 2024

Table[Sum[Binomial[n,k]2^(k(n-k)),{k,0,n}],{n,0,20}] (* Harvey P. Dale, May 09 2012 *)
nmax = 20; CoefficientList[Series[Sum[E^(2^k*x)*x^k/k!, {k, 0, nmax}], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 05 2019 *)

{a(n)=n!*polcoeff(sum(k=0,n,exp(2^k*x +x*O(x^n))*x^k/k!),n)} \\ Paul D. Hanna, Nov 27 2007

{a(n)=polcoeff(sum(k=0, n, x^k/(1-2^k*x +x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Mar 08 2008

N=66; x='x+O('x^N); egf = sum(n=0, N, exp(2^n*x)*x^n/n!);
Vec(serlaplace(egf))  \\ Joerg Arndt, May 04 2013

from sympy import binomial
def a(n): return sum([binomial(n, k)*2**(k*(n - k)) for k in range(n + 1)]) # Indranil Ghosh, Jun 03 2017

def A047863(n): return sum(binomial(n,k)*2^(k*(n-k)) for k in range(n+1))
[A047863(n) for n in range(41)] # G. C. Greubel, Nov 03 2024

a(n) = Sum_{k=0..n} binomial(n, k)*2^(k*(n-k)).
a(n) = 4 * A000683(n) + 2. - Vladeta Jovovic, Feb 02 2000
E.g.f.: Sum_{n>=0} exp(2^n*x)*x^n/n!. - Paul D. Hanna, Nov 27 2007
O.g.f.: Sum_{n>=0} x^n/(1 - 2^n*x)^(n+1). - Paul D. Hanna, Mar 08 2008
From Peter Bala, Apr 11 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 is E(x)^2 = 1 + 2*x + 6*x^2/(2!*2) + 26*x^3/(3!*2^3) + .... In general, E(x)^k, k = 1, 2, ..., is a generating function for labeled k-colored graphs (see Stanley). For other examples see A191371 (k = 3) and A223887 (k = 4).
If A(x) = 1 + 2*x + 6*x^2/2! + 26*x^3/3! + ... denotes the e.g.f. for this sequence then sqrt(A(x)) = 1 + x + 2*x^2/2! + 7*x^3/3! + ... is the e.g.f. for A047864, which counts labeled 2-colorable graphs. (End)
a(n) ~ c * 2^(n^2/4+n+1/2)/sqrt(Pi*n), where c = Sum_{k = -infinity..infinity} 2^(-k^2) = EllipticTheta[3, 0, 1/2] = 2.128936827211877... if n is even and c = Sum_{k = -infinity..infinity} 2^(-(k+1/2)^2) = EllipticTheta[2, 0, 1/2] = 2.12893125051302... if n is odd. - Vaclav Kotesovec, Jun 24 2013

Better description from Christian G. Bower, Dec 15 1999

A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

Original entry on oeis.org

1, 3, 13, 81, 721, 9153, 165313, 4244481, 154732801, 8005686273, 587435092993, 61116916981761, 9011561121239041, 1882834327457349633, 557257804202631217153, 233610656002563147038721, 138681207656726645785559041

Offset: 1

N. J. A. Sloane

a(n) = A058872(n) + 1. This sequence counts the empty graph on n nodes which is not allowed in A058872. - Geoffrey Critzer, Oct 07 2012

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..100 (first 32 terms from R. W. Robinson)
S. R. Finch, Bipartite, k-colorable and k-colored graphs (2*A000684)
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
A. Nymeyer and R. W. Robinson, Tabulation of the Numbers of Labeled Bipartite Blocks and Related Classes of Bicolored Graphs, 1982 [Annotated scanned copy of unpublished MS and letter from R.W.R.]
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976

2 * A000683(n) + 1.

Cf. A058872, A111636, A134531.

With[{nn=20},Rest[CoefficientList[Series[Sum[x^n/(1-2^n x)^n,{n,nn}],{x,0,nn}], x]]] (* Harvey P. Dale, Nov 24 2011 *)

a(n)=polcoeff(sum(k=1,n,x^k/(1-2^k*x +x*O(x^n))^k),n) \\ Paul D. Hanna, Sep 14 2009

G.f.: A(x) = Sum_{n>=1} x^n/(1 - 2^n*x)^n. - Paul D. Hanna, Sep 14 2009
G.f.: 1/(W(0)-x) where W(k) = x*(x*2^k-1)^k - (x*2^(k+1)-1)^(k+1) + x*((2*x*2^k-1)^(2*k+2))/W(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 17 2012
From Peter Bala, Apr 01 2013: (Start)
a(n) = Sum_{k = 0..n-1} binomial(n-1,k)*2^(k*(n-k)).
a(n) = Sum_{k = 0..n} 2^k*A111636(n,k).
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence (but with an offset of 0) is E(x)*E(2*x) = Sum_{n >= 0} a(n+1)*x^n/(n!*2^C(n,2)) = 1 + 3*x + 13*x^2/(2!*2) + 81*x^3/(3!*2^3) + 721*x^4/(4!*2^6) + .... Cf. A134531. (End)

a(15) onwards added by N. J. A. Sloane, Oct 19 2006 from the Robinson reference

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

Original entry on oeis.org

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

A381058 Irregular triangular array read by rows. Let S_n be the set of labeled graphs G on [n] with 2-colored nodes where black nodes are only connected to white nodes and vice versa. Orient the edges in each such graph G from black to white. T(n,k) is the number of graphs in S_n containing exactly k descents, n>=0, 0<=k<=A002620(n).

Original entry on oeis.org

1, 2, 5, 1, 16, 8, 2, 67, 56, 30, 8, 1, 374, 436, 358, 188, 68, 16, 2, 2825, 4143, 4508, 3460, 2032, 924, 320, 80, 13, 1, 29212, 50460, 66976, 66092, 52412, 34280, 18630, 8376, 3072, 892, 194, 28, 2, 417199, 811790, 1246486, 1471358, 1436404, 1195166, 859650, 537750, 292880, 138280, 56048, 19168, 5382, 1188, 192, 20, 1

Offset: 0

Geoffrey Critzer, Feb 12 2025

A descent in a labeled directed graph is an edge s->t such that s>t.

T(n,0) = A006116(n).

			    1;
    2;
    5,    1;
   16,    8,    2;
   67,   56,   30,    8,    1;
  374,  436,  358,  188,   68,  16,   2;
 2825, 4143, 4508, 3460, 2032, 924, 320, 80, 13, 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. A228890, A047863 (row sums), A006116, A111636, A381102, A381192.

nn = 7; 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[e[z]^2, {z, 0, nn}],z] /. y -> 1] // Grid

A111637 Number of labeled graphs having n blue nodes and n green ones, where edges join only nodes of different colors.

Original entry on oeis.org

1, 4, 96, 10240, 4587520, 8455716864, 63496796504064, 1932044240141942784, 237409596228641929297920, 117555946699326540948428554240, 234206054295766751302924897412448256, 1875359927045089548108556844295368069873664

Offset: 0

Emeric Deutsch, Aug 09 2005

nonn

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

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

Cf. A111636, A000984, A002416.

a:= n-> 2^(n^2)*binomial(2*n,n): seq(a(n),n=0..12);

a(n) = C(2n,n) * 2^(n^2).
a(n) = A000984(n) * A002416(n).
a(n) = A111636(2n,n).

cp's OEIS Frontend

A224069 Matrix inverse of A111636.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A047863 Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Python

SageMath

Formula

Extensions

A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A111637 Number of labeled graphs having n blue nodes and n green ones, where edges join only nodes of different colors.

Views

Author

Keywords

Examples

References

Crossrefs

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