Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #97 Jul 10 2023 10:29:23
%S 1,2,5,14,43,144,523,2048,8597,38486,182905,919146,4866871,27068420,
%T 157693007,959873708,6091057009,40213034874,275699950381,
%U 1959625294310,14418124498211,109655727901592,860946822538675,6969830450679864,58114638923638573
%N Antidiagonal sums of nexus numbers (A047969).
%C From _Lara Pudwell_, Oct 23 2008: (Start)
%C 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.
%C 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.
%C 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.
%C 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)
%C Number of ordered factorizations over the Gaussian polynomials.
%C 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
%C 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
%C 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
%C 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
%C a(n) counts all positive-integer m-tuples whose maximum is n-m+2. - _Mathew Englander_, Feb 28 2021
%C a(n) counts the cyclic permutations of [n+2] that avoid the vincular pattern 12-3-4, i.e., the pattern 1234 where the 1 and 2 are required to be adjacent. - _Rupert Li_, Jul 27 2021
%H Alois P. Heinz, <a href="/A047970/b047970.txt">Table of n, a(n) for n = 0..300</a>
%H G. E. Andrews, <a href="http://books.google.de/books?id=Sp7z9sK7RNkC&lpg=PA242&vq=242&hl=de&pg=PA242#v=onepage&q&f=false">The Theory of Partitions</a>, 1976, page 242 table of Gaussian polynomials.
%H David Callan, <a href="http://arxiv.org/abs/1111.3088">The number of bar(31)542-avoiding permutations</a>, arXiv:1111.3088 [math.CO], 2011.
%H Rupert Li, <a href="https://arxiv.org/abs/2107.12353">Vincular Pattern Avoidance on Cyclic Permutations</a>, arXiv:2107.12353 [math.CO], 2021.
%H Zhicong Lin and Sherry H. F. Yan, <a href="https://doi.org/10.1016/j.amc.2019.124672">Vincular patterns in inversion sequences</a>, Applied Mathematics and Computation (2020), Vol. 364, 124672.
%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/pudwell_thesis.pdf">Enumeration Schemes for Pattern-Avoiding Words and Permutations</a>, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
%H Lara Pudwell, <a href="https://doi.org/10.37236/301">Enumeration schemes for permutations avoiding barred patterns</a>, El. J. Combinat. 17 (1) (2010) R29.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/NexusNumber.html">Nexus Number</a>
%H Chunyan Yan and Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.
%F Formal o.g.f.: (1 - x)*( Sum_{n >= 0} x^n/(1 - (n + 2)*x) ). - _Peter Bala_, Jul 09 2014
%F 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
%F O.g.f.: Sum_{n>=0} x^n / ( (1 - n*x) * (1 - (n+1)*x) ). - _Paul D. Hanna_, Jul 22 2014
%F From _Mathew Englander_, Feb 28 2021: (Start)
%F a(n) = A089246(n+2,0) = A242431(n,0).
%F a(n) = Sum_{m = 1..n+1} Sum_{i = 0..m-1} binomial(m,i) * (n-m+1)^i.
%F a(n) = 1 + Sum_{i = 0..n} i * (i+1)^(n-i). (End)
%e a(3) = 1 + 5 + 7 + 1 = 14.
%e From _Paul D. Hanna_, Jul 22 2014: (Start)
%e 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 + ...
%e where we have the series identity:
%e 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) + ...)
%e is equal to
%e 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)) + ...
%e and also equals
%e 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)) + ...
%e (End)
%e From _Joerg Arndt_, Mar 08 2015: (Start)
%e There are a(4-1)=14 length-4 RGS as in the comment (dots denote zeros):
%e 01: [ . . . . ]
%e 02: [ . . . 1 ]
%e 03: [ . . 1 . ]
%e 04: [ . . 1 1 ]
%e 05: [ . 1 . . ]
%e 06: [ . 1 . 1 ]
%e 07: [ . 1 . 2 ]
%e 08: [ . 1 1 . ]
%e 09: [ . 1 1 1 ]
%e 10: [ . 1 1 2 ]
%e 11: [ . 1 2 . ]
%e 12: [ . 1 2 1 ]
%e 13: [ . 1 2 2 ]
%e 14: [ . 1 2 3 ]
%e (End)
%p T := proc(n, k) option remember; local j;
%p if k=n then 1
%p elif k>n then 0
%p else (k+1)*T(n-1, k) + add(T(n-1, j), j=k..n)
%p fi end:
%p A047970 := n -> T(n,0);
%p seq(A047970(n), n=0..24); # _Peter Luschny_, May 14 2014
%t a[ n_] := SeriesCoefficient[ ((1 - x) Sum[ x^k / (1 - (k + 2) x), {k, 0, n}]), {x, 0, n}]; (* _Michael Somos_, Jul 09 2014 *)
%o (Sage)
%o def A074664():
%o T = []; n = 0
%o while True:
%o T.append(1)
%o yield T[0]
%o for k in (0..n):
%o T[k] = (k+1)*T[k] + add(T[j] for j in (k..n))
%o n += 1
%o a = A074664()
%o [next(a) for n in range(25)] # _Peter Luschny_, May 13 2014
%o (PARI) /* From o.g.f. (_Paul D. Hanna_, Jul 20 2014) */
%o {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)}
%o for(n=0, 25, print1(a(n), ", "))
%o (PARI) /* From o.g.f. (_Paul D. Hanna_, Jul 22 2014) */
%o {a(n)=polcoeff( sum(m=0, n, x^m/((1-m*x)*(1-(m+1)*x +x*O(x^n)))), n)}
%o for(n=0, 25, print1(a(n), ", "))
%Y Antidiagonal sums of A085388 (beginning with the second antidiagonal) and A047969.
%Y Partial sums are in A026898, A003101. First differences A112532.
%Y Cf. A112531, A089246, A242431, A101494.
%K nonn
%O 0,2
%A _Alford Arnold_, Dec 11 1999