A134531 -id:A134531 - cp's OEIS frontend

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

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

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Original entry on oeis.org

1, 2, 15, 316, 16885, 2174586, 654313415, 450179768312, 696979588034313, 2398044825254021110, 18151895792052235541515, 299782788128536523836784628, 10727139906233315197412684689421

Offset: 1

N. J. A. Sloane

nonn

From Gus Wiseman, Jan 02 2024: (Start)
Also the number of n-element sets of finite nonempty subsets of {1..n}, including a unique singleton, such that there is exactly one way to choose a different element from each. For example, the a(0) = 0 through a(3) = 15 set-systems are:
  .  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,3}}
            {{2},{1,2}}  {{1},{1,2},{2,3}}
                         {{1},{1,3},{2,3}}
                         {{2},{1,2},{1,3}}
                         {{2},{1,2},{2,3}}
                         {{2},{1,3},{2,3}}
                         {{3},{1,2},{1,3}}
                         {{3},{1,2},{2,3}}
                         {{3},{1,3},{2,3}}
                         {{1},{1,2},{1,2,3}}
                         {{1},{1,3},{1,2,3}}
                         {{2},{1,2},{1,2,3}}
                         {{2},{2,3},{1,2,3}}
                         {{3},{1,3},{1,2,3}}
                         {{3},{2,3},{1,2,3}}
These set-systems are all connected.
The case of labeled graphs is A000169.
(End)

			a(2) = 2: o-->--o (2 ways)
a(3) = 15: o-->--o-->--o (6 ways) and
o ... o o-->--o
.\ . / . \ . /
. v v ... v v
.. o ..... o
(3 ways) (6 ways)

R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

A diagonal of A058876.
Row sums of A350487.
The unlabeled version is A350415.
Column k=1 of A361718.
Cf. A003026, A003028, A345258.
For any number of sinks we have A003024, unlabeled A003087.
For n-1 sinks we have A058877.
For a fixed sink we have A134531 (up to sign), column k=1 of A368602.
Cf. A000169, A058891, A059201, A082402, A088957, A323818, A334282, A367904, A368600, A368601.

Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Count[#,{}]==1&&Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,4}] (* _Gus Wiseman, Jan 02 2024 *)

\\ requires A058876.
my(T=A058876(20)); vector(#T, n, T[n][1]) \\ Andrew Howroyd, Dec 27 2021

\\ see Marcel et al. link (formula for a').
seq(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1) * binomial(n,k) * (2^(n-k)-1)^k * a[n-k])); a} \\ Andrew Howroyd, Jan 01 2022

a(n) = (-1)^(n-1) * n * A134531(n). - Gus Wiseman, Jan 02 2024

More terms from Vladeta Jovovic, Apr 10 2001

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

A118197 Column 0 of the matrix log of triangle A117401, after term in row n is multiplied by n: a(n) = n[log(A117401)](n,0), where A117401(n,k) = 2^(k(n-k)).

Original entry on oeis.org

0, 1, 0, -1, 4, -11, -186, 10823, -492536, 5125897, 10381552650, -6405856963573, 3302055158456332, 2338316177882689549, -30991279275364493410290, 224870687441604081662836751, -1045565401111374322223949545456, -50507259999091315834370754855632879

Offset: 0

Paul D. Hanna, Apr 15 2006, Oct 30 2007

sign

The entire matrix log of triangle A117401 is determined by column 0 (this sequence): [log(A117401)](n,k) = a(n-k)*2^(k*(n-k))/(n-k) for n>k>=0.

			Column 0 of log(A117401) = [0, 1, 0, -1/3, 4/4, -11/5, -186/6, ...] and
consists of terms a(n)/n (n>0); these terms are integers at n = [0, 1, 2, 4, 6, 8, 10, 14, 16, 22, 26, 32, 34, 38, 46, 50, 58, 62, 64, 70, ...].
The g.f. is illustrated by:
x/(1-x)^2 = x + 2*x^2 + 3*x^3 + 4*x^4 + 5*x^5 + 6*x^6 +... = x/(1-2*x) - 0*x^2/(1-4*x) - 1*x^3/(1-8*x) + 4*x^4/(1-16*x) - 11*x^5/(1-32*x) - 186*x^6/(1-64*x) + 10823*x^7/(1-128*x) + ...
Define g.f.: G(x) = Sum_{n>=1} a(n)*x^n/[n * 2^(n(n-1)/2)], then G(x) = x + 0*x^2/4 - x^3/24 + 4*x^4/256 - 11*x^5/5120 - 186*x^6/196608 + ... and exp(G(x)) = 1 + x + x^2/2 + x^3/8 + x^4/64 + x^5/1024 + x^6/32768 + ...

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

Cf. A117401, A118196, A134531.

A118196[n_]:= A118196[n]= If[n<2, (-1)^n, -Sum[2^(j*(n-j))*A118196[j], {j, 0, n-1}]];
a[n_]:= a[n]= -Sum[2^(j*(n-j))*j*A118196[j], {j, 0, n}];
Table[a[n], {n, 0, 30}] (* G. C. Greubel, Jun 30 2021 *)

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

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

@CachedFunction
def A118196(n): return (-1)^n if (n<2) else -sum(2^(j*(n-j))*A118196(j) for j in (0..n-1))
def a(n): return (-1)*sum(2^(j*(n-j))*j*A118196(j) for j in (0..n))
[a(n) for n in (0..30)] # G. C. Greubel, Jun 30 2021

G.f.: x/(1-x)^2 = Sum_{n>=0} a(n)*x^n/(1-2^n*x).
By using the inverse transformation: a(n) = Sum_{k=0..n} k*A118196(n-k)*2^(k*(n-k)) for n>=0.
a(2^n) is divisible by 2^n.
G.f.: Sum_{n>=1} a(n)*x^n/[n*2^(n(n-1)/2)] = log(Sum_{n>=0} x^n/2^[n(n-1)/2]).

A219765 Triangle of coefficients of a polynomial sequence related to the coloring of labeled graphs.

Original entry on oeis.org

1, 0, 1, 0, -1, 2, 0, 5, -12, 8, 0, -79, 208, -192, 64, 0, 3377, -9520, 10240, -5120, 1024, 0, -362431, 1079744, -1282560, 778240, -245760, 32768, 0, 93473345, -291615296, 372893696, -255754240, 100925440, -22020096, 2097152, 0, -56272471039, 182582658048, -247557029888, 185511968768, -84263567360, 23488102400, -3758096384, 268435456

Offset: 0

Peter Bala, Apr 16 2013

A simple graph G is a k-colorable graph if it is possible to assign one of k' <= k colors to each vertex of G so that no two adjacent vertices receive the same color. Such an assignment of colors is called a k-coloring function for the graph. The chromatic polynomial P(G,k) of a simple graph G gives the number of different k-colorings functions of the graph as a function of k. P(G,k) is a polynomial function of k.

The row polynomials R(n,x) of this triangle are defined to be the sum of the chromatic polynomials of all labeled simple graphs on n vertices: R(n,x) = sum {labeled graphs G on n nodes} P(G,x). An example is given below.

			Triangle begins:
  n\k.|..0.....1......2.......3......4.......5
  = = = = = = = = = = = = = = = = = = = = = = =
  .0..|..1
  .1..|..0.....1
  .2..|..0....-1......2
  .3..|..0.....5....-12.......8
  .4..|..0...-79....208....-192.....64
  .5..|..0..3377..-9520...10240..-5120....1024
  ...
Row 3 = [5, -12, 8]: There are 4 unlabeled graphs on 3 vertices, namely
(a)  o    o    o    (b)  o    o----o    (c)  o----o----o
(d)   0
     / \
    0---0
with chromatic polynomials x^3, x^2*(x-1), x*(x-1)^2 and (x-1)^3 - (x-1), respectively. Allowing for labeling, there is 1 labeled graph of type (a), 3 labeled graphs of type (b), 3 labeled graphs of type (c) and 1 labeled graph of type (d). Thus the sum of the chromatic polynomials over all labeled graphs on 3 nodes is x^3 + 3*x^2*(x-1) + 3*x*(x-1)^2  + (x-1)^3 - (x-1) = 5*x - 12*x^2 + 8*x^3.
Row 3 of A058843 is [1,12,8]. Thus R(3,x) = x + 12*x*(x-1) + 8*x*(x-1)*(x-2) = 5*x - 12*x^2 + 8*x^3.

Alois P. Heinz, Rows n = 0..77, flattened
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Exponential structures
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.
Wikipedia, Graph coloring

Cf. A003024 (alt. row sums), A006125 (main diagonal), A095351 (main subdiagonal), A134531 (column 1), A058843, A322280.

R:= proc(n) option remember; `if`(n=0, 1, expand(x*add(
      binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1)))
    end:
T:= n-> (p-> seq(coeff(p,x,i), i=0..degree(p)))(R(n)):
seq(T(n), n=0..10);  # Alois P. Heinz, May 16 2024

r[0] = 1; r[1] = x; r[n_] := r[n] = x*Sum[ Binomial[n-1, k]*2^(k*(n-k))*(r[k] /. x -> x-1), {k, 0, n-1}]; row[n_] := CoefficientList[ r[n], x]; Table[ row[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Apr 17 2013 *)

Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function for the triangle is E(z)^x = Sum_{n >= 0} R(n,x)*z^n/(n!*2^C(n,2)) = 1 + x*z + (-x + 2*x^2)*z^2/(2!*2) + (5*x - 12*x^2 + 8*x^3)*z^3/(3!*2^3) + ....
The row polynomials satisfy the recurrence equation: R(0,x) = 1 and
R(n+1,x) = x*Sum_{k = 0..n} binomial(n,k)*2^(k*(n+1-k))*R(k,x-1).
In terms of the basis of falling factorial polynomials we have, for n >= 1, R(n,x) = Sum_{k = 1..n} A058843(n,k)*x*(x-1)*...*(x-k+1).
The polynomials R(n,x)/2^comb(n,2) form a sequence of binomial type (see Stanley). Setting D = d/dx, the associated delta operator begins D + D^2/(2!*2) + D^3/(3!*2^3) - D^4/(4!*2^4) + 23*D^5/(5!*2^5) + 559*D^6/(6!*2^6) - ... obtained by series reversion of the formal series D - D^2/(2!*2) + 5*D^3/(3!*2^3) - 79*D^4/(4!*2^4) + 3377*D^5/(5!*2^5) - ... coming from column 1 of the triangle.
Alternating row sums A003024. Column 1 = A134531. Main diagonal A006125. Main subdiagonal (-1)*A095351.
The row polynomials evaluated at k is A322280(n,k). - Geoffrey Critzer, Mar 02 2024
Let k>=1 and let D be a directed acyclic graph with vertices labeled on [n].  Then (-1)^n*R(n,-k) is the number of maps C:[n]->[k] such that for all vertices i,j in [n], if i is directed to j in D then C(i)>=C(j).  Cf A003024 (k=1), A339934 (k=2). - Geoffrey Critzer, May 15 2024

A361718 Triangular array read by rows. T(n,k) is the number of labeled directed acyclic graphs on [n] with exactly k nodes of indegree 0.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 15, 9, 1, 0, 316, 198, 28, 1, 0, 16885, 10710, 1610, 75, 1, 0, 2174586, 1384335, 211820, 10575, 186, 1, 0, 654313415, 416990763, 64144675, 3268125, 61845, 441, 1, 0, 450179768312, 286992935964, 44218682312, 2266772550, 43832264, 336924, 1016, 1

Offset: 0

Geoffrey Critzer, Apr 02 2023

Also the number of sets of n nonempty subsets of {1..n}, k of which are singletons, such that there is only one way to choose a different element from each. For example, row n = 3 counts the following set-systems:
  {{1},{1,2},{1,3}}    {{1},{2},{1,3}}    {{1},{2},{3}}
  {{1},{1,2},{2,3}}    {{1},{2},{2,3}}
  {{1},{1,3},{2,3}}    {{1},{3},{1,2}}
  {{2},{1,2},{1,3}}    {{1},{3},{2,3}}
  {{2},{1,2},{2,3}}    {{2},{3},{1,2}}
  {{2},{1,3},{2,3}}    {{2},{3},{1,3}}
  {{3},{1,2},{1,3}}    {{1},{2},{1,2,3}}
  {{3},{1,2},{2,3}}    {{1},{3},{1,2,3}}
  {{3},{1,3},{2,3}}    {{2},{3},{1,2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{1,3},{1,2,3}}
  {{2},{1,2},{1,2,3}}
  {{2},{2,3},{1,2,3}}
  {{3},{1,3},{1,2,3}}
  {{3},{2,3},{1,2,3}}

			Triangle begins:
  1;
  0,     1;
  0,     2,     1;
  0,    15,     9,    1;
  0,   316,   198,   28,  1;
  0, 16885, 10710, 1610, 75, 1;
  ...

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.

Cf. A058876 (mirror), A361579, A224069.
Row-sums are A003024, unlabeled A003087.
Column k = 1 is A003025(n) = |n*A134531(n)|.
Column k = n-1 is A058877.
For fixed sinks we get A368602.
A058891 counts set-systems, unlabeled A000612.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A000169, A059201, A082402, A088957, A133686, A334282, A350415, A367904, A367908, A368600, A368601.

nn = 8; B[n_] := n! 2^Binomial[n, 2] ;ggf[egf_] := Normal[Series[egf, {z, 0, nn}]] /. Table[z^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[ Series[ggf[Exp[(u - 1) z]]/ggf[Exp[-z]], {z, 0, nn}], {z, u}])[[i]], i], {i, 1, nn + 1}] // Grid
nv=4;Table[Length[Select[Subsets[Subsets[Range[n]],{n}], Count[#,{_}]==k&&Length[Select[Tuples[#], UnsameQ@@#&]]==1&]],{n,0,nv},{k,0,n}]

T(n,k) = A368602(n,k) * binomial(n,k). - Gus Wiseman, Jan 03 2024

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

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

Original entry on oeis.org

0, 1, -2, 28, -1808, 469072, -456745472, 1601325615808, -19650153075181568, 826737899840505194752, -117393483573257494026125312, 55564698792825562646890851908608, -86789641569440259960965030826164092928

Offset: 0

Seiichi Manyama, Jun 18 2022

sign

Cf. A134531, A355071.

Cf. A188457, A355073.

a(n) = n!*3^(n*(n-1)/2)*polcoef(log(sum(k=0, n, x^k/(k!*3^(k*(k-1)/2)))+x*O(x^n)), n);

a_vector(n) = my(v=vector(n+1)); v[1]=0; for(i=1, n, v[i+1]=1-sum(j=1, i-1, 3^(j*(i-j))*binomial(i-1, j)*v[i-j+1])); v;

a(0) = 0; a(n) = 1 - Sum_{k=1..n-1} 3^(k*(n-k)) * binomial(n-1,k) * a(n-k).

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

Original entry on oeis.org

0, 1, -3, 81, -13311, 11688705, -51334027263, 1082183686000641, -106464672910860746751, 47880898685034024043741185, -96901748928702482338511172665343, 871602415363671863767026450797790494721

Offset: 0

Seiichi Manyama, Jun 18 2022

sign

Cf. A134531, A355070.

Cf. A137435, A355074.

a(n) = n!*4^(n*(n-1)/2)*polcoef(log(sum(k=0, n, x^k/(k!*4^(k*(k-1)/2)))+x*O(x^n)), n);

a_vector(n) = my(v=vector(n+1)); v[1]=0; for(i=1, n, v[i+1]=1-sum(j=1, i-1, 4^(j*(i-j))*binomial(i-1, j)*v[i-j+1])); v;

a(0) = 0; a(n) = 1 - Sum_{k=1..n-1} 4^(k*(n-k)) * binomial(n-1,k) * a(n-k).

A368602 Triangle read by rows where T(n,k) is the number of labeled acyclic digraphs on {1..n} with sinks {1..k}.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 5, 3, 1, 0, 79, 33, 7, 1, 0, 3377, 1071, 161, 15, 1, 0, 362431, 92289, 10591, 705, 31, 1, 0, 93473345, 19856703, 1832705, 93375, 2945, 63, 1, 0, 56272471039, 10249747713, 789619327, 32382465, 782719, 12033, 127, 1

Offset: 0

Gus Wiseman, Jan 02 2024

Also the number of set-systems with n vertices and n edges such that {i} is a singleton edge iff i <= k, and such that there is only one way to choose a different vertex from each edge.

			Triangle begins:
    1
    0    1
    0    1    1
    0    5    3    1
    0   79   33    7    1
    0 3377 1071  161   15    1
    ...
Row n = 3 counts the following set-systems:
  {{1},{1,2},{1,3}}    {{1},{2},{1,3}}    {{1},{2},{3}}
  {{1},{1,2},{2,3}}    {{1},{2},{2,3}}
  {{1},{1,3},{2,3}}    {{1},{2},{1,2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{1,3},{1,2,3}}

Column k = n-1 is A000225 = A058877(n)/n.
Column k = 1 is A134531 (up to sign) or A003025(n)/n, non-fixed A350415.
For any choice of k sinks we get A361718.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A000169, A003024, A003087, A082402, A088957, A334282, A367862, A367904, A367908, A368600, A368601.

Table[Length[Select[Subsets[Subsets[Range[n]],{n}], Union@@Cases[#,{_}]==Range[k] && Length[Select[Tuples[#],UnsameQ@@#&]]==1&]], {n,0,3},{k,0,n}]

T(n,k) = A361718(n,k)/binomial(n,k).

More terms from Alois P. Heinz, Jan 04 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

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

A118197 Column 0 of the matrix log of triangle A117401, after term in row n is multiplied by n: a(n) = n*[log(A117401)](n,0), where A117401(n,k) = 2^(k*(n-k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Sage

Formula

A219765 Triangle of coefficients of a polynomial sequence related to the coloring of labeled graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A361718 Triangular array read by rows. T(n,k) is the number of labeled directed acyclic graphs on [n] with exactly k nodes of indegree 0.

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.

A118197 Column 0 of the matrix log of triangle A117401, after term in row n is multiplied by n: a(n) = n[log(A117401)](n,0), where A117401(n,k) = 2^(k(n-k)).

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

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