A047921 -id:A047921

Search: a047921 -id:a047921

Displaying 1-4 of 4 results found.

page 1

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.

+0
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

Table of n, a(n) for n=0..40.

Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020).

Wikipedia, Permutation

FORMULA

T(3n,n) = n!.

EXAMPLE

T(4,1) = 4: 1342, 2314, 3421, 4231.

Triangle T(n,k) begins:

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];

T /@ Range[0, 13] // Flatten (* Jean-François Alcover, Apr 26 2021, after Alois P. Heinz *)

CROSSREFS

Column k=0 gives A212580.

Row sums give A000142.

Cf. A047921, A123513, A197365, A216716.

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Apr 18 2021

STATUS

approved

A002628

Number of permutations of length n without 3-sequences.
(Formerly M1536 N0600)

+0
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

a(n) = sum of row n of A180185. - Emeric Deutsch, Sep 06 2010

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

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.

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:

seq(a(n), n=0..25); # Alois P. Heinz, Jul 21 2019

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]}];

a /@ Range[0, 25] (* Jean-François Alcover, May 23 2020 *)

CROSSREFS

Column k=0 of A047921.

Cf. A165960, A165961, A165962. - Isaac Lambert, Oct 07 2009

Cf. A000166, A180185. - Emeric Deutsch, Sep 06 2010

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005

a(0)=1 prepended by Alois P. Heinz, Jul 21 2019

STATUS

approved

A002629

Number of permutations of length n with one 3-sequence.
(Formerly M2003 N0792)

+0
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

Alois P. Heinz, Table of n, a(n) for n = 1..200

J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.

FORMULA

a(n) = Sum(binomial(n-k-2,k-1)*A000166(n-k), k=1..floor((n-1)/2)). - Emeric Deutsch, Sep 07 2010

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

a(4) = 2 because we have 2341 and 4123. - Emeric Deutsch, Sep 07 2010

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:

seq(a(n), n=1..25); # Alois P. Heinz, Jan 25 2014

MATHEMATICA

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 *)

CROSSREFS

Cf. A000166, A047921.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Max Alekseyev, Feb 20 2010

STATUS

approved

A002630

Number of permutations of length n with two 3-sequences.
(Formerly M2032 N0804)

+0
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

Table of n, a(n) for n=1..24.

J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.

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

Cf. A047921.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Max Alekseyev, Feb 20 2010

STATUS

approved

page 1

Search completed in 0.007 seconds