Search: a047921 -id:a047921
|
| |
|
|
A002628
|
|
Number of permutations of length n without 3-sequences.
(Formerly M1536 N0600)
|
|
+10
14
|
|
|
|
1, 1, 2, 5, 21, 106, 643, 4547, 36696, 332769, 3349507, 37054436, 446867351, 5834728509, 82003113550, 1234297698757, 19809901558841, 337707109446702, 6094059760690035, 116052543892621951, 2325905946434516516, 48937614361477154273, 1078523843237914046247
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
|
|
|
REFERENCES
|
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).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k)*(d(n-k) + d(n-k-1)) for n>0, where d(j) = A000166(j) are the derangement numbers. - Emeric Deutsch, Sep 06 2010
|
|
|
EXAMPLE
|
a(4) = 21 because only 1234, 2341, and 4123 contain 3-sequences. - Emeric Deutsch, Sep 06 2010
|
|
|
MAPLE
|
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:
|
|
|
MATHEMATICA
|
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]}];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A002629
|
|
Number of permutations of length n with one 3-sequence.
(Formerly M2003 N0792)
|
|
+10
8
|
|
|
|
0, 0, 1, 2, 11, 62, 406, 3046, 25737, 242094, 2510733, 28473604, 350651588, 4661105036, 66529260545, 1014985068610, 16484495344135, 283989434253186, 5173041992087562, 99346991708245506, 2006304350543326057, 42505510227603678206, 942678881135812883321
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
a(n) is also the number of successions in all permutations of [n-1] with no 3-sequences. A succession of a permutation p is a position i such that p(i+1) - p(i) = 1. Example: a(4)=2 because in 132, 213, 2*31, 31*2, 321 we have 0+0+1+1+0=2 successions (marked *). - Emeric Deutsch, Sep 07 2010
|
|
|
REFERENCES
|
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).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) ~ (n-1)! * (1 - 4/n + 13/(2*n^2) + 29/(6*n^3) - 551/(24*n^4) - 1101/(20*n^5) + 58879/(720*n^6)). - Vaclav Kotesovec, Mar 16 2015
|
|
|
EXAMPLE
|
|
|
|
MAPLE
|
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:
|
|
|
MATHEMATICA
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A002630
|
|
Number of permutations of length n with two 3-sequences.
(Formerly M2032 N0804)
|
|
+10
2
|
|
|
|
0, 0, 0, 1, 2, 12, 71, 481, 3708, 32028, 306723, 3228804, 37080394, 461569226, 6192527700, 89102492915, 1369014167140, 22373840093040, 387602212164321, 7095737193164187, 136885937242792752, 2775675888994318366, 59023506305591628101, 1313445236142071926488
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
REFERENCES
|
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).
|
|
|
LINKS
|
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(PARI) 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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
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.
|
|
+10
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Terms in column k are multiples of k!.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(3n,n) = n!.
|
|
|
EXAMPLE
|
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;
...
|
|
|
MAPLE
|
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);
|
|
|
MATHEMATICA
|
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];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.012 seconds
|
