A152716 -id:A152716 - cp's OEIS frontend

A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

1, 0, 1, 2, 6, 10, 26, 42, 106, 170, 426, 682, 1706, 2730, 6826, 10922, 27306, 43690, 109226, 174762, 436906, 699050, 1747626, 2796202, 6990506, 11184810, 27962026, 44739242, 111848106, 178956970, 447392426, 715827882, 1789569706, 2863311530, 7158278826

Offset: 0

Emeric Deutsch, May 16 2001

Or, number of permutations with no fixed points avoiding 213 and 132.
Number of derangements of {1,2,...,n} having ascending runs consisting of consecutive integers. Example: a(4)=6 because we have 234/1, 34/12, 34/2/1, 4/123, 4/3/12, 4/3/2/1, the ascending runs being as indicated. - Emeric Deutsch, Dec 08 2004
Let c be twice the sequence A002450 interlaced with itself (from the second term), i.e., c = 2*(0, 1, 1, 5, 5, 21, 21, 85, 85, 341, 341, ...). Let d be powers of 4 interlaced with the zero sequence: d = (1, 0, 4, 0, 16, 0, 64, 0, 256, 0, ...). Then a(n+1) = c(n) + d(n). - Creighton Dement, May 09 2005
Inverse binomial transform of A094705 (0, 1, 4, 15). - Paul Curtz, Jun 15 2008
Equals row sums of triangle A177993. - Gary W. Adamson, May 16 2010
a(n-1) is also the number of order preserving partial isometries (of an n-chain) of fix 1 (fix of alpha equals the number of fixed points of alpha). - Abdullahi Umar, Dec 28 2010
a(n+1) <= A218553(n) is also the Moore lower bound on the order of a (5,n)-cage. - Jason Kimberley, Oct 31 2011
For n > 0, a(n) is the location of the n-th new number to make a first appearance in A087230. E.g., the 17th number to make its first appearance in A087230 is 18 and this occurs at A087230(43690) and a(17)=43690. - K D Pegrume, Jan 26 2022
Position in A002487 of 2 adjacent terms of A000045. E.g., 3/5 at 10, 5/8 at 26, 8/13 at 42, ... - Ed Pegg Jr, Dec 27 2022

			a(4)=6 because the only 132 and 213-avoiding permutations of {1,2,3,4} without fixed points are: 2341, 3412, 3421, 4123, 4312 and 4321.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
F. Al-Kharousi, R. Kehinde and A. Umar, Combinatorial results for certain semigroups of partial isometries of a finite chain, The Australasian Journal of Combinatorics, Volume 58 (3) (2014), 363-375.
J. Brillhart and P. Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, 103 (1996) 854-869 (contains the sequence of the odd-subscripted terms and that of the even-subscripted terms).
Emeric Deutsch, Derangements That Don't Rise Too Fast: 10902, Amer. Math. Monthly, Vol. 110, No. 7 (2003), pp. 639-640.
K. Dilcher and K. B. Stolarsky, Stern polynomials and double-limit continued fractions, Acta Arithmetica 140 (2009), 119-134
R. Kehinde and A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.0049 [math.GR], 2010.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002
Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

Cf. A000166, A020988, A020989, A068018.
Cf. A177993. - Gary W. Adamson, May 16 2010
Cf. A183158, A183159. - Abdullahi Umar, Dec 28 2010
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), this sequence (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 31 2011

[(3/8)*2^n +(1/24)*(-2)^n - 2/3: n in [1..35]]; // Vincenzo Librandi, Aug 13 2011

A061547:=n->ceil(abs((3/8)*2^n +(1/24)*(-2)^n - 2/3)); seq(A061547(n), n=1..30); # Wesley Ivan Hurt, Apr 03 2014

f[n_] := (9*2^(n-3) - (-2)^(n-3) - 2)/3; Array[f, 32] (* Robert G. Wilson v, Aug 13 2011 *)

a(n)=(3/8)*2^n+(1/24)*(-2)^n-2/3 \\ Charles R Greathouse IV, Sep 24 2015

a(n) = (3/8)*2^n + (1/24)*(-2)^n - 2/3 for n>=1.
a(n) = 4*a(n-2) + 2, a(0)=1, a(1)=0, a(2)=1.
G.f: (5*z^3-3*z^2-z+1)/((z-1)*(4*z^2-1)).
a(n) = A020989((n-2)/2) for n=2, 4, 6, ... and A020988((n-3)/2) for n=3, 5, 7, ... .
a(n+1)-2*a(n) = A078008 signed. Differences: doubled A000302. - Paul Curtz, Jun 15 2008
a(2i+1) = 2*Sum_{j=0..i-1} 4^j = string "2"^i read in base 4.
a(2i+2) = 4^i + 2*Sum_{j=0..i-1} 4^j = string "1"*"2"^i read in base 4.
a(n+2) = Sum_{k=0..n} A144464(n,k)^2 = Sum_{k=0..n} A152716(n,k). - Philippe Deléham and Michel Marcus, Feb 26 2014
a(2*n-1) = A176965(2*n), a(2*n) = A176965(2*n-1) for n>0. - Yosu Yurramendi, Dec 23 2016
a(2*n-1) = A020988(k-1), a(2*n)= A020989(n-1) for n>0. - Yosu Yurramendi, Jan 03 2017
a(n+2) = 2*A086893(n), n > 0. - Yosu Yurramendi, Mar 07 2017
E.g.f.: (15 - 8*cosh(x) + 5*cosh(2*x) - 8*sinh(x) + 4*sinh(2*x))/12. - Stefano Spezia, Apr 07 2022

a(0)=1 prepended by Alois P. Heinz, Jan 27 2022

A004197 Triangle read by rows. T(n, k) = n - k if n - k < k, otherwise k.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 3, 2, 1, 0, 0, 1, 2, 3, 3, 2, 1, 0, 0, 1, 2, 3, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2

Offset: 0

David W. Wilson

Table of min(x,y), where (x,y) = (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),...
Highest power of 6 that divides A036561. - Fred Daniel Kline, May 29 2012
Triangle T(n,k) read by rows: T(n,k) = min(k,n-k). - Philippe Deléham, Feb 25 2014

			From _Philippe Deléham_, Feb 25 2014: (Start)
Top left corner of table:
  0 0 0 0
  0 1 1 1
  0 1 2 2
  0 1 2 3
Triangle T(n,k) begins:
  0;
  0, 0;
  0, 1, 0;
  0, 1, 1, 0;
  0, 1, 2, 1, 0;
  0, 1, 2, 2, 1, 0;
  0, 1, 2, 3, 2, 1, 0;
  0, 1, 2, 3, 3, 2, 1, 0;
  0, 1, 2, 3, 4, 3, 2, 1, 0;
  0, 1, 2, 3, 4, 4, 3, 2, 1, 0;
  0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0;
  0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0;
  0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, 0;
  0, 1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1, 0;
  0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0;
  0, 1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1, 0;
  ... (End)

Reinhard Zumkeller, Rows n=0..100 of triangle, flattened

Similar to but strictly different from A087062 and A261684.
Row sums give A002620. - Reinhard Zumkeller, Jul 27 2005
Positions of zero are given in A117142. - Ridouane Oudra, Apr 30 2019
Cf. A144464, A152714, A152716, A152717.

a004197 n k = a004197_tabl !! n !! k
a004197_tabl = map a004197_row [0..]
a004197_row n = hs ++ drop (1 - n `mod` 2) (reverse hs)
   where hs = [0..n `div` 2]
-- Reinhard Zumkeller, Aug 14 2011

T := (n, k) -> if n - k < k then n - k else k fi:
for n from 0 to 9 do seq(T(n, k), k=0..n) od; # Peter Luschny, May 07 2023

Flatten[Table[IntegerExponent[2^(n - k) 3^k, 6], {n, 0, 20}, {k, 0, n}]] (* Fred Daniel Kline, May 29 2012 *)

T(x,y)=min(x,y) \\ Charles R Greathouse IV, Feb 07 2017

a(n) = A003983(n) - 1.
G.f.: x*y/((1-x)*(1-y)*(1-x*y)). - Franklin T. Adams-Watters, Feb 06 2006
2^T(n,k) = A144464(n,k), 3^T(n,k) = A152714(n,k), 4^T(n,k) = A152716(n,k), 5^T(n,k) = A152717(n,k). - Philippe Deléham, Feb 25 2014
a(n) = (1/2)*(t - 1 - abs(t^2 - 2*n - 1)), where t = floor(sqrt(2*n+1)+1/2). - Ridouane Oudra, May 03 2019

Mathematica program fixed by Harvey P. Dale, Nov 26 2020

Name edited by Peter Luschny, May 07 2023

A144464 Triangle T(n,m) read by rows: T(n,m) = 2^min(m,n-m).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 2, 4, 4, 2, 1, 1, 2, 4, 8, 4, 2, 1, 1, 2, 4, 8, 8, 4, 2, 1, 1, 2, 4, 8, 16, 8, 4, 2, 1, 1, 2, 4, 8, 16, 16, 8, 4, 2, 1, 1, 2, 4, 8, 16, 32, 16, 8, 4, 2, 1

Offset: 0

Roger L. Bagula and Gary W. Adamson, Oct 09 2008

			The triangle starts in row n=0 as:
{1},
{1, 1},
{1, 2, 1},
{1, 2, 2, 1},
{1, 2, 4, 2, 1},
{1, 2, 4, 4, 2, 1},
{1, 2, 4, 8, 4, 2, 1},
{1, 2, 4, 8, 8, 4, 2, 1},
{1, 2, 4, 8, 16, 8, 4, 2, 1},
{1, 2, 4, 8, 16, 16, 8, 4, 2, 1},
{1, 2, 4, 8, 16, 32, 16, 8, 4, 2, 1}

Cf. A004197, A152714, A152716, A152717.

Clear[f, t]; f[n_, m_] = If[m <= Floor[n/2], m, n - m]; Table[Table[f[n, m], {m, 0, n}], {n, 0, 10}]; Flatten[%]

T(n,m)=1<Charles R Greathouse IV, Jan 15 2012

Row sums: sum_{m=0..n} T(n,m) = A027383(n).

T(n,k) = 2^A004197(n,k). - Philippe Deléham, Feb 25 2014

Offset corrected by the Associate Editors of the OEIS, Sep 11 2009

Better name by Philippe Deléham, Feb 25 2014

A152714 Triangle read by rows: T(n,k) = 3^min(k, n-k).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 3, 3, 1, 1, 3, 9, 3, 1, 1, 3, 9, 9, 3, 1, 1, 3, 9, 27, 9, 3, 1, 1, 3, 9, 27, 27, 9, 3, 1, 1, 3, 9, 27, 81, 27, 9, 3, 1, 1, 3, 9, 27, 81, 81, 27, 9, 3, 1, 1, 3, 9, 27, 81, 243, 81, 27, 9, 3, 1

Offset: 0

Roger L. Bagula and Gary W. Adamson, Dec 11 2008

			Triangle begins
  {1},
  {1, 1},
  {1, 3, 1},
  {1, 3, 3,  1},
  {1, 3, 9,  3,  1},
  {1, 3, 9,  9,  3,   1},
  {1, 3, 9, 27,  9,   3,  1},
  {1, 3, 9, 27, 27,   9,  3,  1},
  {1, 3, 9, 27, 81,  27,  9,  3, 1},
  {1, 3, 9, 27, 81,  81, 27,  9, 3, 1},
  {1, 3, 9, 27, 81, 243, 81, 27, 9, 3, 1}

G. C. Greubel, Rows n=0..100 of triangle, flattened

Cf. A004197, A144464, A152716, A152717, A062318 (row sums).

[[3^(Min(k,n-k)): k in [0..n]]: n in [0..15]]; // G. C. Greubel, Sep 01 2018

Clear[a, k, m]; k = 3; a[0] = {1}; a[1] = {1, 1};
a[n_] := a[n] = Join[{1}, k*a[n - 2], {1}];
Table[a[n], {n, 0, 10}];
Flatten[%]
Table[3^(Min[k, n - k]), {n, 0, 100}, {k, 0, n}] // Flatten (* G. C. Greubel, Sep 01 2018 *)

for(n=0,15, for(k=0,n, print1(3^(min(k,n-k)), ", "))) \\ G. C. Greubel, Sep 01 2018

T(n,k) = 3^min(k, n-k) = 3^A004197(n,k). - Philippe Deléham, Feb 25 2014

Better name by Philippe Deléham, Feb 25 2014

A152717 Triangle T(n,k) read by rows: T(n,k) = 5^min(k, n-k) = 5^A004197(n,k).

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 5, 5, 1, 1, 5, 25, 5, 1, 1, 5, 25, 25, 5, 1, 1, 5, 25, 125, 25, 5, 1, 1, 5, 25, 125, 125, 25, 5, 1, 1, 5, 25, 125, 625, 125, 25, 5, 1, 1, 5, 25, 125, 625, 625, 125, 25, 5, 1, 1, 5, 25, 125, 625, 3125, 625, 125, 25, 5, 1

Offset: 0

Roger L. Bagula and Gary W. Adamson, Dec 11 2008

Row sums are: {1, 2, 7, 12, 37, 62, 187, 312, 937, 1562, 4687,...}

			{1},
{1, 1},
{1, 5, 1},
{1, 5, 5, 1},
{1, 5, 25, 5, 1},
{1, 5, 25, 25, 5, 1},
{1, 5, 25, 125, 25, 5, 1},
{1, 5, 25, 125, 125, 25, 5, 1},
{1, 5, 25, 125, 625, 125, 25, 5, 1},
{1, 5, 25, 125, 625, 625, 125, 25, 5, 1},
{1, 5, 25, 125, 625, 3125, 625, 125, 25, 5, 1}

Cf. A004197, A144464, A152714, A152716.

Clear[a, k, m]; k = 5; a[0] = {1}; a[1] = {1, 1};
a[n_] := a[n] = Join[{1}, k*a[n - 2], {1}];
Table[a[n], {n, 0, 10}];
Flatten[%]

T(n,k) = 5^min(k, n-k). - Philippe Deléham, Feb 25 2014

Better name from Philippe Deléham, Feb 25 2014

A262616 Triangle read by rows: T(n,k) = 4^(n-k), n>=0, 0<=k<=n.

Original entry on oeis.org

1, 4, 1, 16, 4, 1, 64, 16, 4, 1, 256, 64, 16, 4, 1, 1024, 256, 64, 16, 4, 1, 4096, 1024, 256, 64, 16, 4, 1, 16384, 4096, 1024, 256, 64, 16, 4, 1, 65536, 16384, 4096, 1024, 256, 64, 16, 4, 1, 262144, 65536, 16384, 4096, 1024, 256, 64, 16, 4, 1, 1048576, 262144, 65536, 16384, 4096, 1024, 256, 64, 16, 4, 1

Offset: 0

Omar E. Pol, Nov 23 2015

A triangle of the same family of A130321 and A140303, with the same offset.

T(n,k) is also the number of hidden crosses of size k+1 formed by squares and rectangles in the toothpick structure of A139250 after 2^(n+2) stages. The last term in every row represents the central cross of the toothpick structure.

			Triangle begins:
1;
4,       1;
16,      4,       1;
64,      16,      4,      1;
256,     64,      16,     4,     1;
1024,    256,     64,     16,    4,     1;
4096,    1024,    256,    64,    16,    4,    1;
16384,   4096,    1024,   256,   64,    16,   4,    1;
65536,   16384,   4096,   1024,  256,   64,   16,   4,   1;
262144,  65536,   16384,  4096,  1024,  256,  64,   16,  4,  1;
1048576, 262144,  65536,  16384, 4096,  1024, 256,  64,  16, 4,  1;
4194304, 1048576, 262144, 65536, 16384, 4096, 1024, 256, 64, 16, 4, 1;
...

Indranil Ghosh, Rows 0..100, flattened
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Column k gives A000302.
Row sums give the positive terms of A002450.
Alternating row sums give the positive terms of A015521.
Cf. A130321, A139250, A140303, A152571, A152716.

Table[4^(n - k), {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Jul 17 2016 *)

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

cp's OEIS Frontend

A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A004197 Triangle read by rows. T(n, k) = n - k if n - k < k, otherwise k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A144464 Triangle T(n,m) read by rows: T(n,m) = 2^min(m,n-m).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A152714 Triangle read by rows: T(n,k) = 3^min(k, n-k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A152717 Triangle T(n,k) read by rows: T(n,k) = 5^min(k, n-k) = 5^A004197(n,k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A262616 Triangle read by rows: T(n,k) = 4^(n-k), n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula