login
Antidiagonal sums of nexus numbers (A047969).
23

%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&amp;lpg=PA242&amp;vq=242&amp;hl=de&amp;pg=PA242#v=onepage&amp;q&amp;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