A000506 -id:A000506 - 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

A133884 a(n) = binomial(n+4,n) mod 4.

Original entry on oeis.org

1, 1, 3, 3, 2, 2, 2, 2, 3, 3, 1, 1, 0, 0, 0, 0, 1, 1, 3, 3, 2, 2, 2, 2, 3, 3, 1, 1, 0, 0, 0, 0, 1, 1, 3, 3, 2, 2, 2, 2, 3, 3, 1, 1, 0, 0, 0, 0, 1, 1, 3, 3, 2, 2, 2, 2, 3, 3, 1, 1, 0, 0, 0, 0, 1, 1, 3, 3, 2, 2, 2, 2, 3, 3, 1, 1, 0, 0, 0, 0, 1, 1, 3, 3, 2, 2, 2, 2, 3, 3, 1, 1, 0, 0, 0, 0, 1, 1, 3, 3, 2, 2, 2, 2, 3

Offset: 0

Hieronymus Fischer, Oct 10 2007

Periodic with length 4^2=16.

			For n=2, binomial(6,2) = 6*5/2 = 15, which is 3 (mod 4) so a(2) = 3. - _Michael B. Porter_, Jul 19 2016

Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, -1, 1, 0, 0, -1, 1, 0, 0, -1, 1).

Cf. A000040, A133630, A038509.
Cf. A133620, A133621, A133622, A133623, A133624, A133625
Cf. A133634, A133635, A133636.
Cf. A133874, A133880, A133890, A133900, A133910.

[Binomial(n+4,n) mod 4: n in [0..100]]; // Vincenzo Librandi, Jul 15 2016

Table[Mod[Binomial[n + 4, 4], 4], {n, 0, 100}] (* Vincenzo Librandi, Jul 15 2016 *)

a(n) = binomial(n+4,4) mod 4.
G.f.: (1 + x + 3*x^2 + 3*x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + 3*x^8 + 3*x^9 + x^10 + x^11)/(1 - x^16) = (1 + 2*x^2 + 2*x^6 + x^8)/((1 - x)*(1 + x^4)*(1 + x^8)).
a(n) = A000505(n+5) mod 4. - John M. Campbell, Jul 14 2016
a(n) = A000506(n+6) mod 4. - John M. Campbell, Jul 15 2016

G.f. corrected by Bruno Berselli, Jul 19 2016

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

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

A133884 a(n) = binomial(n+4,n) mod 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

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