A216837 -id:A216837 - cp's OEIS frontend

A356692 Pascal-like triangle, where each entry is the sum of the four entries above it starting with 1 at the top.

1, 1, 1, 2, 2, 2, 4, 6, 6, 4, 10, 16, 20, 16, 10, 26, 46, 62, 62, 46, 26, 72, 134, 196, 216, 196, 134, 72, 206, 402, 618, 742, 742, 618, 402, 206, 608, 1226, 1968, 2504, 2720, 2504, 1968, 1226, 608, 1834, 3802, 6306, 8418, 9696, 9696, 8418, 6306, 3802, 1834, 5636, 11942, 20360, 28222, 34116, 36228, 34116, 28222, 20360, 11942, 5636

Offset: 0

Greg Dresden and Sadek Mohammed, Aug 23 2022

Similar in spirit to the regular Pascal triangle, except that here we have T(n,k) = T(n-1,k-2) + T(n-1,k-1) + T(n-1,k) + T(n-1,k+1), with the understanding that T(0,0) is defined to be 1, and T(n,k) is defined as 0 for k<0 and k>n.

T(n,k) is the number of permutations p of [n+1] such that at most one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i <= n and p(n+1) = k+1. T(4,1) = 16: 13542, 14532, 15342, 15432, 31542, 35142, 35412, 41532, 45132, 45312, 51342, 51432, 53142, 53412, 54132, 54312. - Alois P. Heinz, Aug 31 2022

			T(4,0) = 10 because it is the sum of T(3,-2), T(3,-1), T(3,0), and T(3,1) which gives 0+0+4+6 = 10.
Triangle begins:
             1
           1   1
         2   2   2
       4   6   6   4
     10  16  20  16  10
   26  46  62  62  46  26
  ...

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

Row sums give A216837(n+1).
Column k=0 and also main diagonal give A356832.
T(2n,n) gives A356853.
Cf. A007318, A064189.

T:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, add(T(n-1,j), j=k-2..k+1)))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Aug 28 2022

T[0, 0] = 1; T[n_, k_] := T[n, k] = If[k < 0 || k > n, 0,
    T[n - 1, k - 2] + T[n - 1, k - 1] + T[n - 1, k] + T[n - 1, k + 1]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten

T(n,k) = T(n,n-k).

A356832 Number of permutations p of [n] such that at most one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i < n and n = 0 or p(n) < 3.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 72, 206, 608, 1834, 5636, 17578, 55516, 177192, 570700, 1852572, 6055080, 19910730, 65823752, 218654100, 729459552, 2443051214, 8210993364, 27685671844, 93625082140, 317470233150, 1079183930828, 3676951654520, 12554734605496, 42952566314236

Offset: 0

Alois P. Heinz, Aug 30 2022

nonn

			a(0) = 1: (), the empty permutation.
a(1) = 1: 1.
a(2) = 2: 12, 21.
a(3) = 4: 132, 231, 312, 321.
a(4) = 10: 1342, 1432, 2431, 3142, 3412, 3421, 4132, 4231, 4312, 4321.
a(5) = 26: 13542, 14532, 15342, 15432, 24531, 25431, 31542, 35142, 35412, 35421, 41532, 42531, 45132, 45231, 45312, 45321, 51342, 51432, 52431, 53142, 53412, 53421, 54132, 54231, 54312, 54321.

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

Column k=0 and also main diagonal of A356692.

Cf. A000142, A102407, A216837, A291683.

b:= proc(u, o) option remember; `if`(u+o=0, 1,
      add(b(sort([o-j, u+j-1])[]), j=1..min(2, o))+
      add(b(sort([u-j, o+j-1])[]), j=1..min(2, u)))
    end:
a:= n-> b(0, n):
seq(a(n), n=0..30);
# second Maple program:
b:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, add(b(n-1, j), j=k-2..k+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..30);

a(n) = A356692(n,0) = A356692(n,n).
a(n) = 1 + A291683(n).
a(n) >= A102407(n) with equality only for n <= 7.

A187817 Number of permutations p of {1,...,n} such that exactly two elements of {p(1),...,p(i-1)} are between p(i) and p(i+1) for all i from 3 to n-1.

Original entry on oeis.org

1, 1, 2, 6, 4, 4, 4, 4, 8, 12, 20, 32, 52, 104, 188, 344, 616, 1116, 2232, 4236, 8084, 15212, 28760, 57520, 111512, 216804, 417560, 806440, 1612880, 3162132, 6209192, 12113136, 23670168, 47340336, 93411704, 184494460, 362693224, 713767712, 1427535424

Offset: 0

Alois P. Heinz, Oct 03 2013

nonn

			a(4) = 4: 2314, 2341, 3214, 3241.
a(5) = 4: 23514, 32514, 34152, 43152.
a(6) = 4: 341625, 346152, 431625, 436152.
a(7) = 4: 3471625, 4371625, 4517263, 5417263.
a(8) = 8: 34716258, 43716258, 45182736, 45817263, 54182736, 54817263, 56283741, 65283741.
a(9) = 12: 348172596, 438172596, 451827369, 459182736, 541827369, 549182736, 561928374, 569283741, 651928374, 659283741, 672938514, 762938514.

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

Cf. A174700, A174701, A174702, A174703, A174704, A174705, A174706, A174707, A174708, A185030, A216837.

b:= proc(u, o) option remember; `if`(u+o<3, (u+o)!,
      `if`(o>2, b(sort([o-3, u+2])[]), 0)+
      `if`(u>2, b(sort([u-3, o+2])[]), 0))
    end:
a:= n-> `if`(n=0, 1, add(b(sort([j-1, n-j])[]), j=1..n)):
seq(a(n), n=0..40);

b[u_, o_] := b[u, o] = If[u + o < 3, (u + o)!,
     If[o > 2, b @@ Sort[{o - 3, u + 2}], 0] +
     If[u > 2, b @@ Sort[{u - 3, o + 2}], 0]];
a[n_] := If[n == 0, 1, Sum[b @@ Sort[{j - 1, n - j}], {j, 1, n}]];
a /@ Range[0, 40] (* Jean-François Alcover, Mar 15 2021, after Alois P. Heinz *)

cp's OEIS Frontend

A356692 Pascal-like triangle, where each entry is the sum of the four entries above it starting with 1 at the top.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A356832 Number of permutations p of [n] such that at most one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i < n and n = 0 or p(n) < 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A187817 Number of permutations p of {1,...,n} such that exactly two elements of {p(1),...,p(i-1)} are between p(i) and p(i+1) for all i from 3 to n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica