The On-Line Encyclopedia of Integer Sequences (OEIS)

The OEIS is supported by the many generous donors to the OEIS Foundation.

Revision History for A003430 (Bold, blue-underlined text is an addition; faded, red-underlined text is a ~~deletion~~.)
Showing entries 1-10 | older changes

Number of unlabeled series-parallel posets (i.e., generated by unions and sums) with n nodes.
(history; published version)

#77 by OEIS Server at Wed Dec 02 13:57:16 EST 2020

LINKS

Alois P. Heinz, <a href="/A003430/b003430_1.txt">Table of n, a(n) for n = 0..1000</a> (terms n = 1..100 from Jean-François Alcover)

#76 by Alois P. Heinz at Wed Dec 02 13:57:16 EST 2020

STATUS

editing

approved

Discussion

Wed Dec 02

13:57

OEIS Server: Installed new b-file as b003430.txt.  Old b-file is now b003430_1.txt.

#75 by Alois P. Heinz at Wed Dec 02 13:57:02 EST 2020

LINKS

Jean-François Alcover, Alois P. Heinz, <a href="/A003430/b003430_1.txt">Table of n, a(n) for n = 0..1000</a> (terms n = 1..100</a> from Jean-François Alcover)

STATUS

approved

editing

#74 by Alois P. Heinz at Wed Dec 02 13:55:53 EST 2020

STATUS

editing

approved

#73 by Alois P. Heinz at Tue Dec 01 16:35:20 EST 2020

DATA

1, 1, 2, 5, 15, 48, 167, 602, 2256, 8660, 33958, 135292, 546422, 2231462, 9199869, 38237213, 160047496, 674034147, 2854137769, 12144094756, 51895919734, 222634125803, 958474338539, 4139623680861, 17931324678301, 77880642231286, 339093495674090, 1479789701661116

OFFSET

1,2

0,3

EXTENSIONS

a(0)=1 prepended (using the g.f.) by Alois P. Heinz, Dec 01 2020

Discussion

Wed Dec 02

13:55

Alois P. Heinz: I will publish now ...

#72 by Andrew Howroyd at Tue Dec 01 14:45:54 EST 2020

COMMENTS

Number of number of oriented series-parallel networks with n elements. A series configuration is a unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is a unit element or a multiset of two or more series configurations. a(n) is the number of series or parallel configurations with n elements. The sequences A007453 and A007454 enumerate respectively series and parallel configurations. - Andrew Howroyd, Dec 01 2020

Discussion

Tue Dec 01

14:55

Andrew Howroyd: I think I understand the justification of why "rooted" trees don't normally have a(0)=1. Consider the number of expressions using n 1's and +, - operations: For n=1 there is (1), and for n=2 there is (1 + 1) and (1 * 1) etc. For n = 0 the answer isn't 1 because () isn't a valid expression - the grammar just doesn't allow it. [I have added the logical grammar for this tree in comments]. Similarly A126100 has a(1)=0 (see explanation in that sequence) and A303831 has a(1)=a(2)=0. There may of coarse be other interpretations in which a(1)=1 makes sense.

15:20

Andrew Howroyd: sorry for all the typos! (I wish there was a way to edit pink box comments). I mean "a(0)=0 and a(0)=a(1)=0 and a(0)=1" (offset issues in my typing - sigh!)

16:27

Alois P. Heinz: The Stanley article has f_0=1 (page 296) and F(x)=1 + x + 2*x^2 + 5*x^3 + ... (page 298) ...

16:29

Alois P. Heinz: the same can be found in Finch's article ...

16:32

Alois P. Heinz: also in Uli Fahrenberg et.al. article ...

#71 by Andrew Howroyd at Tue Dec 01 14:45:07 EST 2020

COMMENTS

Number of number of oriented series-parallel networks with n elements. A series configuration is a unit element or an ordered concatenation of two or more parallel configurations and a parallel configuration is a unit element or a multiset of two or more series configurations. a(n) is the number of series or parallel configurations with n elements. The sequences A007453 and A007454 enumerate respectively series and parallel configurations. - Andrew Howroyd, Dec 01 2020

CROSSREFS

Row sums of A339231.

Column k=1 of A339228.

Cf. A000669, A000084, A003431, A048172 (labeled N-free posets), A007453, A007454, A339156, A339159, A339225.

#70 by Andrew Howroyd at Fri Nov 27 18:07:50 EST 2020

EXAMPLE

a(4) = 15: (oooo), (oo(o|o)), (o(o|o)o), ((o|o)oo), ((o|o)(o|o)), (o(o|oo)), (o(o|o|o)), ((o|oo)o), ((o|o|o)o), (o|o|o|o), (o|o|oo), (oo|oo), (o|(ooo)), , (o|(o(o|o))), , (o|((o|o)o)).

PROG

(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}

seq(n)={my(p=x+O(x^2)); for(n=2, n, p=x*Ser(EulerT(Vec(p^2/(1+p)+x, 1-n)))); Vec(p)} \\ Andrew Howroyd, Nov 27 2020

Discussion

Mon Nov 30

21:19

Alois P. Heinz: a(0)=1: () makes sense.  See g.f. also.

22:14

Andrew Howroyd: That's a huge change (if applied everywhere). Most of the core sequences relating to trees do not include. A000084, A000669 which is a very similar sequence (series-parallel with series also being multisets) do not have. I don't pretend to know why most tree sequences don't have a(0)=1 (perhaps just history?, but I suspect there is more to it  - there is a comment somewhere, but don't ask me for the seq nr that says the sequence has a(0)=0, although a(0)=1 would also make sense - I strongly suspect someone has had this argument before?).
In any case this is not a piece of string I want to start pulling on - because all of these sequences interrelate. (but feel free)

#69 by Andrew Howroyd at Thu Nov 26 18:31:46 EST 2020

CROSSREFS

Cf. A000669, A003431, A053554 A048172 (labeled N-free posets), A007453, A007454.

#68 by Andrew Howroyd at Thu Nov 26 17:57:26 EST 2020

FORMULA

From: Andrew Howroyd, Nov 26 2020: (Start)

a(n) = A007453(n) + A007454(n) for n > 1.

Euler transform of A007453.

G.f.: P(x)/(1 - P(x)) where P(x) is the g.f. of A007454.

(End)

EXAMPLE

From Andrew Howroyd, Nov 26 2020: (Start)

In the following examples of series-parallel networks, elements in series are juxtaposed and elements in parallel are separated by '|'. The unit element is denoted by 'o'.

a(1) = 1: (o).

a(2) = 2: (oo), (o|o).

a(3) = 5: (ooo), (o(o|o)), ((o|o)o), (o|o|o), (o|oo).

a(4) = 15: (oooo), (oo(o|o)), (o(o|o)o), ((o|o)oo), ((o|o)(o|o)), (o(o|oo)), (o(o|o|o)), ((o|oo)o), ((o|o|o)o), (o|o|o|o), (o|o|oo), (oo|oo), (o|(ooo)), (o|(o(o|o))), (o|((o|o)o)).

(End)

CROSSREFS

Cf. A000669, A003431, A053554 (labeled N-free posets), A007453, A007454.

STATUS

approved

editing