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

%I #36 Jan 24 2024 08:41:13

%S 1,1,2,6,23,106,567,3440,23286,173704,1414102,12465119,118205428,

%T 1199306902,12958274048,148502304614,1798680392716,22953847041950,

%U 307774885768354,4325220458515307,63563589415836532,974883257009308933,15575374626562632462,258780875395778033769,4464364292401926006220

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

%C From _Joerg Arndt_, Jan 20 2024: (Start)

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

%C 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.

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

%C (End)

%H Alois P. Heinz, <a href="/A336070/b336070.txt">Table of n, a(n) for n = 0..400</a>

%H Juan S. Auli and Sergi Elizalde, <a href="https://arxiv.org/abs/2003.11533">Wilf equivalences between vincular patterns in inversion sequences</a>, arXiv:2003.11533 [math.CO], 2020. See p. 5, Table 1. Gives terms 1-10.

%H Beata Benyi, Anders Claesson, and Mark Dukes, <a href="https://arxiv.org/abs/2111.03159">Weak ascent sequences and related combinatorial structures</a>, arXiv:2111.03159 [math.CO], (4-November-2021).

%e From _Joerg Arndt_, Jan 20 2024: (Start)

%e There are a(4) = 23 weak ascent sequences (dots for zeros):

%e 1: [ . . . . ]

%e 2: [ . . . 1 ]

%e 3: [ . . . 2 ]

%e 4: [ . . . 3 ]

%e 5: [ . . 1 . ]

%e 6: [ . . 1 1 ]

%e 7: [ . . 1 2 ]

%e 8: [ . . 1 3 ]

%e 9: [ . . 2 . ]

%e 10: [ . . 2 1 ]

%e 11: [ . . 2 2 ]

%e 12: [ . . 2 3 ]

%e 13: [ . 1 . . ]

%e 14: [ . 1 . 1 ]

%e 15: [ . 1 . 2 ]

%e 16: [ . 1 1 . ]

%e 17: [ . 1 1 1 ]

%e 18: [ . 1 1 2 ]

%e 19: [ . 1 1 3 ]

%e 20: [ . 1 2 . ]

%e 21: [ . 1 2 1 ]

%e 22: [ . 1 2 2 ]

%e 23: [ . 1 2 3 ]

%e (End)

%p b:= proc(n, i, t) option remember; `if`(n=0, 1,

%p add(b(n-1, j, t+`if`(j>=i, 1, 0)), j=0..t+1))

%p end:

%p a:= n-> b(n, -1$2):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Jan 23 2024

%o (PARI) \\ see formula (5) on page 18 of the Benyi/Claesson/Dukes reference

%o N=40;

%o M=matrix(N,N,r,c,-1); \\ memoization

%o a(n,k)=

%o {

%o if ( n==0 && k==0, return(1) );

%o if ( k==0, return(0) );

%o if ( n==0, return(0) );

%o if ( M[n,k] != -1 , return( M[n,k] ) );

%o my( s );

%o s = sum( i=0, n, sum( j=0, k-1,

%o (-1)^j * binomial(k-j,i) * binomial(i,j) * a( n-i, k-j-1 )) );

%o M[n,k] = s;

%o return( s );

%o }

%o for (n=0, N, print1( sum(k=1,n,a(n,k)),", "); );

%o \\ print triangle a(n,k), see A369321:

%o \\ for (n=0, N, for(k=0,n, print1(a(n,k),", "); ); print(););

%o \\ _Joerg Arndt_, Jan 20 2024

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

%Y Row sums of A369321.

%K nonn

%O 0,3

%A _Michael De Vlieger_, Jul 07 2020

%E a(0)=1 prepended and more terms from _Joerg Arndt_, Jan 20 2024