A061547 -id:A061547 - cp's OEIS frontend

A068018 Number of fixed points in all 132- and 213-avoiding permutations of {1,2,...,n} (these are permutations with runs consisting of consecutive integers).

0, 1, 2, 4, 6, 12, 18, 40, 62, 148, 234, 576, 918, 2284, 3650, 9112, 14574, 36420, 58266, 145648, 233030, 582556, 932082, 2330184, 3728286, 9320692, 14913098, 37282720, 59652342, 149130828, 238609314, 596523256, 954437198, 2386092964, 3817748730, 9544371792

Offset: 0

Emeric Deutsch, Mar 22 2002

			a(3) = 4 because the permutations 123, 231, 312, 321 of {1,2,3} contain 4 fixed points altogether (all three entries of the first permutation and entry 2 in the last one).

Index entries for linear recurrences with constant coefficients, signature (2,3,-8,4).

Cf. A061547.

Maple
```
seq(2^n/4-(-2)^n/36+2*n/3-2/9,n=0..40);
```

a(n) = 2^n/4 - (-2)^n/36 + 2*n/3 - 2/9.
G.f.: z*(1 - 3*z^2)/((1 - 4*z^2)*(1 - z)^2).
E.g.f.: (cosh(x)*(5*sinh(x) + 6*x - 2) + 2*(cosh(2*x) + (3*x - 1)*sinh(x)))/9. - Stefano Spezia, Jun 12 2023

A258041 Number of 312-avoiding derangements of {1,2,...,n}.

Original entry on oeis.org

1, 0, 1, 1, 4, 10, 31, 94, 303, 986, 3284, 11099, 38024, 131694, 460607, 1624451, 5771532, 20640334, 74246701, 268478962, 975436348, 3559204700, 13037907692, 47931423574, 176792821643, 654078238224, 2426705590840, 9026907769955

Offset: 0

David Callan, May 17 2015

nonn

In the Mathematica recurrence below, a(n,k) is the number of 312-avoiding permutations of {1,2,...,n} with no entry moved k places to the right of its "natural" position; thus a(n,0) = a(n). The recurrence for a(n,k) counts these permutations by the position j of 1 in the permutation.

Numerical evidence suggests lim_{n->inf} a(n)/a(n-1) = 4 and lim_{n->inf} A000108(n)/(n*a(n)) ~ .105.

			a(4) = 4 counts 2143, 2341, 3421, 4321.

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
Aaron Robertson, Dan Saracino, and Doron Zeilberger, Refined Restricted Permutations, arXiv:math/0203033 [math.CO], 2002.
Aaron Robertson, Dan Saracino, and Doron Zeilberger, Refined Restricted Permutations, Annals of Combinatorics 6 (2002) 427-444.

Cf. A000108, A000166, A061547.

a[n_, k_] /; k >= n := CatalanNumber[n]
a[n_, k_] /; 0 <= k < n :=
a[n, k] = Sum[a[j - 1, k + 1] a[n - j, k]  , {j, k}] + Sum[a[j - 1, k + 1] a[n - j, k],{j, k + 2, n}]
a[n_] := a[n, 0]
Table[a[n], {n, 0, 30}]

G.f.: 1/(1 + C(0)x -
         x/(1 + C(1)x^2 -
             x/(1 + C(2)x^3 -
                x/(1 + C(3)x^4 -
                   x/(1 + C(4)x^5 -
                      x/(1 + C(5)x^6 - ...)))))))) [continued fraction] where C(n) = A000108(n) is the n-th Catalan number.

A108723 Triangle read by rows: T(n,k) is number of permutations of [n] with ascending runs consisting of consecutive integers and having k fixed points.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 6, 0, 1, 0, 1, 10, 4, 0, 1, 0, 1, 26, 0, 4, 0, 1, 0, 1, 42, 16, 0, 4, 0, 1, 0, 1, 106, 0, 16, 0, 4, 0, 1, 0, 1, 170, 64, 0, 16, 0, 4, 0, 1, 0, 1, 426, 0, 64, 0, 16, 0, 4, 0, 1, 0, 1, 682, 256, 0, 64, 0, 16, 0, 4, 0, 1, 0, 1, 1706, 0, 256, 0, 64, 0, 16, 0, 4, 0, 1, 0, 1

Offset: 0

Emeric Deutsch, Jun 21 2005

T(n,0)=A061547(n). Sum of row n is 2^(n-1) (n>=1).

			T(3,0)=2 because we have (23)(1) and (3)(12); T(3,1)=1 because we have (3)(2)(1); T(3,3)=1 because we have (123) (the ascending runs are shown between parentheses).
Triangle begins:
1;
0,1;
1,0,1;
2,1,0,1;
6,0,1,0,1;
10,4,0,1,0,1;

Cf. A061547.

T:=proc(n,k) if k=n then 1 elif k>n then 0 elif k=0 then 3*2^n/8+(-2)^n/24-2/3 elif k>0 and n-k mod 2 = 0 then 2^(n-k-2) else 0 fi end: for n from 0 to 13 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

T[n_, k_] := Which[k == n, 1, k > n, 0, k == 0, 3*2^n/8 + (-2)^n/24 - 2/3, k > 0 && EvenQ[n-k], 2^(n-k-2), True, 0];
Table[T[n, k], {n, 0, 13}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 14 2024, after Maple program *)

T(n, 0)=(3/8)2^n + (1/24)(-2)^n - 2/3; T(n, n)=1; T(n, k)=2^(n-k-2) if k>0 and n-k is even; T(n, k)=0 if k>0 and n-k is odd or if k>n.

cp's OEIS Frontend

A068018 Number of fixed points in all 132- and 213-avoiding permutations of {1,2,...,n} (these are permutations with runs consisting of consecutive integers).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A258041 Number of 312-avoiding derangements of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A108723 Triangle read by rows: T(n,k) is number of permutations of [n] with ascending runs consisting of consecutive integers and having k fixed points.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula