cp's OEIS Frontend

The total number of those graphs of order 5 is 608. The number of forests of trees on n labeled nodes of order 5 is 291, so the majority of the graphs of that kind have one or more unicycles.

Also the number of labeled graphs with n vertices satisfying a strict version of the axiom of choice. The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once. The connected case is A129271, complement A140638. The unlabeled version is A134964. - Gus Wiseman, Dec 22 2023

Conjecture: this sequence is the inverse binomial transform of A075272 or, equivalently, the inverse binomial transform of the BinomialMean transform of A075271. - John W. Layman, Sep 12 2002

To win a game, you must flip n+1 heads in a row, where n is the total number of tails flipped so far. Then the probability of winning for the first time after n tails is A005329 / A006125. The probability of having won before n+1 tails is A114604 / A006125. - Joshua Zucker, Dec 14 2005

Number of upper triangular n X n (0,1)-matrices with no zero rows. - Vladeta Jovovic, Mar 10 2008

Equals the q-Fibonacci series for q = (-2), and the series prefaced with a 1: (1, 1, 1, 3, 21, ...) dot (1, -2, 4, -8, ...) if n is even, and (-1, 2, -4, 8, ...) if n is odd. For example, a(3) = 21 = (1, 1, 1, 3) dot (-1, 2, -4, 8) = (-1, 2, -4, 24) and a(4) = 315 = (1, 1, 1, 3, 21) dot (1, -2, 4, -8 16) = (1, -2, 4, -24, 336). - Gary W. Adamson, Apr 17 2009

Number of chambers in an A_n(K) building where K=GF(2) is the field of two elements. This is also the number of maximal flags in an n-dimensional vector space over a field of two elements. - Marcos Spreafico, Mar 22 2012

Given probability p = 1/2^n that an outcome will occur at the n-th stage of an infinite process, then starting at n=1, A114604(n)/A006125(n+2) = 1-a(n)/A006125(n+1) is the probability that the outcome has occurred up to and including the n-th iteration. The limiting ratio is 1-A048651 ~ 0.7112119. These observations are a more formal and generalized statement of Joshua Zucker's Dec 14, 2005 comment. - Bob Selcoe, Mar 02 2016

Also the number of dominating sets in the n-triangular honeycomb rook graph. - Eric W. Weisstein, Jul 14 2017

Empirical: Letting Q denote the Hall-Littlewood Q basis of the symmetric functions over the field of fractions of the univariate polynomial ring in t over the field of rational numbers, and letting h denote the complete homogeneous basis, a(n) is equal to the absolute value of 2^A000292(n) times the coefficient of h_{1^(n*(n+1)/2)} in Q_{(n, n-1, ..., 1)} with t evaluated at 1/2. - John M. Campbell, Apr 30 2018

The series f(x) = Sum_{n>=0} x^(2^n-1)/a(n) satisfies f'(x) = f(x^2), f(0) = 1. - Lucas Larsen, Jan 05 2022

Nilpotent n X n matrices over GF(2). Also number of simple digraphs (without self-loops) on n labeled nodes (see also A002416).

For n >= 1 a(n) is the size of the Sylow 2-subgroup of the Chevalley group A_n(4) (sequence A053291). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 30 2001

(-1)^ceiling(n/2) * resultant of the Chebyshev polynomial of first kind of degree n and Chebyshev polynomial of first kind of degree (n+1) (cf. A039991). - Benoit Cloitre, Jan 26 2003

The number of reflexive binary relations on an n-element set. - Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005

From Rick L. Shepherd, Dec 24 2008: (Start)

Number of gift exchange scenarios where, for each person k of n people,

i) k gives gifts to g(k) of the others, where 0 <= g(k) <= n-1,

ii) k gives no more than one gift to any specific person,

iii) k gives no single gift to two or more people and

iv) there is no other person j such that j and k jointly give a single gift.

(In other words -- but less precisely -- each person k either gives no gifts or gives exactly one gift per person to 1 <= g(k) <= n-1 others.) (End)

