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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• tabf

Comments

The recurrence given by Roselle is wrong.

Examples

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

Links

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

Crossrefs

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

Row sums give A000255.

Programs

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

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.

Extensions

More terms from Vladeta Jovovic, Jan 03 2003