A121251 -id:A121251 - cp's OEIS frontend

A372175 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with exactly 2k directed cycles of length > 2.

1, 0, 1, 3, 1, 19, 15, 0, 6, 0, 0, 0, 1, 155, 232, 15, 190, 0, 0, 70, 50, 0, 0, 0, 0, 30, 15, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 24 2024

A directed cycle in a simple (undirected) graph is a sequence of distinct vertices, up to rotation, such that there are edges between all consecutive elements, including the last and the first.

			Triangle begins (zeros shown as dots):
  1
  .
  1
  3 1
  19 15 . 6 ... 1
  155 232 15 190 .. 70 50 .... 30 15 .......... 10 .............. 1
Row n = 4 counts the following graphs:
  12,34     12,13,14,23  .  12,13,14,23,24  .  .  .  12,13,14,23,24,34
  13,24     12,13,14,24     12,13,14,23,34
  14,23     12,13,14,34     12,13,14,24,34
  12,13,14  12,13,23,24     12,13,23,24,34
  12,13,24  12,13,23,34     12,14,23,24,34
  12,13,34  12,13,24,34     13,14,23,24,34
  12,14,23  12,14,23,24
  12,14,34  12,14,23,34
  12,23,24  12,14,24,34
  12,23,34  12,23,24,34
  12,24,34  13,14,23,24
  13,14,23  13,14,23,34
  13,14,24  13,14,24,34
  13,23,24  13,23,24,34
  13,23,34  14,23,24,34
  13,24,34
  14,23,24
  14,23,34
  14,24,34

Row lengths are A002807 + 1.
Row sums are A006129, unlabeled A002494.
Column k = 0 is A105784 (for triangles A372168, non-covering A213434), unlabeled A144958 (for triangles A372169).
Counting triangles instead of cycles gives A372167 (non-covering A372170), unlabeled A372173 (non-covering A263340).
The non-covering version is A372176.
Column k = 1 is A372195 (non-covering A372193, for triangles A372171), unlabeled A372191 (non-covering A236570, for triangles A372174).
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000272, A053530, A121251, A137916, A137917, A372172, A372194.

