Displaying 1-10 of 22 results found.
Number of length n inversion sequences avoiding the patterns 110 and 120.
+10
29
1, 1, 2, 6, 22, 92, 423, 2091, 10950, 60120, 343453, 2029809, 12354661, 77168197, 493189283, 3217459119, 21382723456, 144518555231, 991885282987, 6904454991721, 48691257834999, 347542736059492, 2508603139285095, 18297609829743478, 134772911886028731
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i <= e_j > e_k and e_i > e_k. This is the same as the set of length n inversion sequences avoiding 110 and 120.
EXAMPLE
The length 4 inversion sequences avoiding (110,120) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0100, 0101, 0102, 0103, 0111, 0112, 0113, 0121, 0122, 0123.
CROSSREFS
Cf. A000108, A057552, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 010 and 120.
+10
28
1, 1, 2, 5, 15, 52, 201, 845, 3801, 18089, 90316, 470010, 2536077, 14127741, 80966690, 475979359, 2863157581, 17585971037, 110095460224, 701418693025, 4541497543092, 29847982448766, 198913925919741, 1342890255133042, 9176456969273844, 63422002415068463
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i < e_j and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010 and 120.
EXAMPLE
The length 4 inversion sequences avoiding (010, 120) are 0000, 0001, 0002, 0003, 0011, 0012, 0013, 0021, 0022, 0023, 0111, 0112, 0113, 0122, 0123.
CROSSREFS
Cf. A000108, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 110, 210, 120, and 010.
+10
27
1, 1, 2, 5, 15, 51, 189, 746, 3091, 13311, 59146, 269701, 1256820, 5966001, 28773252, 140695923, 696332678, 3483193924, 17589239130, 89575160517, 459648885327, 2374883298183, 12346911196912, 64555427595970, 339276669116222, 1791578092326881, 9501960180835998
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_j > e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010, 110, 120, and 210.
It can be shown that this sequence also counts the length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i <> e_j >=e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010, 100, 120, and 210.
EXAMPLE
The length 3 inversion sequences avoiding (010, 110, 120, 210) are 000, 001, 002, 011, 012.
The length 4 inversion sequences avoiding (010, 110, 120, 210) are 0000, 0001, 0002, 0003, 0011, 0012, 0013, 0021, 0022, 0023, 0111, 0112, 0113, 0122, 0123.
CROSSREFS
Cf. A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 000 and 100.
+10
27
1, 1, 2, 5, 16, 60, 260, 1267, 6850, 40572, 260812, 1805646, 13377274, 105487540, 881338060, 7770957903, 72060991394, 700653026744, 7123871583656, 75561097962918, 834285471737784, 9570207406738352, 113855103776348136, 1402523725268921870, 17863056512845724036, 234910502414771617316, 3185732802058088068444, 44501675392317774477088
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i >= e_j = e_k. This is the same as the set of length n inversion sequences avoiding 000 and 100.
FORMULA
The length 4 inversion sequences avoiding (000,100) are 0011, 0012, 0013, 0021, 0022, 0023, 0101, 0102, 0103, 0110, 0112, 0113, 0120, 0121, 0122, 0123.
MAPLE
b:= proc(n, i, m, s) option remember; `if`(n=0, 1, add(
`if`(j in s, 0, b(n-1, i+1, max(m, j),
`if`(j<=m, s union {j}, s))), j=1..i))
end:
a:= n-> b(n, 1, 0, {}):
MATHEMATICA
b[n_, i_, m_, s_List] := b[n, i, m, s] = If[n == 0, 1, Sum[If[MemberQ[s, j], 0, b[n-1, i+1, Max[m, j], If[j <= m, s ~Union~ {j}, s]]], {j, 1, i}] ]; a[n_] := b[n, 1, 0, {}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jul 10 2017, after Alois P. Heinz *)
CROSSREFS
Cf. A000108, A057552, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 102 and 201.
+10
26
1, 1, 2, 6, 22, 87, 354, 1465, 6154, 26223, 113236, 494870, 2185700, 9743281, 43784838, 198156234, 902374498, 4131895035, 19012201080, 87864535600, 407664831856, 1898184887679, 8867042353912, 41543375724751, 195164372948152, 919138464708907, 4338701289961694, 20524046955770940
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i > e_j < e_k and e_i <> e_k. This is the same as the set of length n inversion sequences avoiding 102 and 201.
FORMULA
G.f.: (-8*x^4 + 18*x^3 - 10*x^2 - 8*x + 4 + 2 * (2*x - 1) * (x^2 - 2*x + 2) * ((5*x - 1)*(x - 1))^(1/2)) / (4*x * (2*x - 1) * (x - 1) * (x - 2)^2). - Benjamin Testart, Jul 12 2024
EXAMPLE
The length 4 inversion sequences avoiding (102, 201) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0100, 0101, 0110, 0111, 0112, 0113, 0120, 0121, 0122, 0123
CROSSREFS
Cf. A000108, A057552, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 110, 120, and 021.
+10
25
1, 1, 2, 6, 20, 68, 233, 805, 2807, 9879, 35073, 125513, 452389, 1641029, 5986994, 21954974, 80884424, 299233544, 1111219334, 4140813374, 15478839554, 58028869154, 218123355524, 821908275548, 3104046382352, 11747506651600, 44546351423300, 169227201341652
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i <= e_j > e_k and e_i <> e_k. This is the same as the set of length n inversion sequences avoiding 110, 120, and 021.
FORMULA
a(n) = 1 + Sum_{t=1..n-1} Sum_{k=t+2..n+1} (k-t-1)*(k-t)/(n-t+1) * binomial(2n-k-t+1,n-k+1).
Conjecture: a(n) = C_{n+1}-Sum_{i=1..n} C_i where C_i is the i-th Catalan number, binomial(2i,i)/(i+1).
Assuming the conjecture a(n) ~ (64/3)*4^n/((4*n+7)^(3/2)*sqrt(Pi)). - Peter Luschny, Feb 24 2017 G.f.: (sqrt(1-4*x)+2*x-1)*(2*x-1)/(2*(1-x)*x^2). (End)
D-finite with recurrence: (n+2)*a(n) +(-7*n-4)*a(n-1) +2*(7*n-5)*a(n-2) +4*(-2*n+3)*a(n-3)=0. - R. J. Mathar, Feb 21 2020
EXAMPLE
The length 4 inversion sequences avoiding (110, 120, 021) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0022, 0023, 0100, 0101, 0102, 0103, 0111, 0112, 0113, 0122, 0123.
MAPLE
a:= proc(n) option remember; `if`(n<3, n!,
((5*n^2-6*n-2)*a(n-1)-(4*n-2)*(n-1)*a(n-2))/(n^2-4))
end:
MATHEMATICA
a[n_] := 1 + Sum[(k - t - 1) (k - t)/(n - t + 1)* Binomial[2 n - k - t + 1, n - k + 1], {t, n - 1}, {k, t + 2, n + 1}]; Array[a, 28, 0] (* Robert G. Wilson v, Feb 25 2017 *)
CROSSREFS
Cf. A000108, A114277, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 100, 110, 120, 201, and 210.
+10
25
1, 1, 2, 6, 21, 81, 332, 1420, 6266, 28318, 130412, 609808, 2887582, 13818590, 66726628, 324713196, 1590853485, 7840315329, 38843186366, 193342353214, 966409013021, 4848846341569, 24412146213116, 123290812268404, 624448756434476, 3171046361310556
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i > e_k. This is the same as the set of length n inversion sequences avoiding 100, 110, 120, 201, and 210.
FORMULA
a(n) = (1/n)*Sum_{m=1..n} m*Sum_{k=0..n-m} C(k,n-m-k)*C(n+k-1,k), n>0, a(0)=1. - Vladimir Kruchinin, Mar 26 2019 a(n) ~ 3^(3*n + 1/2) / (2^(7/2) * sqrt(Pi) * n^(3/2) * 5^(n - 1/2)). - Vaclav Kotesovec, Oct 07 2021 Conjecture: a(n) = (v_n + v_{n+1})/2 for n > 0 with a(0) = 1 where we start with vector v of fixed length m with elements v_i = 1 and for i=1..m-2, for j=i+2..m apply v_j := Sum_{k=0..2} v_{j-k}. - Mikhail Kurkov, Sep 03 2024
EXAMPLE
The length 4 inversion sequences avoiding (100, 110, 120, 201, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0101, 0102, 0103, 0111, 0112, 0113, 0121, 0122, 0123.
MAPLE
a:= proc(n) option remember; `if`(n<3, n!,
((n-1)*(17*n-28)*a(n-1) +(49*n^2-185*n+196)*a(n-2)
+(3*(3*n-7))*(3*n-8)*a(n-3)) / (5*n*(n-1)))
end:
MATHEMATICA
a[n_] := a[n] = If[n < 3, n!, (((n - 1)*(17*n - 28)*a[n-1] + (49*n^2 - 185*n + 196)*a[n-2] + (3*(3*n - 7))*(3*n - 8)*a[n-3]) / (5*n*(n - 1)))]; Array[a, 30, 0] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *) Join[{1}, Table[(1/n)*Sum[m*Sum[Binomial[k, n-m-k]*Binomial[n+k-1, k], {k, 0, n-m}], {m, 1, n}], {n, 1, 30}]] (* G. C. Greubel, Mar 29 2019 *)
PROG
(Maxima)
a(n):=if n=0 then 1 else sum(m*sum(binomial(k, n-m-k)*binomial(n+k-1, k), k, 0, n-m), m, 1, n)/n /* Vladimir Kruchinin, Mar 26 2019 */ (PARI) my(x='x+O('x^30)); Vec(round(3/(4-4*sin(asin((27*x+11)/16)/3)))) \\ G. C. Greubel, Mar 29 2019 (Magma) I:=[6, 21, 81]; [1, 1, 2] cat [n le 3 select I[n] else ( (n+1)*(17*n+6)*Self(n-1) +(49*n^2+11*n+22)*Self(n-2) +3*(3*n-1)*(3*n-2)*Self(n-3) )/(5*(n+2)*(n+1)) : n in [1..30]]; // G. C. Greubel, Mar 29 2019 (Sage) [1] +[(1/n)*(sum(sum(k*binomial(j, n-k-j)*binomial(n+j-1, j) for j in (0..n-k)) for k in (1..n))) for n in (1..30)] # G. C. Greubel, Mar 29 2019
CROSSREFS
Cf. A000108, A057552, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 000 and 010.
+10
24
1, 1, 2, 4, 10, 29, 95, 345, 1376, 5966, 27886, 139608, 744552, 4210191, 25140790, 157981820, 1041480482, 7183374125, 51711299169, 387683162541, 3020997261596, 24424884853963, 204559337781097, 1772011400733378, 15855597322378302, 146360032952969570
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_j >= e_k and e_i = e_k. This is the same as the set of length n inversion sequences avoiding 000 and 010.
EXAMPLE
For n=3, the inversion sequences are 001, 002, 011, 012.
For n=4, the inversion sequences are 0011, 0012, 0013, 0021, 0022, 0023, 0112, 0113, 0122, 0123.
CROSSREFS
Cf. A263777, A263778, A263779, A263780, A279551, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 101, 102, 201, and 210.
+10
24
1, 1, 2, 6, 21, 77, 287, 1079, 4082, 15522, 59280, 227240, 873886, 3370030, 13027730, 50469890, 195892565, 761615285, 2965576715, 11563073315, 45141073925, 176423482325, 690215089745, 2702831489825, 10593202603775, 41550902139551, 163099562175851
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i > e_j <> e_k. This is the same as the set of length n inversion sequences avoiding 101, 102, 201, and 210.
It is conjectured that a_n also counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i < e_j > e_k and e_i <> e_k. This is the same as the set of length n inversion sequences avoiding 021 and 120.
FORMULA
a(n) = 1 + Sum_{i=1..n-1} binomial(2i, i-1).
G.f.: (1-4*x+sqrt(-16*x^3+20*x^2-8*x+1))/(2*(x-1)*(4*x-1)).
D-finite with recurrence: n*a(n) +(-7*n+6)*a(n-1) +2*(7*n-13)*a(n-2) +4*(-2*n+5)*a(n-3)=0. - R. J. Mathar, Feb 21 2020
EXAMPLE
The length 4 inversion sequences avoiding (101, 102, 201, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0100, 0110, 0111, 0112, 0113, 0120, 0121, 0122, 0123.
The length 4 inversion sequences avoiding (021, 120) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0022, 0023, 0100, 0101, 0102, 0103, 0110, 0111, 0112, 0113, 0122, 0123.
MAPLE
a:= proc(n) option remember; `if`(n<3, 1+n*(n-1)/2,
((5*n^2-12*n+6)*a(n-1)-(4*n^2-10*n+6)*a(n-2))/((n-2)*n))
end:
MATHEMATICA
a[n_] := 1 + Sum[Binomial[2i, i-1], {i, 0, n-1}];
CROSSREFS
Cf. A000108, A057552, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Number of length n inversion sequences avoiding the patterns 110, 210, 120, 201, and 010.
+10
23
1, 1, 2, 5, 15, 50, 178, 663, 2552, 10071, 40528, 165682, 686151, 2872576, 12137278, 51690255, 221657999, 956265050, 4147533262, 18074429421, 79102157060, 347519074010, 1532070899412, 6775687911920, 30052744139440, 133649573395725, 595816470717728
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_j <> e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010, 110, 120, 201, and 210.
It can be shown that this sequence also counts the length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i <> e_j and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010, 100, 120, 201, and 210.
FORMULA
a(n) ~ c * d^n / (sqrt(Pi) * n^(3/2)), where d = 4.730576939379622099763633264641101585205420756515858657461873... is the greatest real root of the equation 4 - 12*d + 4*d^2 - 24*d^3 + 5*d^4 = 0 and c = 0.3916760466183576202289779130261876915536170330427700961416097... is the positive real root of the equation -5 - 64*c^2 - 33728*c^4 + 209664*c^6 + 93184*c^8 = 0. - Vaclav Kotesovec, Jul 12 2018 D-finite with recurrence: 45*n*(n-1)*a(n) -4*(n-1)*(49*n-66)*a(n-1) +2*(-25*n^2+157*n-264)*a(n-2) +2*(-70*n^2+445*n-714)*a(n-3) -4*(n-6)*(n-13)*a(n-4) -4*(n-6)*(2*n-17)*a(n-5) +8*(n-6)*(n-7)*a(n-6)=0. - R. J. Mathar, Feb 21 2020
EXAMPLE
The length 3 inversion sequences avoiding (110, 210, 120, 201, 010) are 000, 001, 002, 011, 012.
The length 4 inversion sequences avoiding (110, 210, 120, 201, 010) are 0000, 0001, 0002, 0003, 0011, 0012, 0013, 0021, 0022, 0023, 0111, 0112, 0113, 0122, 0123.
MAPLE
a:= proc(n) option remember; `if`(n<4, [1, 1, 2, 5][n+1],
((12*(n-1))*(182*n^3-1659*n^2+4628*n-3756)*a(n-1)
-(4*(91*n^4-1057*n^3+3812*n^2-4046*n-906))*a(n-2)
+(6*(n-4))*(182*n^3-1659*n^2+4901*n-4630)*a(n-3)
-(4*(n-4))*(n-5)*(91*n^2-511*n+690)*a(n-4))
/(5*n*(n-1)*(91*n^2-693*n+1292)))
end:
MATHEMATICA
a[n_] := a[n] = If[n < 4, {1, 1, 2, 5}[[n + 1]], ((12*(n - 1))*(182*n^3 - 1659*n^2 + 4628*n - 3756)*a[n - 1] - (4*(91*n^4 - 1057*n^3 + 3812*n^2 - 4046*n - 906))*a[n - 2] + (6*(n - 4))*(182*n^3 - 1659*n^2 + 4901*n - 4630)*a[n - 3] - (4*(n - 4))*(n - 5)*(91*n^2 - 511*n + 690)*a[n - 4]) / (5*n*(n - 1)*(91*n^2 - 693*n + 1292))]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)
PROG
(PARI)
seq(N) = my(x='x+O('x^N)); Vec(1+serreverse((-x^3+x^2+x)/(2*x^2+3*x+1)));
CROSSREFS
Cf. A263777, A263778, A263779, A263780, A279551, A279552, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
Search completed in 0.079 seconds
| 