A014495 -id:A014495 - cp's OEIS frontend

A326763 Number of permutations of length n and order at most 3 whose powers all avoid the pattern 132.

1, 1, 2, 5, 10, 16, 36, 65, 118, 232, 452, 800, 1622, 3042, 5758, 11077, 21712, 40204, 79718, 151628, 292994, 561954, 1103786, 2087696, 4115506, 7884446, 15393710, 29592074, 58229334, 111422134, 219575234, 422888473, 830617400, 1602832900, 3160618558, 6092881976

Offset: 0

Amanda Burcroff, Aug 15 2019

nonn

Miklós Bóna and Rebecca Smith, Pattern Avoidance in Permutations and Their Squares, Discrete Mathematics, 342 (2019), pp. 3194-3200; arXiv:1901.00026 [math.CO], 2019.
Amanda Burcroff and Colin Defant, Pattern-Avoiding Permutation Powers, Discrete Mathematics, 343 (2020), 112017; arXiv:1907.09451 [math.CO], 2019.

Cf. A326760, A326761, A326762, A001405, A014495, A370686.

def a(n):
    return len([p for p in Permutations(n)
        if p*p == Permutations(n).identity() and p.avoids([1, 3, 2])
        or p*p*p == Permutations(n).identity() and p.avoids([1, 3, 2]) and (p*p).avoids([1, 3, 2])]) # Andrey Zabolotskiy, Apr 13 2025

a(n) = A014495(n) + A370686(n), where the 1st (resp. 2nd) term counts 132-avoiding permutations of order 2 (resp. 1 or 3). - Andrey Zabolotskiy, Apr 13 2025

Terms a(16) onwards using the formula from Andrey Zabolotskiy, Apr 14 2025

A368175 Square array read by ascending antidiagonals: T(n,k) = Sum_{i=ceiling((k-n)/2)..floor((k+n-1)/2)} binomial(k,i), with n >= 1, k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 2, 3, 3, 1, 2, 4, 6, 6, 1, 2, 4, 7, 10, 10, 1, 2, 4, 8, 14, 20, 20, 1, 2, 4, 8, 15, 25, 35, 35, 1, 2, 4, 8, 16, 30, 50, 70, 70, 1, 2, 4, 8, 16, 31, 56, 91, 126, 126, 1, 2, 4, 8, 16, 32, 62, 112, 182, 252, 252, 1, 2, 4, 8, 16, 32, 63, 119, 210, 336, 462, 462

Offset: 1

Paolo Xausa, Dec 14 2023

T(n,k), for k >= 1, is the size of the largest possible set S of k-bit strings such that, if S_a < S_b are members of S, then W(S_b) < W(S_a) + n, where W is A000120.

T(1,k), for k >= 1, gives the number of rows in the Christmas tree pattern (cf. A367508) of order k. Furthermore, T(n,k), for k >= 1, gives the number of rows generated by iteratively applying k times the map described in A367508, starting from a single row of length n.

			Array begins:
  n\k|  0  1  2  3   4   5   6    7    8    9    10  ...
  ---+--------------------------------------------------
   1 |  1, 1, 2, 3,  6, 10, 20,  35,  70, 126,  252, ... = A001405
   2 |  1, 2, 3, 6, 10, 20, 35,  70, 126, 252,  462, ... = A001405
   3 |  1, 2, 4, 7, 14, 25, 50,  91, 182, 336,  672, ... = A026010
   4 |  1, 2, 4, 8, 15, 30, 56, 112, 210, 420,  792, ... = A026023
   5 |  1, 2, 4, 8, 16, 31, 62, 119, 238, 456,  912, ...
   6 |  1, 2, 4, 8, 16, 32, 63, 126, 246, 492,  957, ...
   7 |  1, 2, 4, 8, 16, 32, 64, 127, 254, 501, 1002, ...
   8 |  1, 2, 4, 8, 16, 32, 64, 128, 255, 510, 1012, ...
   9 |  1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1022, ...
  10 |  1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, ...
  ...
For n = 3 and k = 4 the 14 members of S are 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110.

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, exercises 71 and 72, pp. 479 and 799.

Paolo Xausa, Table of n, a(n) for n = 1..11325 (antidiagonals 1..150 of the array, flattened).

Cf. A000079, A000120, A000225, A001405, A014495, A026010, A026023, A191781, A367508.

A368175[n_,k_]:=If[n>k,2^k,Sum[Binomial[k,i],{i,Ceiling[(k-n)/2],Floor[(k+n-1)/2]}]];
With[{dmax=15},Table[A368175[n-k,k],{n,dmax},{k,0,n-1}]] (* Generates 15 antidiagonals *)

T(n,0) = 1.
T(1,k) = A001405(k).
T(n,k) = 2^k = A000079(k), for n > k.
T(n,n) = 2^n - 1 = A000225(n).
Antidiagonal sums: Sum_{n=1..d} T(n,d-n) = binomial(d+1,floor((d+1)/2)) - 1 = A014495(d+1), for d >= 1.

A247374 Number of button presses required to try every combination of a binary combination lock with n number buttons.

Original entry on oeis.org

3, 8, 17, 38, 77, 165, 331, 698, 1397, 2921, 5843, 12149, 24299, 50315, 100631, 207698, 415397, 855105, 1710211, 3512801, 7025603, 14403923, 28807847, 58967773, 117935547, 241071395, 482142791, 984343883, 1968687767, 4014934295, 8029868591, 16360277378, 32720554757, 66607912625, 133215825251, 270969218153

Offset: 1

Elliott Line, Sep 15 2014

nonn

This type of lock is quite common in the real world. The lock has typically 13 'number' buttons (actually 0 1 2 3 4 5 6 7 8 9 X Y Z), plus a C (for clear) button, and a knob to turn to 'try' the combination. The way it functions is that the unlocking code is an n-digit binary number. By pressing one of the number buttons, you change the corresponding digit from 0 to 1. Pressing C reverts all digits to 0.

			A lock with four number buttons (plus try and clear) would have 16 combinations to try, namely 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.
All combinations can be tried in 38 presses using the following sequence of presses:
T 1 T 2 T 3 T 4 T C 2 T 3 T 4 T C 3 T 4 T 1 T C 4 T 1 T 2 T C 1 3 T C 2 4 T. The T (tries) will attempt the combinations in the following order: 0000, 1000, 1100, 1110, 1111, 0100, 0110, 0111, 0010, 0011, 1011, 0001, 1001, 1101, 1010, 0101.

Cf. A000079, A014495, A014314.

a(n) = A000079(n) + A014495(n) + A014314(n). A000079 is how many times the 'try' button (or knob) is pressed. A014495 is how many times the C (clear) button is pressed. A014314 is how many times the number buttons are pressed.

Conjectured to be D-finite with recurrence: n*a(n) +2*(-2*n+1)*a(n-1) +(n-2)*a(n-2) +2*(7*n-10)*a(n-3) +4*(-5*n+11)*a(n-4) +8*(n-3)*a(n-5)=0. - R. J. Mathar, Nov 19 2019

A261681 a(n) = 2^n + binomial(n, floor(n/2)) - 1.

Original entry on oeis.org

1, 2, 5, 10, 21, 41, 83, 162, 325, 637, 1275, 2509, 5019, 9907, 19815, 39202, 78405, 155381, 310763, 616665, 1233331, 2449867, 4899735, 9740685, 19481371, 38754731, 77509463, 154276027, 308552055, 614429671, 1228859343, 2448023842, 4896047685, 9756737701

Offset: 0

N. J. A. Sloane, Sep 04 2015

nonn

Riccardo Biagioli, Frédéric Jouhet, and Philippe Nadeau, Combinatorics of fully commutative involutions in classical Coxeter groups, arXiv preprint arXiv:1411.4561 [math.CO] (2014). See Prop. 2.1.
Riccardo Biagioli, Frédéric Jouhet, and Philippe Nadeau, Combinatorics of fully commutative involutions in classical Coxeter groups, Discrete Math., 338 (2015), 2242-2259. See Prop. 2.1.

Cf. A000079, A014495.

Cf. A000225, A001405.

[2^n+Binomial(n, Floor(n/2))-1: n in [0..40]]; // Vincenzo Librandi, Sep 05 2015

Table[2^n + Binomial[n, Floor[n/2]] - 1, {n, 0, 40}] (* Vincenzo Librandi, Sep 05 2015 *)

a(n) = 2^n + binomial(n, n\2) - 1 \\ Michel Marcus, Sep 05 2015

a(n) = A000079(n) + A014495(n).
Conjecture: -(n+1)*(n-4)*a(n) +(3*n^2-9*n-8)*a(n-1) +2*(n^2-9*n+16)*a(n-2) +4*(-3*n^2+18*n-25)*a(n-3) +8*(n-3)^2*a(n-4)=0. - R. J. Mathar, Jan 04 2017
a(n) = Sum_{i=1..n+1} C(n,floor(i/2)). - Wesley Ivan Hurt, Nov 22 2017

cp's OEIS Frontend

A326763 Number of permutations of length n and order at most 3 whose powers all avoid the pattern 132.

Views

Author

Keywords

Links

Crossrefs

Programs

SageMath

Formula

Extensions

A368175 Square array read by ascending antidiagonals: T(n,k) = Sum_{i=ceiling((k-n)/2)..floor((k+n-1)/2)} binomial(k,i), with n >= 1, k >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A247374 Number of button presses required to try every combination of a binary combination lock with n number buttons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A261681 a(n) = 2^n + binomial(n, floor(n/2)) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula