cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A242783 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down; triangle T(n,k), n>=0, read by rows.

Original entry on oeis.org

1, 1, 2, 5, 1, 21, 3, 70, 50, 450, 270, 4326, 602, 99, 12, 1, 34944, 5376, 209863, 139714, 13303, 1573632, 1366016, 530432, 158720, 21824925, 15302031, 2715243, 74601, 302273664, 161855232, 14872704, 2854894485, 2600075865, 712988175, 59062275
Offset: 0

Views

Author

Alois P. Heinz, May 22 2014

Keywords

Comments

Sum_{k>0} k*T(n,k) = A249249(n).

Examples

			T(7,3) = 12 because 12 permutations of {1,2,3,4,5,6,7} have exactly 3 (possibly overlapping) occurrences of the consecutive step pattern up, up, up given by the binary expansion of 7 = 111_2: (1,2,3,4,5,7,6), (1,2,3,4,6,7,5), (1,2,3,5,6,7,4), (1,2,4,5,6,7,3), (1,3,4,5,6,7,2), (2,1,3,4,5,6,7), (2,3,4,5,6,7,1), (3,1,2,4,5,6,7), (4,1,2,3,5,6,7), (5,1,2,3,4,6,7), (6,1,2,3,4,5,7), (7,1,2,3,4,5,6).
Triangle T(n,k) begins:
: n\k :       0        1       2       3  4  ...
+-----+------------------------------------
:  0  :       1;
:  1  :       1;                             [row  1 of A008292]
:  2  :       2;                             [row  2 of A008303]
:  3  :       5,       1;                    [row  3 of A162975]
:  4  :      21,       3;                    [row  4 of A242819]
:  5  :      70,      50;                    [row  5 of A227884]
:  6  :     450,     270;                    [row  6 of A242819]
:  7  :    4326,     602,     99,     12, 1; [row  7 of A220183]
:  8  :   34944,    5376;                    [row  8 of A242820]
:  9  :  209863,  139714,  13303;            [row  9 of A230695]
: 10  : 1573632, 1366016, 530432, 158720;    [row 10 of A230797]

Links

Crossrefs

Column k=0-10 give: A242785, A246221, A246222, A246223, A246224, A246225, A246226, A246227, A246228, A246229, A243105.
Row sums give A000142.
Cf. A242784, A249249, A295987, A335308.

Programs

  • Maple
    T:= proc(n) option remember; local b, k, r, h;
      k:= iquo(n,2,'r'); h:= 2^ilog2(n);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, irem(2*t,   h))*`if`(r=0 and t=k, x, 1), j=1..u)+
      add(b(u+j-1, o-j, irem(2*t+1, h))*`if`(r=1 and t=k, x, 1), j=1..o)))
      end: forget(b);
      (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 0))
    end:
seq(T(n), n=0..15);
  • Mathematica
    T[n_] := T[n] = Module[{b, k, r, h}, {k, r} = QuotientRemainder[n, 2]; h = 2^Floor[Log[2, n]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Expand[ Sum[b[u - j, o + j - 1, Mod[2*t, h]]*If[r == 0 && t == k, x, 1], {j, 1, u}] + Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]]*If[r == 1 && t == k, x, 1], {j, 1, o}]]]; Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 0]]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Feb 20 2016, after Alois P. Heinz *)

A295987 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step patterns 010 or 101, where 1=up and 0=down; triangle T(n,k), n >= 0, k = max(0, n-3), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 14, 10, 52, 36, 32, 204, 254, 140, 122, 1010, 1368, 1498, 620, 544, 5466, 9704, 9858, 9358, 3164, 2770, 34090, 67908, 90988, 72120, 63786, 18116, 15872, 233026, 545962, 762816, 839678, 560658, 470262, 115356, 101042, 1765836, 4604360, 7458522
Offset: 0

Views

Author

Alois P. Heinz, Dec 01 2017

Keywords

Examples

			Triangle T(n,k) begins:
:      1;
:      1;
:      2;
:      6;
:     14,     10;
:     52,     36,     32;
:    204,    254,    140,    122;
:   1010,   1368,   1498,    620,    544;
:   5466,   9704,   9858,   9358,   3164,   2770;
:  34090,  67908,  90988,  72120,  63786,  18116,  15872;
: 233026, 545962, 762816, 839678, 560658, 470262, 115356, 101042;

Links

Crossrefs

Column k=0 gives A295974.
Last elements of rows for n>3 give: A001250, A260786, 2*A000111.
Row sums give A000142.
Cf. A227884, A230695, A230797, A231384, A232933, A242783, A242819, A242820, A296054.

Programs

  • Maple
    b:= proc(u, o, t, h) option remember; expand(
           `if`(u+o=0, 1, `if`(t=0, add(b(u-j, j-1, 1$2), j=1..u),
       add(`if`(h=3, x, 1)*b(u-j, o+j-1, [1, 3, 1][t], 2), j=1..u)+
       add(`if`(t=3, x, 1)*b(u+j-1, o-j, 2, [1, 3, 1][h]), j=1..o))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$3)):
seq(T(n), n=0..12);
  • Mathematica
    b[u_, o_, t_, h_] := b[u, o, t, h] = Expand[If[u + o == 0, 1, If[t == 0, Sum[b[u - j, j - 1, 1, 1], {j, 1, u}], Sum[If[h == 3, x, 1]*b[u - j, o + j - 1, {1, 3, 1}[[t]], 2], {j, 1, u}] + Sum[If[t == 3, x, 1]*b[u + j - 1, o - j, 2, {1, 3, 1}[[h]]], {j, 1, o}]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 0, 0]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jun 07 2018, from Maple *)

A177519 Number of permutations of 1..n avoiding adjacent step pattern up, down, down, up.

Original entry on oeis.org

1, 1, 2, 6, 24, 109, 588, 3654, 26125, 209863, 1876502, 18441367, 197776850, 2297242583, 28739304385, 385195455471, 5507210188401, 83657067537498, 1345556172013026, 22844387886649418, 408258252653717337, 7660885499702743124, 150600621665021781932
Offset: 0

Views

Author

R. H. Hardin, May 10 2010

Keywords

Links

Crossrefs

Column k=0 of A230695.
Column k=9 of A242784.

Programs

  • Maple
    b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<3, add(b(u+j-1, o-j, 1), j=1..o), 0)+
      add(b(u-j, o+j-1, `if`(t in [0,3], 0, t+1)), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013
  • Mathematica
    b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t < 3,
     Sum[b[u + j - 1, o - j, 1], {j, 1, o}], 0] +
     Sum[b[u - j, o + j - 1, If[MemberQ[{0, 3}, t], 0, t+1]], {j, 1, u}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 20 2022, after Alois P. Heinz *)

Formula

a(n) ~ c * d^n * n!, where d = 0.89356257576899599804435763285311831354458355576519..., c = 1.593348415562339201282264582915828860634166516332738... . - Vaclav Kotesovec, Aug 29 2014

Extensions

a(17)-a(22) from Alois P. Heinz, Oct 07 2013
a(0)=1 from Alois P. Heinz, Apr 20 2022
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.