A102038 -id:A102038 - cp's OEIS frontend

A336070 Number of inversion sequences avoiding the vincular pattern 10-0 (or 10-1).

1, 1, 2, 6, 23, 106, 567, 3440, 23286, 173704, 1414102, 12465119, 118205428, 1199306902, 12958274048, 148502304614, 1798680392716, 22953847041950, 307774885768354, 4325220458515307, 63563589415836532, 974883257009308933, 15575374626562632462, 258780875395778033769, 4464364292401926006220

Offset: 0

Michael De Vlieger, Jul 07 2020

nonn

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 _Joerg Arndt_, Jan 20 2024: (Start)
There are a(4) = 23 weak ascent sequences (dots for zeros):
   1:  [ . . . . ]
   2:  [ . . . 1 ]
   3:  [ . . . 2 ]
   4:  [ . . . 3 ]
   5:  [ . . 1 . ]
   6:  [ . . 1 1 ]
   7:  [ . . 1 2 ]
   8:  [ . . 1 3 ]
   9:  [ . . 2 . ]
  10:  [ . . 2 1 ]
  11:  [ . . 2 2 ]
  12:  [ . . 2 3 ]
  13:  [ . 1 . . ]
  14:  [ . 1 . 1 ]
  15:  [ . 1 . 2 ]
  16:  [ . 1 1 . ]
  17:  [ . 1 1 1 ]
  18:  [ . 1 1 2 ]
  19:  [ . 1 1 3 ]
  20:  [ . 1 2 . ]
  21:  [ . 1 2 1 ]
  22:  [ . 1 2 2 ]
  23:  [ . 1 2 3 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..400
Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020. See p. 5, Table 1. Gives terms 1-10.
Beata Benyi, Anders Claesson, and Mark Dukes, Weak ascent sequences and related combinatorial structures, arXiv:2111.03159 [math.CO], (4-November-2021).

Cf. A000079, A000108, A000110, A022493, A091768, A102038, A113227, A263777, A328441, A336071, A336072.

Row sums of A369321.

b:= proc(n, i, t) option remember; `if`(n=0, 1,
      add(b(n-1, j, t+`if`(j>=i, 1, 0)), j=0..t+1))
    end:
a:= n-> b(n, -1$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 23 2024

b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, Sum[b[n - 1, j, t + If[j >= i, 1, 0]], {j, 0, t + 1}]];
a[n_] := b[n, -1, -1];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 18 2025, after Alois P. Heinz *)

\\ see formula (5) on page 18 of the Benyi/Claesson/Dukes reference
N=40;
M=matrix(N,N,r,c,-1);  \\ memoization
a(n,k)=
{
    if ( n==0 && k==0, return(1) );
    if ( k==0, return(0) );
    if ( n==0, return(0) );
    if ( M[n,k] != -1 , return( M[n,k] ) );
    my( s );
    s = sum( i=0, n, sum( j=0, k-1,
         (-1)^j * binomial(k-j,i) * binomial(i,j) * a( n-i, k-j-1 )) );
    M[n,k] = s;
    return( s );
}
for (n=0, N, print1( sum(k=1,n,a(n,k)),", "); );
\\ print triangle a(n,k), see A369321:
\\ for (n=0, N, for(k=0,n, print1(a(n,k),", "); ); print(););
\\ Joerg Arndt, Jan 20 2024

a(0)=1 prepended and more terms from Joerg Arndt, Jan 20 2024

A096121 Number of full spectrum rook's walks on a (2 X n) board.

Original entry on oeis.org

2, 8, 60, 816, 17520, 550080, 23839200, 1365799680, 100053999360, 9127781913600, 1015061950425600, 135193044668774400, 21248464632595200000, 3891825697262043340800, 821745573997874093568000, 198152975926832672858112000, 54121124248225908770856960000, 16621698830590738881776812032000

Offset: 1

Hugo van der Sanden, Jul 22 2004

A rook must land on each square exactly once, but may start and end anywhere and may intersect its own path.

This also gives the number of ways to arrange n pairs of shoes in a row so that no left shoe is next to a right shoe from a different pair. - Jerrold Grossman, Jul 19 2024

			Tagging the squares on a (3 X 2) board with A,B,C/D,E,F, the 10 tours starting at A are ABCFDE, ABCFED, ABEDFC, ACBEDF, ACBEFD, ACFDEB, ADEBCF, ADEFCB, ADFCBE, ADFEBC. There are a similar 10 tours starting at each of the other 5 squares, so a(3) = 6 * 10 = 60.

Inspired by Leroy Quet in a Jul 05 2004 posting to the Seqfan mailing list.

Y. Cha, Closed form solutions of difference equations (2011) PhD Thesis, Florida State University, Example 5.1.1

Column 2 of A269565.

Cf. A096970 and references to "rook tours" or "rook walks".

a[1]=2; a[2]=8; a[n_]:= n*(n-1)*(a[n-1] + a[n-2]); Array[a,18] (* Stefano Spezia, Jul 19 2024 *)

D-finite with recurrence: a(n+1) = n*(n+1)*(a(n) + a(n-1)) for n > 1.
Further refinement gives: a(n+1) = 2*(n+1)! * Sum_{k=0..floor(n/2)} (P(n-k, k) * C(n-k, k) + P(n-k, k+1) * C(n-1-k, i)), where P(i,j) = i!/j!.
Conjecture: a(n) = 2*n!*A102038(n). - Mikhail Kurkov, Feb 07 2019

a(16)-a(18) from Stefano Spezia, Jul 19 2024

A104557 Triangle T, read by rows, such that the unsigned columns of the matrix inverse when read downwards equals the rows of T read backwards, with T(n,n)=1 and T(n,n-1) = floor((n+1)/2)*floor((n+2)/2).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 6, 6, 4, 1, 24, 24, 18, 6, 1, 120, 120, 96, 36, 9, 1, 720, 720, 600, 240, 72, 12, 1, 5040, 5040, 4320, 1800, 600, 120, 16, 1, 40320, 40320, 35280, 15120, 5400, 1200, 200, 20, 1, 362880, 362880, 322560, 141120, 52920, 12600, 2400, 300, 25, 1

Offset: 0

Paul D. Hanna, Mar 16 2005

Matrix inverse is A104558. Row sums form A102038. See A104559 for further formulas, where A104559(n,k) = T(n,k)/(n-k)!.

			Rows of T begin:
      1;
      1,     1;
      2,     2,     1;
      6,     6,     4,     1;
     24,    24,    18,     6,    1;
    120,   120,    96,    36,    9,    1;
    720,   720,   600,   240,   72,   12,   1;
   5040,  5040,  4320,  1800,  600,  120,  16,  1;
  40320, 40320, 35280, 15120, 5400, 1200, 200, 20, 1; ...
The matrix inverse A104558 begins:
   1;
  -1,  1;
   0, -2,  1;
   0,  2, -4,   1;
   0,  0,  6,  -6,   1;
   0,  0, -6,  18,  -9,   1;
   0,  0,  0, -24,  36, -12,   1;
   0,  0,  0,  24, -96,  72, -16, 1; ...

Cf. A104558, A104559, A102038.

T(n,k)=(n-k)!*binomial(n-(k\2),(k+1)\2)*binomial(n-((k+1)\2),k\2)

Formula: T(n,k) = (n-k)!*C(n-floor(k/2), floor((k+1)/2))*C(n-floor((k+1)/2), floor(k/2)).
Recurrence: T(n,k) = n*T(n-1,k) + T(n-2,k-2) for n >= k >= 2, with T(0,0) = T(1,0) = T(1,1) = 1.
T(n,0) = n!.
T(n,k) = T(n-1,k-1) + floor((k+2)/2)*T(n,k+1), T(0,0)=1, T(n,k)=0 for k > n or for k < 0. - Philippe Deléham, Dec 18 2006

A109139 Numerators associated with the continued fraction of the differences of consecutive prime numbers.

Original entry on oeis.org

1, 2, 5, 12, 53, 118, 525, 1168, 5197, 32350, 69897, 451732, 1876825, 4205382, 18698353, 116395500, 717071353, 1550538206, 10020300589, 41631740562, 93283781713, 601334430840, 2498621505073, 15593063461278, 127243129195297

Offset: 0

Giorgio Balzarotti, Aug 18 2005

The value of the continued fraction up to n is: R(n) = A(n)/B(n) where B(0) = 1, B(1) = a(1) *B(0), B(n) = a(n)* B(n - 1) + B(n-2) (n>=2).
From theory related to the continued fractions, we have:
- the continued fraction is a simple continued fraction (i.e., generated by integer positive numbers);
- the limit C0 (for n to infinity) exists, it is greater than 1 and is R(n) = A(n)/B(n) = C0 = 1.71010202343009...;
- the limit C0 is an irrational number;
- there is a unique simple continued fraction with limit C0;
- the generating number sequences of the simple continued fraction with limit C0 is unique;
- the sequence of generating numbers of the continued fraction (i.e., the difference of consecutive prime numbers and, consequently, the prime numbers) can be evaluated from C0 by:
a(0) = floor(C0), C1 = 1/(C0-a(0)), a(1) = floor(C1), C2 = 1/(C1-a(1)), ... a(n) = floor(Cn) ...;
- C0 satisfies the inequality: A(n)/B(n) - 1/B(n)^2 < C0 < A(n)/B(n) + 1/B(n)^2;
- this inequality allows us to evaluate the range of a(n+1), given A(n) and B(n);
- knowledge of A(n)/B(n) allows us to evaluate a(0), a(1) ..., a(n), i.e., the difference of consecutive prime numbers and, consequently, the prime numbers.
- The continued fraction derived from the sequences of consecutive prime number differences performs lower gradient w.r.t. the continued fraction based on prime sequence and it is therefore computationally easier to use.
The denominators B(n) are in A109140. Related sequences are D(n) = A(n) - B(n), S(n) = A(n) + B(n).

			n = 2, A(n) = A(2) = 5 because A(0) = 2-1 = 1, A(1) = (3-2) * A(0) + 1 = 2, A(2) = (5-3) * A(1) + 1 * A(0) = 5.

Cf. A001053, A003736, A001040, A102038, A109140.

A(0) = a(0), A(1) = a(1)*A(0) + 1, A(n) = a(n)*A(n - 1) + A(n-2) (n>=2) where a(0) = p(0) - 1, a(1) = p(1) - p(0), a(2) = p(2) - p(1) ..., a(n) = p(n) - p(n-1) where p(n) is the n-th prime number.

A336071 Number of inversion sequences avoiding the vincular pattern 1-01 (or 1-10).

Original entry on oeis.org

1, 2, 6, 23, 107, 584, 3655, 25790, 202495, 1750763

Offset: 1

Michael De Vlieger, Jul 07 2020

Juan S. Auli, Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020. See p. 5, Table 1. Gives terms 1-10.

Cf. A000079, A000110, A022493, A091768, A102038, A113227, A263777, A328441, A336070, A336072.

A336072 Number of inversion sequences avoiding the vincular pattern 2-01 (or 2-10).

Original entry on oeis.org

1, 2, 6, 24, 118, 680, 4460, 32634, 262536, 2296532

Offset: 1

Michael De Vlieger, Jul 07 2020

Juan S. Auli, Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020. See p. 5, Table 1. Gives terms 1-10.

Cf. A000079, A000110, A022493, A091768, A102038, A113227, A263777, A328441, A336070, A336071.

A347051 a(0) = 1, a(1) = 2; a(n) = n * (n+1) * a(n-1) + a(n-2).

Original entry on oeis.org

1, 2, 13, 158, 3173, 95348, 4007789, 224531532, 16170278093, 1455549559902, 160126621867313, 21138169636045218, 3297714589844921321, 600205193521411725640, 126046388354086307305721, 30251733410174235165098680, 8228597533955746051214146681, 2517981097123868465906693983066

Offset: 0

Ilya Gutkovskiy, Aug 13 2021

a(n) is the denominator of fraction equal to the continued fraction [0; 2, 6, 12, 20, 30, ..., n*(n+1)].

			a(1) =    2 because 1/(1*2)                               = 1/2.
a(2) =   13 because 1/(1*2 + 1/(2*3))                     = 6/13.
a(3) =  158 because 1/(1*2 + 1/(2*3 + 1/(3*4)))           = 73/158.
a(4) = 3173 because 1/(1*2 + 1/(2*3 + 1/(3*4 + 1/(4*5)))) = 1466/3173.

Cf. A001040, A001046, A002378, A036246, A071896, A102038, A346960, A347052.

a[0] = 1; a[1] = 2; a[n_] := a[n] = n (n + 1) a[n - 1] + a[n - 2]; Table[a[n], {n, 0, 17}]
Table[Denominator[ContinuedFractionK[1, k (k + 1), {k, 1, n}]], {n, 0, 17}]

a(n) ~ c * n^(2*n + 2) / exp(2*n), where c = 6.9478401587876967481571909904361736371398357108358019737901443045685048723... - Vaclav Kotesovec, Aug 14 2021

A336282 Number of heapable permutations of length n.

Original entry on oeis.org

1, 1, 1, 2, 5, 17, 71, 359, 2126, 14495, 111921, 966709, 9243208, 96991006, 1108710232, 13719469288, 182771488479, 2608852914820, 39730632184343, 643142016659417, 11029056364607167, 199761704824369543, 3811075717138755529, 76396392619230455931, 1605504868758470118493

Offset: 0

Benjamin Chen, Michael Y. Cho, Mario Tutuncu-Macias, Tony Tzolov, Jul 15 2020

nonn

A permutation is heapable if there exists a binary heap with the numbers added to the heap in the order of the permutation, and you may not change already placed numbers.
We provide two programs: The first, given below in the Python section, demonstrates the notion of 'heapable'. It is, however, of big O roughly n!. A second program, given in the Links section, groups heapable sequences into equivalence classes using an extended signature. The big O of this algorithm is roughly 3^n.
We notice that the number of equivalence classes at each step appears to follow A001006, but this has not yet been proven.

			For n=4, the 5 heapable sequences are (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3). Notice that (1,4,3,2) is missing.

Mario Tutuncu-Macias, Table of n, a(n) for n = 0..29
John Byers, Brent Heeringa, Michael Mitzenmacher, and Georgios Zervas, Heapable Sequences and Subsequences, arXiv:1007.2365 [cs.DS], 2010.
G. Istrate and C. Bonchis, Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process, arXiv:1502.02045 [math.CO], 2015.

Cf. A056971, A000111, A102038, A001006.

from itertools import permutations
def isHeapable(seq):
    sig = [0 for _ in range(len(seq))]
    sig[0] = 2
    for j in seq[1:]:
        sig[j] = 2
        while j > -1:
            j -= 1
            if sig[j] > 0:
                sig[j] -= 1
                break
        if j == -1:
            return False
    return True
def A336282(n):
    if n == 0: return 1
    x = permutations(range(n))
    return sum(1 for h in x if isHeapable(h))
print([A336282(n) for n in range(12)])

class EquivalenceClass:
    def _init_(self, example, count):
        self.example = example
        self.count = count
def extendedSig(seq, key, n):
    key = eval(key)
    top = seq.index(n - 1)
    attachement = top - 1
    for i in range(attachement, -1, -1):
        if key[i] > 0:
            key[i] -= 1
            key.insert(top, 2)
            return key
e_list = [{"[2]": EquivalenceClass([0], 1)}, {}]
def A(n):
    if n < 2:
        return 1
    el_0 = e_list[0]
    el = e_list[1]
    for key in el_0:
        seq = el_0[key].example
        for j in range(n - 1, 0, -1):
            p = seq[0:j] + [n - 1] + seq[j:]
            res = extendedSig(p, key, n)
            if not res:
                break
            s = str(res)
            c = el_0[key].count
            if s in el:
                el[s].count += c
            else:
                el[s] = EquivalenceClass(p, c)
    e_list[0] = el
    e_list[1] = {}
    return sum(el[key].count for key in el)
def A336282List(size):
    return [A(k) for k in range(size)]
print(A336282List(12))

Proven bounds:
A000111(n) <= a(n).
a(n) <= A102038(n-1) for n>1.

a(14) from Seiichi Manyama, Jul 20 2020
a(15)-a(20) from Mario Tutuncu-Macias, Jul 22 2020
Extended beyond a(20) by Mario Tutuncu-Macias, Oct 27 2020

cp's OEIS Frontend

A336070 Number of inversion sequences avoiding the vincular pattern 10-0 (or 10-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A096121 Number of full spectrum rook's walks on a (2 X n) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A104557 Triangle T, read by rows, such that the unsigned columns of the matrix inverse when read downwards equals the rows of T read backwards, with T(n,n)=1 and T(n,n-1) = floor((n+1)/2)*floor((n+2)/2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A109139 Numerators associated with the continued fraction of the differences of consecutive prime numbers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A336071 Number of inversion sequences avoiding the vincular pattern 1-01 (or 1-10).

Views

Author

Keywords

Links

Crossrefs

A336072 Number of inversion sequences avoiding the vincular pattern 2-01 (or 2-10).

Views

Author

Keywords

Links

Crossrefs

A347051 a(0) = 1, a(1) = 2; a(n) = n * (n+1) * a(n-1) + a(n-2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A336282 Number of heapable permutations of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula

Extensions