A184181 -id:A184181 - cp's OEIS frontend

A180564 Number of permutations of [n] having no isolated entries. An entry j of a permutation p is isolated if it is not preceded by j-1 and not followed by j+1. For example, the permutation 23178564 has 2 isolated entries: 1 and 4.

1, 0, 1, 1, 2, 3, 7, 14, 35, 81, 216, 557, 1583, 4444, 13389, 40313, 128110, 409519, 1366479, 4603338, 16064047, 56708713, 206238116, 759535545, 2870002519, 10986716984, 43019064953, 170663829777, 690840124506, 2832976091771, 11831091960887, 50040503185030

Offset: 0

Emeric Deutsch, Sep 09 2010

nonn

a(n) = A180196(n,0).

a(n) = n! - A184181(n).

			a(5)=3 because we have 12345, 34512, and 45123.

Alois P. Heinz, Table of n, a(n) for n = 0..893

Cf. A000142, A000166, A180196, A184181.

d[ -1] := 0: d[0] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-j-1, j-1)*(d[j]+d[j-1]), j = 1 .. floor((1/2)*n)) end proc:a(0):=1: seq(a(n), n = 0 .. 32);
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [1, 0, 1, 1][n+1],
      (3*a(n-1)+(n-3)*a(n-2)-(n-3)*a(n-3)+(n-4)*a(n-4))/2)
    end:
seq(a(n), n=0..31);  # Alois P. Heinz, Feb 17 2024

a[n_] := If[n == 0, 1, With[{d = Subfactorial}, Sum[Binomial[n-j-1, j-1]* (d[j] + d[j-1]), {j, 1, Floor[n/2]}]]];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Sep 17 2024 *)

a(n) = Sum_{j=1..floor(n/2)} binomial(n-j-1, j-1)*(d(j) + d(j-1)), where d(i) = A000166(i) are the derangement numbers; a(0)=1.

a(0)=1 prepended by Alois P. Heinz, Feb 17 2024

A184180 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose shortest block is of length k (1 <= k <= n). A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 4512367 has 3 blocks: 45, 123, and 67. Its shortest block has length 2.

Original entry on oeis.org

1, 1, 1, 5, 0, 1, 22, 1, 0, 1, 117, 2, 0, 0, 1, 713, 5, 1, 0, 0, 1, 5026, 11, 2, 0, 0, 0, 1, 40285, 31, 2, 1, 0, 0, 0, 1, 362799, 73, 5, 2, 0, 0, 0, 0, 1, 3628584, 201, 11, 2, 1, 0, 0, 0, 0, 1, 39916243, 532, 20, 2, 2, 0, 0, 0, 0, 0, 1, 479000017, 1534, 40, 5, 2, 1, 0, 0, 0, 0, 0, 1, 6227016356, 4346, 82, 11, 2, 2, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Emeric Deutsch, Feb 13 2011

Sum of entries in row n is n!.

T(n,1) = A184181(n).

			T(5,2) = 2 because we have 45123 and 34512.
Triangle starts:
    1;
    1, 1;
    5, 0, 1;
   22, 1, 0, 1;
  117, 2, 0, 0, 1;
  713, 5, 1, 0, 0, 1;
  ...

Cf. A000142, A000166, A184181, A184182.

d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) options operator, arrow: sum(binomial(n-(k-1)*m-1, m-1)*(d[m]+d[m-1]), m = 1 .. floor(n/k))-(sum(binomial(n-k*m-1, m-1)*(d[m]+d[m-1]), m = 1 .. floor(n/(k+1)))) end proc: for n to 13 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form

T[n_, k_] := With[{d = Subfactorial},
   Sum[Binomial[n-(k-1)*m-1, m-1]*(d[m] + d[m-1]), {m, 1, Floor[n/k]}] -
   Sum[Binomial[n-k*m-1, m-1]*(d[m] + d[m-1]), {m, 1, Floor[n/(k+1)]}]];
Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 18 2024, after Maple code *)

T(n,k) = Sum_{m=1..floor(n/k)} binomial(n-(k-1)*m-1, m-1)*(d(m) + d(m-1)) - Sum_{m=1..floor(n/(k+1))} binomial(n-km-1, m-1)*(d(m) + d(m-1)), where d(j) = A000166(j) are the derangement numbers.

cp's OEIS Frontend

A180564 Number of permutations of [n] having no isolated entries. An entry j of a permutation p is isolated if it is not preceded by j-1 and not followed by j+1. For example, the permutation 23178564 has 2 isolated entries: 1 and 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions