A276837 -id:A276837 - cp's OEIS frontend

A276719 Number A(n,k) of set partitions of [n] such that for each block b the smallest integer interval containing b has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 5, 5, 1, 0, 1, 1, 2, 5, 10, 8, 1, 0, 1, 1, 2, 5, 15, 20, 13, 1, 0, 1, 1, 2, 5, 15, 37, 42, 21, 1, 0, 1, 1, 2, 5, 15, 52, 87, 87, 34, 1, 0, 1, 1, 2, 5, 15, 52, 151, 208, 179, 55, 1, 0, 1, 1, 2, 5, 15, 52, 203, 409, 515, 370, 89, 1, 0

Offset: 0

Alois P. Heinz, Sep 16 2016

The sequence of column k satisfies a linear recurrence with constant coefficients of order 2^(k-1) for k>0.

			A(3,2) = 3: 12|3, 1|23, 1|2|3.
A(4,3) = 10: 123|4, 12|34, 12|3|4, 13|24, 13|2|4, 1|234, 1|23|4, 1|24|3, 1|2|34, 1|2|3|4.
A(5,4) = 37: 1234|5, 123|45, 123|4|5, 124|35, 124|3|5, 12|345, 12|34|5, 12|35|4, 12|3|45, 12|3|4|5, 134|25, 134|2|5, 13|245, 13|24|5, 13|25|4, 13|2|45, 13|2|4|5, 14|235, 14|23|5, 1|2345, 1|234|5, 1|235|4, 1|23|45, 1|23|4|5, 14|25|3, 14|2|35, 14|2|3|5, 1|245|3, 1|24|35, 1|24|3|5, 1|25|34, 1|2|345, 1|2|34|5, 1|25|3|4, 1|2|35|4, 1|2|3|45, 1|2|3|4|5.
Square array A(n,k) begins:
  1, 1,  1,   1,   1,    1,    1,    1,    1, ...
  0, 1,  1,   1,   1,    1,    1,    1,    1, ...
  0, 1,  2,   2,   2,    2,    2,    2,    2, ...
  0, 1,  3,   5,   5,    5,    5,    5,    5, ...
  0, 1,  5,  10,  15,   15,   15,   15,   15, ...
  0, 1,  8,  20,  37,   52,   52,   52,   52, ...
  0, 1, 13,  42,  87,  151,  203,  203,  203, ...
  0, 1, 21,  87, 208,  409,  674,  877,  877, ...
  0, 1, 34, 179, 515, 1100, 2066, 3263, 4140, ...

Alois P. Heinz, Antidiagonals n = 0..40, flattened
Pierpaolo Natalini, Paolo Emilio Ricci, New Bell-Sheffer Polynomial Sets, Axioms 2018, 7(4), 71.
Wikipedia, Partition of a set

Columns k=0..10 give: A000007, A000012, A000045(n+1), A129847, A276720, A276721, A276722, A276723, A276724, A276725, A276726.
Main diagonal gives A000110.
A(n+1,n) gives A005493(n-1) for n>0.
Cf. A276727, A276837.

b:= proc(n, m, l) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j), [subsop(1=NULL, l)[],
      `if`(j<=m, 0, j)]), j={l[], m+1} minus {0}))
    end:
A:= (n, k)-> `if`(n=0, 1, `if`(k<2, k, b(n, 0, [0$(k-1)]))):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, m_, l_List] := b[n, m, l] = If[n == 0, 1, Sum[b[n - 1, Max[m, j], Append[ReplacePart[l, 1 -> Nothing], If[j <= m, 0, j]]], {j, Append[l, m + 1] ~Complement~ {0}}]]; A[n_, k_] := If[n == 0, 1, If[k < 2, k, b[n, 0, Array[0&, k-1]]]]; Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 06 2017, after Alois P. Heinz *)

A(n,k) = Sum_{i=0..k} A276727(n,i).

A263757 Triangle read by rows: T(n,k) (n>=1, 0<=k

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 4, 7, 12, 1, 7, 17, 35, 60, 1, 12, 44, 93, 210, 360, 1, 20, 103, 275, 651, 1470, 2520, 1, 33, 234, 877, 2047, 5208, 11760, 20160, 1, 54, 533, 2544, 7173, 18423, 46872, 105840, 181440, 1, 88, 1196, 7135, 27085, 67545, 184230, 468720, 1058400, 1814400

Offset: 1

Christian Stump, Oct 25 2015

Row sums give A000142, n >= 1.

Main diagonal gives A001710. - Alois P. Heinz, Sep 20 2016

			Triangle begins:
  1;
  1,  1;
  1,  2,  3;
  1,  4,  7, 12;
  1,  7, 17, 35,  60;
  1, 12, 44, 93, 210, 360;
  ...

Alois P. Heinz, Rows n = 1..15, flattened
FindStat - Combinatorial Statistic Finder, Maximum difference of elements in cycles.

Cf. A000071, A000142, A001710, A276727, A276837, A276974, A277031.

T(n,k) = A276837(n,k+1) - A276837(n,k). - Alois P. Heinz, Sep 20 2016

More terms (rows n=7-10) from Alois P. Heinz, Sep 20 2016

A214663 Number of permutations of 1..n for which the partial sums of signed displacements do not exceed 2.

Original entry on oeis.org

1, 1, 2, 6, 12, 25, 57, 124, 268, 588, 1285, 2801, 6118, 13362, 29168, 63685, 139057, 303608, 662888, 1447352, 3160121, 6899745, 15064810, 32892270, 71816436, 156802881, 342360937, 747505396, 1632091412, 3563482500, 7780451037, 16987713169, 37090703118, 80983251898

Offset: 0

David Scambler, Jul 24 2012

Proof: Consider adding the letter n to a conforming (n-1)-permutation. The possible cases are: 1) (n-1)-perm | n; 2) (n-2)-perm | n | n-1; 3) (n-3)-perm | n | n-1 | n-2; 4) (n-3)-perm | n | n-2 | n-1; 5) (n-3)-perm | n-1 | n | n-2; and 6) (n-4)-perm | n-1 | n-3 | n |n-2; other cases are excluded by the rules. This yields a(n-1)+a(n-2)+3*a(n-3)+a(n-4) as the count of conforming n-permutations with a(0)=1.
Partial sums calculated as follows:
  p(i)         3  1  4  2  5
  p(i)-i       2 -1  1 -2  0
  partial sum  2  1  2  0  0 // max = 2 so counted
  p(i)         3  1  4  5  2
  p(i)-i       2 -1  1  1 -3
  partial sum  2  1  2  3  0 // max = 3 so not counted
Number of permutations of length n>=0 avoiding the partially ordered pattern (POP) {1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the last element. - Sergey Kitaev, Dec 08 2020

			a(4) = 12: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 3124, 3142, 3214. The ten 4-permutations starting with 4 or ending with 1, as well as 2413 and 3412, do not comply.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
László Németh and Dragan Stevanović, Graph solution of system of recurrence equations, Research Gate, 2023. See Table 1 at p. 3.
Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns, arXiv:2101.12061 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (1,1,3,1).

Column k=3 of A276837.

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|3|1|1>>^n)[4, 4]:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 25 2012

CoefficientList[Series[1/(1 - x - x^2 - 3 x^3 - x^4), {x, 0, 37}], x]
LinearRecurrence[{1,1,3,1},{1,1,2,6},40] (* Harvey P. Dale, Apr 26 2019 *)

G.f.: 1/(1-x-x^2-3*x^3-x^4).

A276838 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most four elements.

Original entry on oeis.org

1, 1, 2, 6, 24, 60, 150, 399, 1145, 3132, 8420, 22716, 62128, 169536, 460885, 1251777, 3406238, 9272354, 25229036, 68622196, 186682470, 507925571, 1381929921, 3759616968, 10228269080, 27827267544, 75707898304, 205971928848, 560368255081, 1524544463441

Offset: 0

Alois P. Heinz, Sep 20 2016

a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>5} of length 5. That is, the number of length n permutations having no subsequences of length 5 in which the first element is larger than the fifth element. - Sergey Kitaev, Dec 11 2020

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Index entries for linear recurrences with constant coefficients, signature (1,2,2,12,8,-2,-5,-1).

Column k=4 of A276837.

Cf. A276720.

CoefficientList[Series[-(x - 1) (x + 1)/(x^8 + 5 x^7 + 2 x^6 - 8 x^5 - 12 x^4 - 2 x^3 - 2 x^2 - x + 1), {x, 0, 29}], x] (* Michael De Vlieger, Oct 14 2017 *)

G.f.: -(x-1)*(x+1)/(x^8+5*x^7+2*x^6-8*x^5-12*x^4-2*x^3-2*x^2-x+1).

A276839 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most five elements.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 360, 1050, 3192, 10305, 35505, 116620, 374172, 1195764, 3848248, 12538476, 40807108, 132283092, 427799593, 1383464353, 4481902342, 14529001194, 47085299068, 152520137944, 493941015012, 1599895591174, 5182983937428, 16791233651977

Offset: 0

Alois P. Heinz, Sep 20 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=5 of A276837.

Cf. A276721.

G.f.: -(x^8 +x^6 +5*x^5 +3*x^3 +x^2 -1) / (x^16 +7*x^15 +6*x^14 -3*x^13 +53*x^12 +138*x^11 +97*x^10 +95*x^9 +24*x^8 -61*x^7 -75*x^6 -70*x^5 -9*x^4 -5*x^3 -2*x^2 -x +1).

A276840 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most six elements.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 2520, 8400, 28728, 103050, 390555, 1566813, 5994636, 22318676, 82337580, 304360184, 1134352752, 4275368704, 16107425628, 60453074344, 226179710040, 845165016029, 3159696003981, 11832636916230, 44346582492034, 166184942954284

Offset: 0

Alois P. Heinz, Sep 20 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=6 of A276837.

Cf. A276722.

G.f.: -(x^22 +2*x^20 -2*x^19 -44*x^18 +22*x^17 +60*x^16 -4*x^15 +40*x^14 -102*x^13 -120*x^12 -4*x^11 -8*x^10 -142*x^9 +2*x^8 +28*x^7 +42*x^6 -8*x^5 +12*x^4 +8*x^3 +2*x^2 -1) / (x^32 +9*x^31 +9*x^30 -19*x^29 +59*x^28 -461*x^27 -2227*x^26 -977*x^25 +2109*x^24 +655*x^23 -947*x^22 -8178*x^21 -13502*x^20 +1258*x^19 +11266*x^18 -12018*x^17 -32910*x^16 -12790*x^15 +2866*x^14 +6174*x^13 +4666*x^12 +5578*x^11 +3425*x^10 +1037*x^9 -523*x^8 -639*x^7 -449*x^6 -37*x^5 -15*x^4 -9*x^3 -3*x^2 -x +1).

A276841 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most seven elements.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 20160, 75600, 287280, 1133550, 4686660, 20368569, 93109737, 406088940, 1719126780, 7184340564, 29966843736, 125593803792, 530881463680, 2267064321984, 9681953067016, 41200660295772, 174712473986620, 739333708856220

Offset: 0

Alois P. Heinz, Sep 20 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=7 of A276837.

Cf. A276723.

G.f.: -(x^52 +6*x^50 -34*x^49 +20*x^48 +482*x^47 -426*x^46 -1468*x^45 -4536*x^44 +3648*x^43 +19218*x^42 +980*x^41 +11510*x^40 -47116*x^39 +35786*x^38 +93064*x^37 +164632*x^36 +300102*x^35 -85560*x^34 -604736*x^33 +93922*x^32 -445966*x^31 +372558*x^30 +156416*x^29 +160198*x^28 -518168*x^27 -147664*x^26 -493240*x^25 +29594*x^24 +313562*x^23 +610220*x^22 +32062*x^21 -12854*x^20 +13220*x^19 -157960*x^18 -46776*x^17 -70050*x^16 -41076*x^15 -50710*x^14 -5996*x^13 +1894*x^12 -1936*x^11 +968*x^10 +738*x^9 +1040*x^8 +776*x^7 -2*x^6 +70*x^5 +34*x^4 +8*x^3 +2*x^2 -1) / (x^64 +11*x^63 +15*x^62 -31*x^61 +21*x^60 -881*x^59 +6397*x^58 +41653*x^57 +32901*x^56 -67903*x^55 -284725*x^54 -392391*x^53 +559947*x^52 +104334*x^51 -1200042*x^50 -2062678*x^49 -1572286*x^48 +15473434*x^47 +15863554*x^46 +35936394*x^45 +69616662*x^44 -80992842*x^43 -307844474*x^42 -283307502*x^41 -219491322*x^40 +338286*x^39 +213380440*x^38 -3315412*x^37 -349666888*x^36 -484336364*x^35 -431418124*x^34 -248674504*x^33 +22949740*x^32 +144629920*x^31 -9726680*x^30 -113690432*x^29 -126317520*x^28 -143609200*x^27 -79336148*x^26 +10701066*x^25 -42072302*x^24 -78959890*x^23 -72447322*x^22 -22061410*x^21 -5812154*x^20 -8720370*x^19 -2145534*x^18 +2011058*x^17 +2823538*x^16 +1655238*x^15 +661954*x^14 +294538*x^13 +118975*x^12 +23793*x^11 -13327*x^10 -11405*x^9 -7057*x^8 -3807*x^7 -305*x^6 -93*x^5 -37*x^4 -9*x^3 -3*x^2 -x +1).

A276842 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most eight elements.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 181440, 756000, 3160080, 13602600, 60926580, 285159966, 1396646055, 7158444465, 35019420060, 165994449732, 774542703708, 3596199290264, 16729008975792, 78297230499296, 369560004222048, 1760728654735744, 8392003472443920

Offset: 0

Alois P. Heinz, Sep 20 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alois P. Heinz, G.f. for A276842

Column k=8 of A276837.

Cf. A276724.

G.f.: see link above.

A276843 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most nine elements.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 1814400, 8316000, 37920960, 176833800, 852972120, 4277399490, 22346336880, 121693555905, 690665206113, 3742590924108, 19625337285660, 101084160732660, 516806625700056, 2640952527095376, 13549247936670720

Offset: 0

Alois P. Heinz, Sep 20 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..128

Column k=9 of A276837.

Cf. A276725.

A276844 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most ten elements.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 19958400, 99792000, 492972480, 2475673200, 12794581800, 68438391840, 379887726960, 2190484006290, 13122638916147, 81648757479285, 485188719524460, 2787398328848820, 15702226260438924, 87625414510220472

Offset: 0

Alois P. Heinz, Sep 20 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..64

Column k=10 of A276837.

Cf. A276726.

cp's OEIS Frontend

A276719 Number A(n,k) of set partitions of [n] such that for each block b the smallest integer interval containing b has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A263757 Triangle read by rows: T(n,k) (n>=1, 0<=k

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A214663 Number of permutations of 1..n for which the partial sums of signed displacements do not exceed 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A276838 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most four elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A276839 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most five elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A276840 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most six elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A276841 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most seven elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A276842 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most eight elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A276843 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most nine elements.

Views

Author

Keywords

Links

Crossrefs

A276844 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most ten elements.