In general, sequences of the form m^((n^2 - n)/2) enumerate the graphs with n labeled nodes with m types of edge. a(n) therefore is the number of labeled graphs with n nodes with 4 types of edge. To clarify the comment from Benoit Cloitre, dated Jan 26 2003, in this context: simple digraphs (without self-loops) have four types of edge. These types of edges are as follows: the absent edge, the directed edge from A -> B, the directed edge from B -> A and the bidirectional edge, A <-> B. - Mark Stander, Apr 11 2019

The span of a graph is the union of its edges.

Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - Vladeta Jovovic, Oct 26 2004

a(n) is the number of trees on vertex set [n] = {1,2,...,n} rooted at 1 with one marked inversion (an inversion is a pair (i,j) with i > j and j a descendant of i in the tree). Here is a bijection from the title graphs (on [n]) to these marked trees. A title graph has exactly one cycle. There is a unique path from vertex 1 to this cycle, first meeting it at k, say (k may equal 1). Let i and j be the two neighbors of k in the cycle, with i the larger of the two. Delete the edge k<->j thereby forming a tree (in which j is a descendant of i) and take (i,j) as the marked inversion. To reverse this map, create a cycle by joining the smaller element of the marked inversion to the parent of the larger element. a(n) = binomial(n-1,2)*A129137(n). This is because, on the above marked trees, the marked inversion is uniformly distributed over 2-element subsets of {2,3,...,n} and so a(n)/binomial(n-1,2) is the number of trees on [n] (rooted at 1) for which (3,2) is an inversion. - David Callan, Mar 30 2007

a(n) is the number of Dyck paths of semilength n with no UUDD. See A025242 for a bijection between paths avoiding DDUU versus UUDD.

Also number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=1. - Alois P. Heinz, Oct 07 2015

a(n) is the number of bargraphs of semiperimeter n (n>=2). Example: a(4) = 5; the 5 bargraphs correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3]. - Emeric Deutsch, May 20 2016 [a(n) are the row sums of A271942 for n >= 2. Peter Luschny, Oct 18 2020]

a(n) is the number of skew Motzkin paths of length n. A skew Motzkin path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1) (up), D=(1,-1) (down), F=(1,0) (flat) and A=(-1,1) (anti-down) so that down and anti-down steps do not overlap. - Sergey Kirgizov, Oct 03 2018

From Gus Wiseman, Jul 04 2019: (Start)

Conjecture: Also the number of maximal simple graphs with vertices {1..n} and no weakly nesting edges. Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d. For example, the a(1) = 1 through a(5) = 13 edge-sets are:

{} {12} {13} {14} {15}

{12,23} {12,24} {12,25}

{13,24} {13,25}

{13,34} {14,25}

{12,23,34} {14,35}

{14,45}

{12,23,35}

{12,24,35}

{12,24,45}

{13,24,35}

{13,24,45}

{13,34,45}

{12,23,34,45}

Cf. A006125, A054726, A117662, A326244, A326257, A326289, A326293, A326329, A326337, A326338, A326340.

(End)

a(n) is the number of Dyck n-paths in which no nonterminal descent has the same length as the preceding ascent. Example: a(3) = 2 counts UUDUDD and UUUDDD where the latter path qualifies because DDD is the terminal descent. - David Callan, Dec 14 2021

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

In the connected case, these are just graphs with more than one cycle.

Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015

Number of unlabeled acyclic graphs on n vertices. The labeled version is A001858. The covering case is A144958, connected A000055. - Gus Wiseman, Apr 29 2024

The obverse convolution of sequences

s = (s(0), s(1), ...) and t = (t(0), t(1), ...)

is introduced here as the sequence s**t given by

s**t(n) = (s(0)+t(n)) * (s(1)+t(n-1)) * ... * (s(n)+t(0)).

Swapping * and + in the representation s(0)*t(n) + s(1)*t(n-1) + ... + s(n)*t(0)

of ordinary convolution yields s**t.

If x is an indeterminate or real (or complex) variable, then for every sequence t of real (or complex) numbers, s**t is a sequence of polynomials p(n) in x, and the zeros of p(n) are the numbers -t(0), -t(1), ..., -t(n).

Following are abbreviations in the guide below for triples (s, t, s**t):

F = (0,1,1,2,3,5,...) = A000045, Fibonacci numbers

L = (2,1,3,4,7,11,...) = A000032, Lucas numbers

P = (2,3,5,7,11,...) = A000040, primes

T = (1,3,6,10,15,...) = A000217, triangular numbers

C = (1,2,6,20,70, ...) = A000984, central binomial coefficients

LW = (1,3,4,6,8,9,...) = A000201, lower Wythoff sequence

UW = (2,5,7,10,13,...) = A001950, upper Wythoff sequence

[ ] = floor

In the guide below, sequences s**t are identified with index numbers Axxxxxx; in some cases, s**t and Axxxxxx differ in one or two initial terms.

Table 1. s = A000012 = (1,1,1,1...) = (1);

t = A000012; 1 s**t = A000079; 2^(n+1)

t = A000027; n s**t = A000142; (n+1)!

t = A000040, P s**t = A054640

t = A000040, P (1/3) s**t = A374852

t = A000079, 2^n s**t = A028361

t = A000079, 2^n (1/3) s**t = A028362

t = A000045, F s**t = A082480

t = A000032, L s**t = A374890

t = A000201, LW s**t = A374860

t = A001950, UW s**t = A374864

t = A005408, 2*n+1 s**t = A000165, 2^n*n!

t = A016777, 3*n+1 s**t = A008544

t = A016789, 3*n+2 s**t = A032031

t = A000142, n! s**t = A217757

t = A000051, 2^n+1 s**t = A139486

t = A000225, 2^n-1 s**t = A006125

t = A032766, [3*n/2] s**t = A111394

t = A034472, 3^n+1 s**t = A153280

t = A024023, 3^n-1 s**t = A047656

t = A000217, T s**t = A128814

t = A000984, C s**t = A374891

t = A279019, n^2-n s**t = A130032

t = A004526, 1+[n/2] s**t = A010551

t = A002264, 1+[n/3] s**t = A264557

t = A002265, 1+[n/4] s**t = A264635

Sequences (c)**L, for c=2..4: A374656 to A374661

Sequences (c)**F, for c=2..6: A374662, A374662, A374982 to A374855

The obverse convolutions listed in Table 1 are, trivially, divisibility sequences. Likewise, if s = (-1,-1,-1,...) instead of s = (1,1,1,...), then s**t is a divisibility sequence for every choice of t; e.g. if s = (-1,-1,-1,...) and t = A279019, then s**t = A130031.

Table 2. s = A000027 = (0,1,2,3,4,5,...) = (n);

t = A000027, n s**t = A007778, n^(n+1)

t = A000290, n^2 s**t = A374881

t = A000040, P s**t = A374853

t = A000045, F s**t = A374857

t = A000032, L s**t = A374858

t = A000079, 2^n s**t = A374859

t = A000201, LW s**t = A374861

t = A005408, 2*n+1 s**t = A000407, (2*n+1)! / n!

t = A016777, 3*n+1 s**t = A113551

t = A016789, 3*n+2 s**t = A374866

t = A000142, n! s**t = A374871

t = A032766, [3*n/2] s**t = A374879

t = A000217, T s**t = A374892

t = A000984, C s**t = A374893

t = A038608, n*(-1)^n s**t = A374894

Table 3. s = A000290 = (0,1,4,9,16,...) = (n^2);

t = A000290, n^2 s**t = A323540

t = A002522, n^2+1 s**t = A374884

t = A000217, T s**t = A374885

t = A000578, n^3 s**t = A374886

t = A000079, 2^n s**t = A374887

t = A000225, 2^n-1 s**t = A374888

t = A005408, 2*n+1 s**t = A374889

t = A000045, F s**t = A374890

Table 4. s = t;

s = t = A000012, 1 s**s = A000079; 2^(n+1)

s = t = A000027, n s**s = A007778, n^(n+1)

s = t = A000290, n^2 s**s = A323540

s = t = A000045, F s**s = this sequence

s = t = A000032, L s**s = A374850

s = t = A000079, 2^n s**s = A369673

s = t = A000244, 3^n s**s = A369674

s = t = A000040, P s**s = A374851

s = t = A000201, LW s**s = A374862

s = t = A005408, 2*n+1 s**s = A062971

s = t = A016777, 3*n+1 s**s = A374877

s = t = A016789, 3*n+2 s**s = A374878

s = t = A032766, [3*n/2] s**s = A374880

s = t = A000217, T s**s = A375050

s = t = A005563, n^2-1 s**s = A375051

s = t = A279019, n^2-n s**s = A375056

s = t = A002398, n^2+n s**s = A375058

s = t = A002061, n^2+n+1 s**s = A375059

If n = 2*k+1, then s**s(n) is a square; specifically,

s**s(n) = ((s(0)+s(n))*(s(1)+s(n-1))*...*(s(k)+s(k+1)))^2.

If n = 2*k, then s**s(n) has the form 2*s(k)*m^2, where m is an integer.

Table 5. Others

s = A000201, LW t = A001950, UW s**t = A374863

s = A000045, F t = A000032, L s**t = A374865

s = A005843, 2*n t = A005408, 2*n+1 s**t = A085528, (2*n+1)^(n+1)

s = A016777, 3*n+1 t = A016789, 3*n+2 s**t = A091482

s = A005408, 2*n+1 t = A000045, F s**t = A374867

s = A005408, 2*n+1 t = A000032, L s**t = A374868

s = A005408, 2*n+1 t = A000079, 2^n s**t = A374869

s = A000027, n t = A000142, n! s**t = A374871

s = A005408, 2*n+1 t = A000142, n! s**t = A374872

s = A000079, 2^n t = A000142, n! s**t = A374874

s = A000142, n! t = A000045, F s**t = A374875

s = A000142, n! t = A000032, L s**t = A374876

s = A005408, 2*n+1 t = A016777, 3*n+1 s**t = A352601

s = A005408, 2*n+1 t = A016789, 3*n+2 s**t = A064352

Table 6. Arrays of coefficients of s(x)**t(x), where s(x) and t(x) are polynomials

s(x) t(x) s(x)**t(x)

n x A132393

n^2 x A269944

x+1 x+1 A038220

x+2 x+2 A038244

x x+3 A038220

nx x+1 A094638

1 x^2+x+1 A336996

n^2 x x+1 A375041

n^2 x 2x+1 A375042

n^2 x x+2 A375043

2^n x x+1 A375044

2^n 2x+1 A375045

2^n x+2 A375046

x+1 F(n) A375047

x+1 x+F(n) A375048

x+F(n) x+F(n) A375049

Related to Schröder's second problem.

A001006 gives number of ways of drawing any number of nonintersecting chords between n points on a circle, while this sequence gives number of ways of drawing noncrossing chords between n points on a circle. The difference is that nonintersection chords have no point in common, while noncrossing chords may share an endpoint. - David W. Wilson, Jan 30 2003

For n>0, a(n) = number of lattice paths from (0,0) to (n-1,n-1) that consist of steps (i,j), i,j nonnegative integers not both 0 and that stay strictly below the line y=x except at their endpoints. For example, a(3)=8 counts the paths with following step sequences: {(2, 2)}, {(2, 1), (0, 1)}, {(2, 0), (0, 2)}, {(2, 0), (0, 1), (0, 1)}, {(1, 0), (1, 2)}, {(1, 0), (1, 1), (0, 1)}, {(1, 0), (1, 0), (0, 2)}, {(1, 0), (1, 0), (0, 1), (0, 1)}. If the word "strictly" is replaced by "weakly", the counting sequence becomes A059435. - David Callan, Jun 07 2006

The nodes on the circle are distinguished by their positions but are otherwise unlabeled. - Lee A. Newberg, Aug 09 2011

From Gus Wiseman, Jun 22 2019: (Start)

Conjecture: Also the number of simple graphs with vertices {1..n} not containing any pair of nesting edges. Two edges {a,b}, {c,d} where a < b and c < d are nesting if a < c and b > d or a > c and b < d. For example, the a(0) = 1 through a(3) = 8 non-nesting edge-sets are:

{} {} {} {}

{12} {12}

{13}

{23}

{12,13}

{12,23}

{13,23}

{12,13,23}

Cf. A001519, A117662, A326244, A326256, A326257, A326279.

(End)