A060157 Number of permutations of [n] with 3 sequences.

0, 10, 58, 236, 836, 2766, 8814, 27472, 84472, 257522, 780770, 2358708, 7108908, 21392278, 64307926, 193185944, 580082144, 1741295034, 5225982282, 15682141180, 47054812180, 141181213790, 423577195838, 1270798696416, 3812530307016, 11437859356546, 34314114940594

Offset: 3

Author

Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001

Keywords

• nonn
• easy

Examples

			a(4)=10 because each of the 5 (=A000111(4)) up-down permutations and 5 down-up permutations has 3 sequences. For example, the 3 sequences of 2413 are 24, 41, and 13. - _Emeric Deutsch_, Jul 11 2009
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.

Links

• Harry J. Smith, Table of n, a(n) for n = 3..200
• Index entries for linear recurrences with constant coefficients, signature (7,-17,17,-6).

Crossrefs

Cf. A028399, A060158.

Cf. A000111. - Emeric Deutsch, Jul 11 2009

Programs

Maple

n3 := n->11/2-n-2^(n+1)+1/2*3^n; seq(n3(i),i=3..30);

Mathematica

Table[11/2-n-2^(n+1)+3^n/2,{n,3,30}]

PARI

a(n) = { (3^n + 11)/2 - 2^(n + 1) - n } \\ Harry J. Smith, Jul 02 2009

Formula

a(n) = 11/2 - n - 2^(n+1) + (1/2)*3^n.

G.f.: 2*x^4*(5-6*x)/((1-x)^2*(1-2*x)*(1-3*x)). - Colin Barker, Feb 17 2012