cp's OEIS Frontend

There is a connection with the alternating series 1 - (1-x) + (1-x)(1-x^2) - (1-x)(1-x^2)(1-x^3) + .... Namely, if we replace x with 1/(1-x) in the partial sum 1 - (1-x) + (1-x)(1-x^2) - (1-x)(1-x^2)(1-x^3) + ... + (-1)^n(1-x)(1-x^2)...(1-x^n) and then expand about x = 0 we get a series whose first n+1 coefficients agree with the first n+1 terms of the present sequence.

From Vít Jelínek, Sep 04 2014: (Start)

The above remark, first conjectured by Bala, is a consequence of the identities satisfied by the generating function for a(n). More precisely, the generating function F(x)=Sum_{n>=0} a(n)x^n can be expressed by any of these three formulas:

F(x) = Sum_{n>=0} Product_{i=1..n} (1-(1-x)^(2*i-1))

F(x) = Sum_{n>=0} Product_{i=1..n} (1/(1-x)^i - 1)

F(x) = Sum_{n>=0} (1-x)^(n+1) Product_{i=1..n} (1-(1-x)^(2*i))

The first two formulas were conjectured to be equal by Bala. This was confirmed by Andrews and Jelínek, who also derived the third formula.

Bringmann, Li and Rhoades have independently derived the three formulas above, and additionaly, they proved that

F(x) = (1/2)*Sum_{n>=0} Product_{i=1..n} (1/(1+(1-x)^i)).

(End)

From Vít Jelínek, Feb 12 2012: (Start)

a(n) has the following combinatorial interpretations:

(1) the number of upper-triangular nonnegative integer matrices with at least one positive entry in each row, whose entries sum to n. E.g., for n=2 this corresponds to these three matrices (with zeros represented as dots):

(2), (1.) and (.1)

(.1) (.1)

(2) the number of upper-triangular nonnegative matrices that are symmetric along the northeast diagonal, have no positive entry on the northeast diagonal, have at least one positive entry in every row and column, and their entries sum to 2n. These are the three such matrices with n=2:

(2.), (11.) and (1...)

(.2) (..1) (.1..)

(..1) (..1.)

(...1)

(3) the number of upper-triangular nonnegative matrices that are symmetric along the northeast diagonal, have at least one positive entry on the northeast diagonal, have at least one positive entry in every row and column, and their entries on or above the northeast diagonal sum to n. These are the three such matrices with n=2:

(2), (11) and (1..)

(.1) (.1.)

(..1)

(End)

The first column and the row sums are both A022493.

Also the number of length-n ascent sequences with k fixed points. [Joerg Arndt, Nov 03 2012]

Row sums are A022493.

Second column is A000225 (2^n - 1).

Third column appears to be A000392 (Stirling numbers S(n,3)).

Second diagonal (from the right) appears to be A006127 (2^n + n).

Row sums are A022493.

First column and the diagonal is A022493(n-1).

A Fishburn matrix is defined to be an upper-triangular matrix with nonnegative integer entries such that each row and column contains a nonzero entry. See A005321 for primitive Fishburn matrices of dimension n, that is, Fishburn matrices of dimension n with entries in the set {0,1}.

The present sequence has an alternative description as the number of primitive Fishburn matrices of dimension n where the 1's may be colored either black or white.

A Fishburn matrix is defined to be an upper-triangular matrix with nonnegative integer entries such that each row and column contains a nonzero entry. See A005321 for primitive Fishburn matrices of dimension n, that is, Fishburn matrices of dimension n with entries in the set {0,1}.

The present sequence has an alternative description as the number of primitive Fishburn matrices of dimension n where each entry equal to 1 can have one of three different colors. Cf. A289314.

It appears that no formula or g.f. is known.

It appears that no formula or g.f. is known.

From Joerg Arndt, Jan 20 2024: (Start)

a(n) is the number of weak ascent sequences of length n.

A weak ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, d(k)>=0, and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) counts the weak ascents d(j) >= d(j-1) of its argument.

The number of length-n weak ascent sequences with maximal number of weak ascents is A000108(n).

(End)

From Lara Pudwell, Oct 23 2008: (Start)

A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a < c < b.

Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.

A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.

For example, if q=5{bar 1}32{bar 4}, then q1=532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b < d < c < e < a.

(End)

Also equals the row sums of triangle A131338, which starts with a '1' in row 0 and then for n > 0 row n consists of n '1's followed by the partial sums of the prior row.

Also the number of permutations in S_n avoiding {bar 4}25{bar 1}3 (i.e., every occurrence of 253 is contained in an occurrence of a 42513). - Lara Pudwell, Apr 25 2008 (see the Claesson-Dukes-Kitaev article)

From Frank Ruskey, Apr 17 2011: (Start)

Number of sequences S = s(1)s(2)...s(n) such that

S contains m 0's,

for 1 <= j <= n, s(j) < j and s(j-s(j)) = 0,

for 1 < j <= n, if s(j) positive, then s(j-1) < s(j).

(End)

a(n) is also the number of length n permutations that simultaneously avoid the bivincular patterns (132,{2},{}) and (132,{},{2}). - Christian Bean, Mar 25 2015

a(n) is also the number of length n permutations that simultaneously avoid the bivincular patterns (123,{2},{}) and (123,{},{2}). These are the same as the permutations avoiding {bar 4}23{bar 1}5. - Christian Bean, Jun 03 2015

From Peter R. W. McNamara, Jun 22 2019: (Start)

a(n) is the number of upper-triangular matrices with nonnegative integer entries whose entries sum to n, and whose diagonal entries are all positive.

a(n) is the number of ascent sequences [d(1), d(2), ..., d(n)] A022493 for which d(k) comes from the interval [0, d(k-1)] or equals 1 + max([d(1), d(2), ..., d(k-1)]) = 1 + asc([d(1), d(2), ..., d(k-1)]) where asc(.) counts the ascents of its argument. Such sequences are called "self modified ascent sequences" in Bousquet-Mélou et al.

The elements of a (2+2)-free poset can be partitioned into levels, where all elements at the same level have the same strict down-set. Then a(n) is the number of unlabeled (2+2)-free posets with n elements that contain a chain with exactly one element at each level.

(End)