A002628
Number of permutations of length n without 3-sequences.
Original entry on oeis.org
1, 1, 2, 5, 21, 106, 643, 4547, 36696, 332769, 3349507, 37054436, 446867351, 5834728509, 82003113550, 1234297698757, 19809901558841, 337707109446702, 6094059760690035, 116052543892621951, 2325905946434516516, 48937614361477154273, 1078523843237914046247
Offset: 0
a(4) = 21 because only 1234, 2341, and 4123 contain 3-sequences. - _Emeric Deutsch_, Sep 06 2010
- Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), number 1, 297-305.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Alois P. Heinz, Table of n, a(n) for n = 0..450
- D. M. Jackson and R. C. Read, A note on permutations without runs of given length, Aequationes Math. 17 (1978), no. 2-3, 336-343.
- J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.
-
seq(coeff(convert(series(add(m!*((t-t^3)/(1-t^3))^m,m=0..50),t,50), polynom), t,n),n=0..25); # Pab Ter, Nov 06 2005
d[-1]:= 0: for n from 0 to 51 do d[n] := n*d[n-1]+(-1)^n end do: a:= proc(n) add(binomial(n-k, k)*(d[n-k]+d[n-k-1]), k = 0..floor((1/2)*n)) end proc: seq(a(n), n = 0..25); # Emeric Deutsch, Sep 06 2010
# third Maple program:
a:= proc(n) option remember; `if`(n<5,
[1$2, 2, 5, 21][n+1], (n-3)*a(n-1)+(3*n-6)*a(n-2)+
(4*n-12)*a(n-3)+(3*n-12)*a(n-4)+(n-5)*a(n-5))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Jul 21 2019
-
d[0] = 1; d[n_] := d[n] = n d[n - 1] + (-1)^n;
T[n_, k_] := If[n == 0 && k == 0, 1, If[k <= n/2, Binomial[n - k, k] d[n + 1 - k]/(n - k), 0]];
a[n_] := Sum[T[n, k], {k, 0, Quotient[n, 2]}];
a /@ Range[0, 25] (* Jean-François Alcover, May 23 2020 *)
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005
A002629
Number of permutations of length n with one 3-sequence.
Original entry on oeis.org
0, 0, 1, 2, 11, 62, 406, 3046, 25737, 242094, 2510733, 28473604, 350651588, 4661105036, 66529260545, 1014985068610, 16484495344135, 283989434253186, 5173041992087562, 99346991708245506, 2006304350543326057, 42505510227603678206, 942678881135812883321
Offset: 1
a(4) = 2 because we have 2341 and 4123. - _Emeric Deutsch_, Sep 07 2010
- Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), no. 1, 297-305.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
-
d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-k-2, k-1)*d[n-k], k = 1 .. floor((1/2)*n-1/2)) end proc; seq(a(n), n = 1 .. 23); # Emeric Deutsch, Sep 07 2010
# second Maple program:
a:= proc(n) option remember;
`if`(n<5, -n*(n-1)*(n-2)*(n-5)/12,
(n-4) *a(n-1)+(3*n-6) *a(n-2)+(4*n-8) *a(n-3)
+(3*n-6)*a(n-4)+(n-2) *a(n-5))
end:
seq(a(n), n=1..25); # Alois P. Heinz, Jan 25 2014
-
a[n_] := Sum[Binomial[n-k-2, k-1]*Subfactorial[n-k], {k, 1, (n-1)/2}]; Array[a, 23] (* Jean-François Alcover, Mar 13 2014, after Emeric Deutsch *)
A002630
Number of permutations of length n with two 3-sequences.
Original entry on oeis.org
0, 0, 0, 1, 2, 12, 71, 481, 3708, 32028, 306723, 3228804, 37080394, 461569226, 6192527700, 89102492915, 1369014167140, 22373840093040, 387602212164321, 7095737193164187, 136885937242792752, 2775675888994318366, 59023506305591628101, 1313445236142071926488
Offset: 1
- D. M. Jackson, J. W. Reilly, Permutations with a prescribed number of $p$-runs. Ars Combinatoria 1 (1976), no. 1, 297-305.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
-
nmax = 22;
CoefficientList[Sum[((m + 2)*(m + 1)*(m + 2)!/2*(x^6*(1 - x)^4/(1 - x^3)^4) + (m + 1)*(m + 1)!*(x^4*(1 + x)*(1 - x)^3)/(1 - x^3)^3)*((x - x^3)/(1 - x^3))^m, {m, 0, nmax}]/x + O[x]^nmax, x] (* Jean-François Alcover, May 06 2024, after Tani Akinari *)
-
concat([0,0,0],Vec(sum(m=0,100,((m+2)*(m+1)*(m+2)!/2*(x^6*(1-x)^4/(1-x^3)^4)+(m+1)*(m+1)!*(x^4*(1+x)*(1-x)^3)/(1-x^3)^3)*((x-x^3)/(1-x^3))^m)+O(x^100))) \\ Tani Akinari, Nov 08 2014
A343535
Number T(n,k) of permutations of [n] having exactly k consecutive triples j, j+1, j-1; triangle T(n,k), n>=0, 0<=k<=floor(n/3), read by rows.
Original entry on oeis.org
1, 1, 2, 5, 1, 20, 4, 102, 18, 626, 92, 2, 4458, 564, 18, 36144, 4032, 144, 328794, 32898, 1182, 6, 3316944, 301248, 10512, 96, 36755520, 3057840, 102240, 1200, 443828184, 34073184, 1085904, 14304, 24, 5800823880, 413484240, 12538080, 174000, 600, 81591320880
Offset: 0
T(4,1) = 4: 1342, 2314, 3421, 4231.
Triangle T(n,k) begins:
1;
1;
2;
5, 1;
20, 4;
102, 18;
626, 92, 2;
4458, 564, 18;
36144, 4032, 144;
328794, 32898, 1182, 6;
3316944, 301248, 10512, 96;
36755520, 3057840, 102240, 1200;
443828184, 34073184, 1085904, 14304, 24;
5800823880, 413484240, 12538080, 174000, 600;
81591320880, 5428157760, 156587040, 2214720, 10800;
1228888215960, 76651163160, 2105035440, 29777520, 175800, 120;
...
-
b:= proc(s, l, t) option remember; `if`(s={}, 1, add((h->
expand(b(s minus {j}, j, `if`(h=1, 2, 1))*
`if`(t=2 and h=-2, x, 1)))(j-l), j=s))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(
b({$1..n}, -1, 1)):
seq(T(n), n=0..13);
-
b[s_, l_, t_] := b[s, l, t] = If[s == {}, 1, Sum[Function[h,
Expand[b[s ~Complement~ {j}, j, If[h == 1, 2, 1]]*
If[t == 2 && h == -2, x, 1]]][j - l], {j, s}]];
T[n_] := CoefficientList[b[Range[n], -1, 1], x];
T /@ Range[0, 13] // Flatten (* Jean-François Alcover, Apr 26 2021, after Alois P. Heinz *)
Showing 1-4 of 4 results.
Comments