cycles[g_]:=Join@@Table[Select[Join@@Permutations /@ Subsets[Union@@g,{k}],Min@@#==First[#]&&And@@Table[MemberQ[Sort/@g,Sort[{#[[i]], #[[If[i==k,1,i+1]]]}]],{i,k}]&],{k,3,Length[g]}];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[cycles[#]]==2k&]], {n,0,5},{k,0,Length[cycles[Subsets[Range[n],{2}]]]/2}]

A173219 G.f.: A(x) = Sum_{n>=0} (1 + x)^(n(n+1)/2) / 2^(n+1).

Original entry on oeis.org

1, 2, 12, 124, 1800, 33648, 769336, 20796960, 648841680, 22945907520, 907036108432, 39631833652320, 1896696894062880, 98669609894805600, 5543804125505195040, 334563594743197602272, 21583554094995765302592

Offset: 0

Paul D. Hanna, Mar 05 2010

nonn

a(n) is the number of nonnegative integer matrices with n distinct columns and any number of nonzero rows with 2 ones in every column and columns in decreasing lexicographic order. - Andrew Howroyd, Jan 15 2020

Andrew Howroyd, Table of n, a(n) for n = 0..100

Row n=2 of A331278.

Cf. A121251, A173217, A173218.

Table[Sum[StirlingS1[n, j] * Sum[Binomial[j, s]*HurwitzLerchPhi[1/2, -j - s, 0], {s, 0, j}] / 2^(j+1), {j, 0, n}] / n!, {n, 0, 20}] (* Vaclav Kotesovec, Oct 08 2019 *)

{a(n)=local(A=sum(m=0,n^2+100,(1+x +O(x^(n+2)))^(m*(m+1)/2)/2^(m+1)));round(polcoeff(A,n))}

a(n) = A265937(n)/2. - Vaclav Kotesovec, Oct 08 2019
a(n) ~ 2^n * n^n / (2^(log(2)/4) * log(2)^(2*n+1) * exp(n)). - Vaclav Kotesovec, Oct 08 2019
a(n) = 2*A121251(n) for n > 0. - Andrew Howroyd, Jan 15 2020

A331277 Array read by antidiagonals: A(n,k) is the number of binary matrices with k distinct columns and any number of nonzero rows with n ones in every column and columns in decreasing lexicographic order.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 6, 1, 1, 0, 1, 62, 31, 1, 1, 0, 1, 900, 2649, 160, 1, 1, 0, 1, 16824, 441061, 116360, 841, 1, 1, 0, 1, 384668, 121105865, 231173330, 5364701, 4494, 1, 1, 0, 1, 10398480, 49615422851, 974787170226, 131147294251, 256452714, 24319, 1, 1

Offset: 0

Andrew Howroyd, Jan 13 2020

The condition that the columns be in decreasing order is equivalent to considering nonequivalent matrices with distinct columns up to permutation of columns.

A(n,k) is the number of labeled n-uniform hypergraphs with k edges and no isolated vertices. When n=2 these objects are graphs.

			Array begins:
====================================================================
n\k | 0 1    2         3              4            5           6
----+---------------------------------------------------------------
  0 | 1 1    0         0              0            0           0 ...
  1 | 1 1    1         1              1            1           1 ...
  2 | 1 1    6        62            900        16824      384668 ...
  3 | 1 1   31      2649         441061    121105865 49615422851 ...
  4 | 1 1  160    116360      231173330 974787170226 ...
  5 | 1 1  841   5364701   131147294251 ...
  6 | 1 1 4494 256452714 78649359753286 ...
  ...
The A(2,2) = 6 matrices are:
   [1 0]  [1 0]  [1 0]  [1 1]  [1 0]  [1 0]
   [1 0]  [0 1]  [0 1]  [1 0]  [1 1]  [0 1]
   [0 1]  [1 0]  [0 1]  [0 1]  [0 1]  [1 1]
   [0 1]  [0 1]  [1 0]

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Rows n=1..3 are A000012, A121251, A136245.
Columns k=0..3 are A000012, A000012, A047665, A137219.
The version with nonnegative integer entries is A331278.
The version with not necessarily distinct columns is A330942.
Cf. A262809 (unrestricted version), A331315, A331639.

T(n,k)={my(m=n*k); sum(j=0, m, binomial(binomial(j,n), k)*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))}

A(n, k) = Sum_{j=0..n*k} binomial(binomial(j,n),k) * (Sum_{i=j..n*k} (-1)^(i-j)*binomial(i,j)).
A(n, k) = Sum_{j=0..k} Stirling1(k, j)*A262809(n, j)/k!.
A(n, k) = Sum_{j=0..k} (-1)^(k-j)*binomial(k-1, k-j)*A330942(n, j).
A331639(n) = Sum_{d|n} A(n/d, d).

A121316 Unlabeled version of A055203: number of different relations between n intervals (of nonzero length) on a line, up to permutation of intervals.

Original entry on oeis.org

1, 1, 7, 75, 1105, 20821, 478439, 12977815, 405909913, 14382249193, 569377926495, 24908595049347, 1193272108866953, 62128556769033261, 3493232664307133871, 210943871609662171055, 13615857409567572389361, 935523911378273899335537

Offset: 0

Goran Kilibarda and Vladeta Jovovic, Aug 25 2006

nonn

Also number of labeled multigraphs without isolated vertices and with n edges.

Nathaniel Johnston, Table of n, a(n) for n = 0..125
A. N. Bhavale, B. N. Waphare, Basic retracts and counting of lattices, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.

Row n=2 of A330942.

Cf. A055203, A121251, A104209.

seq(sum(binomial(k*(k-1)/2+n-1,n)/2^(k+1),k=0..infinity),n=0..20);
with(combinat): A121316:=proc(n) return (1/n!)*add(abs(stirling1(n,k))*A055203(k),k=0..n): end: seq(A121316(n),n=0..20); # Nathaniel Johnston, Apr 28 2011

Table[Sum[Binomial[k*(k-1)/2+n-1,n]/2^(k+1),{k,0,Infinity}],{n,0,20}] (* Vaclav Kotesovec, Mar 15 2014 *)

a(n) = {sum(j=0, 2*n, binomial(binomial(j,2)+n-1, n) * sum(i=j, 2*n, (-1)^(i-j)*binomial(i,j)))} \\ Andrew Howroyd, Feb 09 2020

a(n) = (1/n!)* Sum_{k=0..n} |Stirling1(n,k)|*A055203(k).
a(n) = Sum_{k>=0} binomial(k*(k-1)/2+n-1,n)/2^(k+1).
a(n) ~ n^n * 2^(n-1 + log(2)/4) / (exp(n) * (log(2))^(2*n+1)). - Vaclav Kotesovec, Mar 15 2014
a(n) = Sum_{j=0..2*n} binomial(binomial(j,2)+n-1, n) * (Sum_{i=j..2*n} (-1)^(i-j)*binomial(i,j)). - Andrew Howroyd, Feb 09 2020

A136245 a(n) = (1/n!)Sum_{k=0..n} Stirling1(n,k)A062208(k).

Original entry on oeis.org

1, 1, 31, 2649, 441061, 121105865, 49615422851, 28371278927921, 21590240845164949, 21097596332115411641, 25747535208630845100139, 38380480386387824213385401, 68621153798435104081277748401

Offset: 0

Vladeta Jovovic, Mar 16 2008

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

Cf. A121251.

a(n) = Sum_{m>=0} binomial(binomial(m,3),n)/2^(m+1).

More terms from Alois P. Heinz, Aug 13 2008

cp's OEIS Frontend

A372175 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with exactly 2k directed cycles of length > 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A173219 G.f.: A(x) = Sum_{n>=0} (1 + x)^(n(n+1)/2) / 2^(n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A331277 Array read by antidiagonals: A(n,k) is the number of binary matrices with k distinct columns and any number of nonzero rows with n ones in every column and columns in decreasing lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A121316 Unlabeled version of A055203: number of different relations between n intervals (of nonzero length) on a line, up to permutation of intervals.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A136245 a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k)*A062208(k).

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A136245 a(n) = (1/n!)Sum_{k=0..n} Stirling1(n,k)A062208(k).