A000486 -id:A000486 - cp's OEIS frontend

A008970 Triangle T(n,k) = P(n,k)/2, n >= 2, 1 <= k < n, of one-half of number of permutations of 1..n such that the differences have k runs with the same signs.

1, 1, 2, 1, 6, 5, 1, 14, 29, 16, 1, 30, 118, 150, 61, 1, 62, 418, 926, 841, 272, 1, 126, 1383, 4788, 7311, 5166, 1385, 1, 254, 4407, 22548, 51663, 59982, 34649, 7936, 1, 510, 13736, 100530, 325446, 553410, 517496, 252750, 50521, 1, 1022, 42236, 433162, 1910706, 4474002, 6031076, 4717222, 1995181, 353792

Offset: 2

N. J. A. Sloane

			Triangle starts
  1;
  1,  2;
  1,  6,   5;
  1, 14,  29,  16;
  1, 30, 118, 150, 61;
  ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261, #13, P_{n,k}.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260, Table 7.2.1.

Vincenzo Librandi, Rows n = 2..100, flattened
Désiré André, Mémoire sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
Désiré André, Etude sur les maxima, minima et sequences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
M. Bona and R. Ehrenborg, A combinatorial proof of the log-concavity of the numbers of permutations with k runs, arXiv:math/9902020 [math.CO], 1999.
F. Morley, A generating function for the number of permutations with an assigned number of sequences, Bull. Amer. Math. Soc. 4 (1897), 23-28. Shows the transpose of this triangle.

Diagonals give A000352, A000486, A000506, A000111, A000708, A091303.
A059427 gives triangle of P(n, k).
A008303 gives circular version of P(n, k).
T(2n,n) gives A360426.

T:= proc(n, k) option remember; `if`(n<2, 0, `if`(k=1, 1,
      k*T(n-1, k) + 2*T(n-1, k-1) + (n-k)*T(n-1, k-2)))
    end:
seq(seq(T(n,k), k=1..n-1), n=2..12);  # Alois P. Heinz, Feb 08 2023

p[n_ /; n >= 2, 1] = 2; p[n_ /; n >= 2, k_] /; 1 <= k <= n := p[n, k] = k*p[n-1, k] + 2*p[n-1, k-1] + (n-k)*p[n-1, k-2]; p[n_, k_] = 0; t[n_, k_] := p[n, k]/2; A008970 = Flatten[ Table[ t[n, k], {n, 2, 11}, {k, 1, n-1}]] (* Jean-François Alcover, Apr 03 2012, after given recurrence *)

Let P(n, k) = number of permutations of [1..n] with k "sequences". Note that A008970 gives P(n, k)/2. Then g.f.: Sum_{n, k} P(n, k) *u^k * t^n/n! = (1 + u)^(-1) * ((1 - u) * (1 - sin(v + t * cos(v))-1) where u = sin(v).

P(n, 1) = 2, P(n, k) = k*P(n-1, k) + 2*P(n-1, k-1) + (n-k)*P(n-1, k-2).

More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001

A000352 One half of the number of permutations of [n] such that the differences have three runs with the same signs.

Original entry on oeis.org

5, 29, 118, 418, 1383, 4407, 13736, 42236, 128761, 390385, 1179354, 3554454, 10696139, 32153963, 96592972, 290041072, 870647517, 2612991141, 7841070590, 23527406090, 70590606895, 211788597919, 635399348208, 1906265153508, 5718929678273, 17157057470297

Offset: 4

N. J. A. Sloane

nonn

			a(4)=5 because the permutations of [4] with three sign runs are 1324, 1423, 2143, 2314, 2413 and their reversals.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 260, #13
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
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).

T. D. Noe, Table of n, a(n) for n = 4..400
E. Rodney Canfield and Herbert S. Wilf, Counting permutations by their runs up and down, arXiv:math/0609704 [math.CO], 2006.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (7,-17,17,-6).

a(n) = T(n, 3), where T(n, k) is the array defined in A008970.

Cf. A000486, A000506.

A000352:=-(-5+6*z)/(3*z-1)/(2*z-1)/(z-1)**2; # [Conjectured by Simon Plouffe in his 1992 dissertation.] [correct up to offset]
# second Maple program:
a:= n-> (<<0|0|1|2>>. <<7|1|0|0>, <-17|0|1|0>, <17|0|0|1>, <-6|0|0|0>>^n)[1, 4]:
seq(a(n), n=4..30);  # Alois P. Heinz, Aug 26 2008

nn = 40; CoefficientList[Series[x^4*(5 - 6*x)/((1 - 3*x)*(1 - 2*x)*(1 - x)^2), {x, 0, nn}], x] (* T. D. Noe, Jun 19 2012 *)

PARI
```
a(n) = (3^n-4*2^n-2*n+11)/4;
```

a(n) = (3^n-4*2^n-2*n+11)/4, n>=4. - Tim Monahan, Jul 14 2011
G.f.: x^4*(5-6*x)/((1-3*x)*(1-2*x)*(1-x)^2).
Limit_{n->infinity} 4*a(n)/3^n = 1. - Philippe Deléham, Feb 22 2004

Edited by Emeric Deutsch, Feb 18 2004

A060158 Number of permutations of [n] with 4 sequences.

Original entry on oeis.org

0, 0, 0, 0, 0, 32, 300, 1852, 9576, 45096, 201060, 866324, 3650592, 15154240, 62260380, 253939116, 1030367448, 4165106264, 16790875860, 67553807428, 271383782544, 1089035545968, 4366631897100, 17497971562460, 70086163646280, 280627369334152, 1123357369925700

Offset: 0

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

nonn

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

Harry J. Smith, Table of n, a(n) for n = 0..200
E. Rodney Canfield and Herbert S. Wilf, Counting permutations by their runs up and down, arXiv:math/0609704 [math.CO], 2006. [See u_4.]
Index entries for linear recurrences with constant coefficients, signature (13, -67, 175, -244, 172, -48).

Cf. A028399, A060157, A000486, A059427, A000352, A123003.

n4 := n->2*n-7+(6-n)*2^(n-1)-3^n+4^(n-1); seq(n4(i),i=5..27);

Join[{0, 0}, LinearRecurrence[{13, -67, 175, -244, 172, -48}, {0, 0, 0, 32, 300, 1852}, 25]] (* Jean-François Alcover, Sep 02 2018 *)

a(n) = { if (n<2, 0, 2*n - 7 + (6 - n)*2^(n - 1) - 3^n + 4^(n - 1)) } \\ Harry J. Smith, Jul 02 2009

a(n) = 2n - 7 + (6-n)*2^(n-1) - 3^n + 4^(n-1).

G.f.: 4*x^5*(8-29*x+24*x^2)/((1-4*x)*(1-3*x)*(1-2*x)^2*(1-x)^2).

Edited by N. J. A. Sloane, Nov 11 2006

cp's OEIS Frontend

A008970 Triangle T(n,k) = P(n,k)/2, n >= 2, 1 <= k < n, of one-half of number of permutations of 1..n such that the differences have k runs with the same signs.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000352 One half of the number of permutations of [n] such that the differences have three runs with the same signs.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A060158 Number of permutations of [n] with 4 sequences.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions