A264173 -id:A264173 - cp's OEIS frontend

A264319 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive pattern 3412; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2-1)), read by rows.

1, 1, 2, 6, 23, 1, 110, 10, 631, 88, 1, 4223, 794, 23, 32301, 7639, 379, 1, 277962, 79164, 5706, 48, 2657797, 885128, 84354, 1520, 1, 27954521, 10657588, 1266150, 38452, 89, 320752991, 137752283, 19621124, 869740, 5461, 1, 3987045780, 1904555934, 316459848

Offset: 0

Alois P. Heinz, Nov 11 2015

Pattern 2143 gives the same triangle.

			T(4,1) = 1: 3412.
T(5,1) = 10: 14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.
T(6,2) = 1: 563412.
T(7,2) = 23: 1674523, 2674513, 3674512, 4673512, 5614723, 5624713, 5634127, 5634712, 5673412, 5714623, 5724613, 5734126, 5734612, 6573412, 6714523, 6724513, 6734125, 6734512, 6735124, 6745123, 6745132, 6745231, 7563412.
T(8,3) = 1: 78563412.
T(9,3) = 48: 189674523, 289674513, 389674512, ..., 896745132, 896745231, 978563412.
Triangle T(n,k) begins:
00 :       1;
01 :       1;
02 :       2;
03 :       6;
04 :      23,      1;
05 :     110,     10;
06 :     631,     88,     1;
07 :    4223,    794,    23;
08 :   32301,   7639,   379,    1;
09 :  277962,  79164,  5706,   48;
10 : 2657797, 885128, 84354, 1520, 1;

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A113229, A264320, A264321, A264322, A264323, A264324, A264325, A264326, A264327, A264328, A264329.
Row sums give A000142.
Cf. A004526, A061206, A264173 (pattern 1324).

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(expand(
       b(u+j-1, o-j, j)*`if`(t<0 and j<1-t, x, 1)), j=1..o)+
      add(b(u-j, o+j-1, `if`(t>0 and j>t, t-j, 0)), j=1..u))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..14);

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[Expand[b[u+j-1, o-j, j]*If[t<0 && j<1-t, x, 1]], {j, 1, o}] + Sum[b[u-j, o+j-1, If[t>0 && j>t, t-j, 0]], {j, 1, u}]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jan 16 2017, translated from Maple_ *)

Sum_{k>0} k * T(n,k) = ceiling((n-3)*n!/4!) = A061206(n-3) (for n>3).

A061206 a(n) = total number of occurrences of the consecutive pattern 1324 in all permutations of [n+3].

Original entry on oeis.org

1, 10, 90, 840, 8400, 90720, 1058400, 13305600, 179625600, 2594592000, 39956716800, 653837184000, 11333177856000, 207484333056000, 4001483566080000, 81096733605888000, 1723305589125120000, 38318206628782080000, 889833909490606080000, 21543347282404147200000

Offset: 1

Melvin J. Knight (knightmj(AT)juno.com), May 30 2001

nonn

a(n) is the number of sequences of n+3 balls colored with at most n colors such that exactly four balls are the same color as some other ball in the sequence. - Jeremy Dover, Sep 27 2017

			a(4)=840 because 4*(7!)/24 = 4*7*6*5 = 840.

Vincenzo Librandi, Table of n, a(n) for n = 1..300
Milan Janjić, Enumerative Formulas for Some Functions on Finite Sets.

Cf. A000142, A001286, A001339, A001563, A005990, A264173.

Cf. A001620, A091725, A099285.

[n*Factorial(n+3)/24: n in [1..20]]; // Vincenzo Librandi, Oct 11 2011

a := n -> n!*binomial(-n,4): seq(a(n),n=1..20); # Peter Luschny, Apr 29 2016

Array[# (# + 3)!/24 &, 20] (* or *) Array[#!*Binomial[-#, 4] &, 20] (* Michael De Vlieger, Sep 30 2017 *)

a(n) = n*(n+3)!/24; \\ Altug Alkan, Oct 08 2017

[binomial(n,4)*factorial (n-3) for n in range(4, 21)] # Zerinvary Lajos, Jul 07 2009

a(n) = n*(n+3)!/24.
If we define f(n,i,x) = Sum_{k=i..n} Sum_{j=i..k} binomial(k,j)*Stirling1(n,k)*Stirling2(j,i) * x^(k-j), then a(n-3) = (-1)^n*f(n,4,-2), (n >= 4). - Milan Janjic, Mar 01 2009
E.g.f.: x/(1-x)^5. (This was initiated by e-mail exchange with Gary Detlefs.) - Wolfdieter Lang, May 28 2010
a(n) = ((n+4)!/6) * Sum_{k=1..n} (k+2)!/(k+4)!. - Gary Detlefs, Aug 05 2010
a(n) = Sum_{k>0} k * A264173(n+3,k). - Alois P. Heinz, Nov 06 2015
a(n) = n!*binomial(-n,4). - Peter Luschny, Apr 29 2016
From Amiram Eldar, Sep 24 2022: (Start)
Sum_{n>=1} 1/a(n) = 118/3 - 16*e - 4*gamma + 4*Ei(1), where gamma is Euler's constant (A001620) and Ei(1) is the exponential integral at 1 (A091725).
Sum_{n>=1} (-1)^(n+1)/a(n) = 2/3 - 8/e + 4*gamma - 4*Ei(-1), where -Ei(-1) is the negated exponential integral at -1 (A099285). (End)

More terms from Jason Earls, Jun 12 2001
Corrected by Zerinvary Lajos, Jul 07 2009
More precise definition from Alois P. Heinz, Nov 06 2015

A113228 a(n) is the number of permutations of [1..n] that avoid the consecutive pattern 1324 (equally, the permutations that avoid 4231).

Original entry on oeis.org

1, 1, 2, 6, 23, 110, 632, 4229, 32337, 278204, 2659223, 27959880, 320706444, 3985116699, 53328433923, 764610089967, 11693644958690, 190015358010114, 3269272324528547, 59373764638615449, 1135048629795612125, 22783668363316052016, 479111084084119883217

Offset: 0

David Callan, Oct 19 2005

nonn

			In 24135, the entries 2435 are in relative order 1324 but they do not occur consecutively and 24135 avoids the consecutive 1324 pattern.

Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 0..60 from Ray Chandler)
Andrew Baxter, Brian Nakamura, and Doron Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
Colin Defant, Noah Kravitz, and Nathan Williams, The Ungar Games, arXiv:2302.06552 [math.CO], 2023.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Cf. A113229, A117156, A117158, A117226, A201692, A201693, A231166.

Column k=0 of A264173.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
       add(b(u-j, o+j-1, `if`(t>0 and j b(n, 0, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 07 2013

Clear[u, v, w]; w[0]=1; w[1]=1;w[2]=2; w[n_]/;n>=3 := w[n] = Sum[w[n, a], {a, n}]; w[1, 1] = w[2, 1] = w[2, 2] = 1; w[n_, a_]/;n>=3 && 1<=a<=n := Sum[u[n, a, b], {b, a+1, n}] + v[n, a]; v[1, 1]=1; v[n_, a_]/;n>=2 && a==1 := 0; v[n_, a_]/;n>=2 && 2<=a<=n := wCumulative[n-1, a-1]; wCumulative[n_, k_]/;Not[1<=k<=n] := 0; wCumulative[n_, k_]/;1<=k<=n := wCumulative[n, k] = Sum[w[n, a], {a, k}]; u[n_, a_, b_]/;Not[1<=a=4 && 1<=a0 && j < t, -j, 0]], {j, 1, u}] + Sum[b[u+j-1, o-j, j], {j, 1, If[t<0, Min[-t-1, o], o]}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 19 2017, after Alois P. Heinz *)

In the recurrence coded in Mathematica below, w[n, a] = #1324-avoiding permutations on [n] with first entry a; u[n, a, b] is the number that start with an ascent a=2). The main sum for u[n, a, b] counts by length k of the longest initial increasing subsequence. The cases k=2, k=3, k>=4 are considered separately.

a(n) ~ c * d^n * n!, where d = 0.9558503134742499886507376383060906722796..., c = 1.15104449887019137479444895134035262624... . - Vaclav Kotesovec, Aug 23 2014

A264174 Number of permutations of [n] with exactly one occurrence of the consecutive pattern 1324.

Original entry on oeis.org

1, 10, 86, 782, 7571, 78726, 882997, 10657118, 137977980, 1910131680, 28178987795, 441555002430, 7326966011380, 128386409972224, 2369404379818067, 45945570232645676, 934057289766619391, 19867567809865839562, 441307130768553551181, 10218971845916640741804

Offset: 4

Alois P. Heinz, Nov 06 2015

nonn

			a(4) = 1: 1324.
a(5) = 10: 12435, 13245, 13254, 14253, 14352, 21435, 24351, 31425, 41325, 51324.

Alois P. Heinz, Table of n, a(n) for n = 4..200

Column k=1 of A264173.

A264175 Number of permutations of [n] with exactly two (possibly overlapping) occurrences of the consecutive pattern 1324.

Original entry on oeis.org

2, 29, 407, 5856, 84351, 1251246, 19318314, 311306106, 5247587002, 92593553775, 1709675651881, 33009644160452, 665774603385155, 14011066071814409, 307285854478257587, 7014599706534263680, 166463062283304010885, 4101715354110043233880, 104819153609360857542346

Offset: 6

Alois P. Heinz, Nov 06 2015

nonn

			a(6) = 2: 132546, 142536.
a(7) = 29: 1243657, 1253647, 1324657, 1325467, 1325476, 1326475, 1326574, 1425367, 1425376, 1426375, 1426573, 1436572, 1526374, 1526473, 1536472, 2143657, 2153647, 2436571, 2536471, 3142657, 3152647, 4132657, 4152637, 5132647, 5142637, 6132547, 6142537, 7132546, 7142536.

Alois P. Heinz, Table of n, a(n) for n = 6..200

Column k=2 of A264173.

A264176 Number of permutations of [n] with exactly three (possibly overlapping) occurrences of the consecutive pattern 1324.

Original entry on oeis.org

5, 94, 2215, 48234, 984498, 20018292, 410686782, 8572433100, 183327724185, 4031683382270, 91372697900165, 2136865477317678, 51598608241844089, 1286708862328929178, 33133108712407230345, 880758960967930222782, 24159154493395236208028, 683464289463119208686060

Offset: 8

Alois P. Heinz, Nov 06 2015

nonn

			a(8) = 5: 13254768, 13264758, 14253768, 14263758, 15263748.

Alois P. Heinz, Table of n, a(n) for n = 8..200

Column k=3 of A264173.

A264177 Number of permutations of [n] with exactly four (possibly overlapping) occurrences of the consecutive pattern 1324.

Original entry on oeis.org

14, 322, 14322, 446883, 12483967, 338673045, 9001362380, 238129970970, 6339260568095, 170856651003305, 4682542114588253, 130886424229747444, 3738852184485065063, 109293382675549834910, 3272185613468650581758, 100391722311294374198126, 3157137371183609019647618

Offset: 10

Alois P. Heinz, Nov 06 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 10..180

Column k=4 of A264173.

A264178 Number of permutations of [n] with exactly five (possibly overlapping) occurrences of the consecutive pattern 1324.

Original entry on oeis.org

42, 1140, 111599, 4611558, 173158550, 6150882796, 207804108053, 6856445861216, 223949186168735, 7301452481956954, 239153348717534527, 7905330813488457406, 264571946551458787730, 8986227993271868092040, 310292223622481235050006, 10906047958204275121950876

Offset: 12

Alois P. Heinz, Nov 06 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 12..180

Column k=5 of A264173.

A264179 Number of permutations of [n] with exactly six (possibly overlapping) occurrences of the consecutive pattern 1324.

Original entry on oeis.org

132, 4125, 1020505, 51702016, 2624962373, 120276735039, 5090983012009, 207018756962968, 8203026471635019, 320184726894303006, 12416042942124295046, 481161485425852541912, 18716816000121904713776, 733252038482676120349158, 29003355422362252267923702

Offset: 14

Alois P. Heinz, Nov 06 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 14..180

Column k=6 of A264173.

A264180 Number of permutations of [n] with exactly seven (possibly overlapping) occurrences of the consecutive pattern 1324.

Original entry on oeis.org

429, 15158, 10456115, 614782886, 43495122923, 2526575343670, 132579863515715, 6585406452179450, 313695654024665114, 14537292870957416456, 662270871072941918072, 29874010431593104928640, 1341720576566678207783742, 60253806120517563450850104

Offset: 16

Alois P. Heinz, Nov 06 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 16..180

Column k=7 of A264173.

cp's OEIS Frontend

A264319 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive pattern 3412; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2-1)), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A061206 a(n) = total number of occurrences of the consecutive pattern 1324 in all permutations of [n+3].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A113228 a(n) is the number of permutations of [1..n] that avoid the consecutive pattern 1324 (equally, the permutations that avoid 4231).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A264174 Number of permutations of [n] with exactly one occurrence of the consecutive pattern 1324.

Views

Author

Keywords

Examples

Links

Crossrefs

A264175 Number of permutations of [n] with exactly two (possibly overlapping) occurrences of the consecutive pattern 1324.

Views

Author

Keywords

Examples

Links

Crossrefs

A264176 Number of permutations of [n] with exactly three (possibly overlapping) occurrences of the consecutive pattern 1324.

Views

Author

Keywords

Examples

Links

Crossrefs

A264177 Number of permutations of [n] with exactly four (possibly overlapping) occurrences of the consecutive pattern 1324.

Views

Author

Keywords

Links

Crossrefs

A264178 Number of permutations of [n] with exactly five (possibly overlapping) occurrences of the consecutive pattern 1324.

Views

Author

Keywords

Links

Crossrefs

A264179 Number of permutations of [n] with exactly six (possibly overlapping) occurrences of the consecutive pattern 1324.

Views

Author

Keywords

Links

Crossrefs

A264180 Number of permutations of [n] with exactly seven (possibly overlapping) occurrences of the consecutive pattern 1324.