A046740 Triangle of number of permutations of [n] with 0 successions, by number of rises.

1, 1, 1, 2, 1, 8, 2, 1, 22, 28, 2, 1, 52, 182, 72, 2, 1, 114, 864, 974, 164, 2, 1, 240, 3474, 8444, 4174, 352, 2, 1, 494, 12660, 57194, 61464, 15782, 732, 2, 1, 1004, 43358, 332528, 660842, 373940, 55286, 1496, 2, 1, 2026, 142552, 1747558, 5814124

Offset

1,4

Comments

The recurrence given by Roselle is wrong.

Links

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

D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 8-16.

D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 8-16. [Annotated scanned copy]

Formula

a(n, 1) = 1; for r > 1, a(n, r) = r*a(n-1, r) + (n-r)*a(n-1, r-1) + (n-2)*a(n-2, r-1).

a(n, 2) = 2^n - 2*n = 2*A000295 = A005803, n >= 3.

Example

Triangle begins:
  1;
  1;
  1,  2;
  1,  8,  2;
  1, 22, 28,  2;
  ...

Mathematica

a[_, 1] = 1; a[n_, 2] := 2^n - 2*n; a[n_, r_] /; 1 <= r <= n-1 := a[n, r] = r*a[n-1, r] + (n-r)*a[n-1, r-1] + (n-2)*a[n-2, r-1]; a[_, _] = 0;
row[1] = {{1}}; row[n_] := Table[a[n, r], {r, 1, n-1}];
Table[row[n], {n, 1, 11}] // Flatten (* Jean-François Alcover, Sep 07 2017 *)

Crossrefs

Cf. A046739, A000295. Row sums give A000255. Diagonals give A005803, A065340.

Row sums give A000255.

Sequence in context: A208660 A367024 A114706 * A317932 A253583 A130562

Adjacent sequences: A046737 A046738 A046739 * A046741 A046742 A046743

Keyword

nonn,easy,nice,tabf

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Jan 03 2003

Status

approved