login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047970 Antidiagonal sums of nexus numbers (A047969). 20
1, 2, 5, 14, 43, 144, 523, 2048, 8597, 38486, 182905, 919146, 4866871, 27068420, 157693007, 959873708, 6091057009, 40213034874, 275699950381, 1959625294310, 14418124498211, 109655727901592, 860946822538675, 6969830450679864, 58114638923638573 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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)

Number of ordered factorizations over the Gaussian polynomials.

Apparently, also the number of permutations in S_n avoiding {bar 3}{bar 1}542 (i.e., every occurrence of 542 is contained in an occurrence of a 31542). - Lara Pudwell, Apr 25 2008

With offset 1, apparently the number of sequences {b(m)} of length n of positive integers with b(1) = 1 and, for all m > 1, b(m) <= max{b(m-1) + 1, max{b(i) | 1 <= i <= m - 1}}. This sequence begins 1, 2, 5, 14, 43, 144, 523, 2048, 8597, 38486. The term 144 counts the length 6 sequence 1, 2, 3, 1, 1, 3, for instance. Contrast with the families of sequences discussed in Franklin T. Adams-Watters's comment in A005425. - Rick L. Shepherd, Jan 01 2015

a(n-1) for n>=1 is the number of length-n restricted growth strings (RGS)  [s(0), s(1), ..., s(n-1)] with s(0)=0 and s(k) <= the number of fixed points in the prefix, see example. - Joerg Arndt, Mar 08 2015

Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) = e(k). [Martinez and Savage, 2.15] - Eric M. Schmidt, Jul 17 2017

LINKS

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

G. E. Andrews, The Theory of Partitions, 1976, page 242 table of Gaussian polynomials.

D. Callan, The number of bar(31)542-avoiding permutations, arXiv:1111.3088

Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.

Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.

Eric Weisstein's World of Mathematics, Nexus Number

FORMULA

Formal o.g.f.: (1 - x)*( sum {n >= 0} x^n/(1 - (n + 2)*x) ). - Peter Bala, Jul 09 2014

O.g.f.: Sum_{n>=0} (n+1)! * x^n/(1-x)^(n+1) / Product_{k=1..n+1} (1 + k*x). - Paul D. Hanna, Jul 20 2014

O.g.f.: Sum_{n>=0} x^n / ( (1 - n*x) * (1 - (n+1)*x) ). - Paul D. Hanna, Jul 22 2014

EXAMPLE

a(3) = 1 + 5 + 7 + 1 = 14.

From Paul D. Hanna, Jul 22 2014:  (Start)

G.f. A(x) = 1 + 2*x + 5*x^2 + 14*x^3 + 43*x^4 + 144*x^5 + 523*x^6 + 2048*x^7 + ...

where we have the series identity:

A(x) = (1-x)*( 1/(1-2*x) + x/(1-3*x) + x^2/(1-4*x) + x^3/(1-5*x) + x^4/(1-6*x) + x^5/(1-7*x) + x^6/(1-8*x) +... )

is equal to

A(x) = 1/(1-x) + x/((1-x)*(1-2*x)) + x^2/((1-2*x)*(1-3*x)) + x^3/((1-3*x)*(1-4*x)) + x^4/((1-4*x)*(1-5*x)) + x^5/((1-5*x)*(1-6*x)) + x^6/((1-6*x)*(1-7*x)) +...

and also equals

A(x) = 1/((1-x)*(1+x)) + 2!*x/((1-x)^2*(1+x)*(1+2*x)) + 3!*x^2/((1-x)^3*(1+x)*(1+2*x)*(1+3*x)) + 4!*x^3/((1-x)^4*(1+x)*(1+2*x)*(1+3*x)*(1+4*x)) +...

(End)

From Joerg Arndt, Mar 08 2015: (Start)

There are a(4-1)=14 length-4 RGS as in the comment (dots denote zeros):

01:  [ . . . . ]

02:  [ . . . 1 ]

03:  [ . . 1 . ]

04:  [ . . 1 1 ]

05:  [ . 1 . . ]

06:  [ . 1 . 1 ]

07:  [ . 1 . 2 ]

08:  [ . 1 1 . ]

09:  [ . 1 1 1 ]

10:  [ . 1 1 2 ]

11:  [ . 1 2 . ]

12:  [ . 1 2 1 ]

13:  [ . 1 2 2 ]

14:  [ . 1 2 3 ]

(End)

MAPLE

T := proc(n, k) option remember; local j;

    if k=n then 1

  elif k>n then 0

  else (k+1)*T(n-1, k) + add(T(n-1, j), j=k..n)

    fi end:

A047970 := n -> T(n, 0);

seq(A047970(n), n=0..24); # Peter Luschny, May 14 2014

MATHEMATICA

a[ n_] := SeriesCoefficient[ ((1 - x) Sum[ x^k / (1 - (k + 2) x), {k, 0, n}]), {x, 0, n}]; (* Michael Somos, Jul 09 2014 *)

PROG

(Sage)

def A074664():

    T = []; n = 0

    while True:

        T.append(1)

        yield T[0]

        for k in (0..n):

            T[k] = (k+1)*T[k] + add(T[j] for j in (k..n))

        n += 1

a = A074664()

[a.next() for n in range(25)] # Peter Luschny, May 13 2014

(PARI) /* From o.g.f. (Paul D. Hanna, Jul 20 2014) */

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

for(n=0, 25, print1(a(n), ", "))

(PARI) /* From o.g.f. (Paul D. Hanna, Jul 22 2014) */

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

for(n=0, 25, print1(a(n), ", "))

CROSSREFS

Partial sums are in A026898, A003101. First differences A112532.

Cf. A112531.

Sequence in context: A014327 A173437 A137550 * A160701 A137551 A148333

Adjacent sequences:  A047967 A047968 A047969 * A047971 A047972 A047973

KEYWORD

nonn

AUTHOR

Alford Arnold, Dec 11 1999

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 20 12:19 EST 2017. Contains 294967 sequences.