|
| |
|
|
A008303
|
|
Triangle read by rows: T(n,k) (n>=1; 0<=k<=ceil(n/2)-1) is the number of permutations of [n] with k peaks.
|
|
2
| |
|
|
1, 2, 4, 2, 8, 16, 16, 88, 16, 32, 416, 272, 64, 1824, 2880, 272, 128, 7680, 24576, 7936, 256, 31616, 185856, 137216, 7936, 512, 128512, 1304832, 1841152, 353792, 1024, 518656, 8728576, 21253376, 9061376, 353792, 2048, 2084864, 56520704, 222398464, 175627264, 22368256, 4096, 8361984, 357888000, 2174832640, 2868264960, 795300864, 22368256, 8192, 33497088, 2230947840, 20261765120, 41731645440, 21016670208, 1903757312
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Row n has ceil(n/2) terms.
Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 26 2009: (Start)
Sum of entries in row n is n! = A000142(n).
T(n,0)=2^(n-1)=A000079(n-1).
T(n,1)=A000431(n).
T(n,2)=A000487(n).
T(n,3)=A000517(n).
T(2n,n-1)=T(2n+1,n)=A000182(n+1) (the tangent numbers).
Sum(k*T(n,k), k>=0)=n!(n-2)/3=A090672(n-1).
(End)
|
|
|
REFERENCES
| F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.3.
S. Elizalde and M. Noy, Consecutive patterns in permutations (Section 5), Adv. Appl. Math. 30 (2003) 110-125.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.46. [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 26 2009]
W. O. Kermack and A. G. McKendrick, "Some distributions associated with a randomly arranged set of numbers", Proc. Royal Soc. of Edinburgh 67 (1937), 332-376.
W. O. Kermack and A. G. McKendrick, "Some properties of points arranged on a M\"obius surface", Mathematical Gazette 22 (1938), 66-72.
Shi-Mei Ma, Derivative polynomials and permutations by numbers of interior peaks and left peaks, Arxiv preprint arXiv:1106.5781, 2011
A. Mendes and J. B. Remmel, Permutations and words counted by consecutive patterns, Adv. Appl. Math. 37 4 (2006) 443-480.
Louis W. Shapiro, Wen-Jin Woan and Seyoum Getu, "Runs, slides and moments", SIAM J. Algebraic and Discrete Methods 4 (1983), 461.
|
|
|
FORMULA
| E.g.f.: G(t,z)=[exp(bz)-exp(az)]/[b*exp(az)-a*exp(bz)], where a+b=2 and ab=t, i.e. a=1+sqrt(1-t), b=1-sqrt(1-t) (see the Goulden-Jackson reference). [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 26 2009]
E.g.f: tan(t*sqrt(x-1))/(sqrt(x-1)-tan(t*sqrt(x-1))) = sum {n>=0} P(n,x)*t^n/n! = t + 2*t^2/2! + (4+2*x)*t^3/3! + (8+16*x)*t^4/4! + .... The row generating polynomials P(n,x) satisfy x^(n-1)*P(n,1+1/x^2) = R(n-1,x), where R(n,x) are the row polynomials of A185896. A000670(n) = (3/2)^(n-1)*P(n,8/9) - Peter Bala, Oct 14 2011
|
|
|
EXAMPLE
| Comment from Luc Roy, Jul 08 2010: (Start)
It appears that one-half of the sequence A008303 can be obtained with this mathematica program:
Expand[CoefficientList[
Simplify[
InverseSeries[
Integrate[Series[(1 + m Sinh[x]^2)^(-1), {x, 0, 15}, {m, 0, 15}],
x]]], x] Denominator[
CoefficientList[Series[Exp[x], {x, 0, 15}], x]]]
{0, 1, 0, 2 m, 0, 8 m + 16 m^2, 0, 32 m + 416 m^2 + 272 m^3, 0,
128 m + 7680 m^2 + 24576 m^3 + 7936 m^4, 0,
512 m + 128512 m^2 + 1304832 m^3 + 1841152 m^4 + 353792 m^5, 0,
2048 m + 2084864 m^2 + 56520704 m^3 + 222398464 m^4 +
175627264 m^5 + 22368256 m^6, 0,
8192 m + 33497088 m^2 + 2230947840 m^3 + 20261765120 m^4 +
41731645440 m^5 + 21016670208 m^6 + 1903757312 m^7}
(end)
1; 2; 4,2; 8,16; 16,88,16; 32,416,272; 64,1824,2880,272; ... T(3,1)=2 because we have 132 and 231.
|
|
|
MAPLE
| Comment from Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 26 2009: The Maple program yields (by straightforward counting) the generating polynomial of the row n specified in the program.
n := 8: with(combinat): P := permute(n): st := proc (p) local ct, j: ct := 0: for j from 2 to nops(p)-1 do if p[j-1] < p[j] and p[j+1] < p[j] then ct := ct+1 else end if end do: ct end proc: sort(add(t^st(P[j]), j = 1 .. factorial(n))); [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 26 2009]
a := 1+sqrt(1-t): b := 1-sqrt(1-t): G := (exp(b*z)-exp(a*z))/(b*exp(a*z)-a*exp(b*z)): Gser := simplify(series(G, z = 0, 15)): for n to 12 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n to 12 do seq(coeff(P[n], t, j), j = 0 .. ceil((1/2)*n)-1) end do; # yields sequence in triangular form [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 26 2009]
|
|
|
MATHEMATICA
| m = 14; a = 1 + Sqrt[1 - t]; b = 1 - Sqrt[1 - t];
g[z_] = (E^(b*z) - E^(a*z))/(b*E^(a*z) - a*E^(b*z));
gser = Series[g[z], {z, 0, m}];
Do[p[n]=n!*Coefficient[gser, z, n]//Simplify, {n, 0, m}];
Flatten[ Table[ Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
(* From Jean-François Alcover, May 27 2011, after E. Deutsch *)
|
|
|
PROG
| (C++)
#include <vector>
#include <iostream>
using namespace std;
int peaks(const vector<int> & perm) {
int pks=0;
for(int i=1 ; i < perm.size()-1; i++)
if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) pks++;
return pks ;
}
int main(int argc, char *argv[]) {
int n=1;
if ( argc > 1 ) n=atoi(argv[1]);
int nmax = n+12;
if ( argc > 2 ) nmax=atoi(argv[2]);
for (; n < nmax ; n++) {
const int kmax = (n+1)/2;
vector<int> Tnk(kmax);
vector<int> perm(n);
for(int i=0 ; i < n ; i++) perm[i]=i+1;
int pks = peaks(perm);
Tnk[pks]++;
while ( next_permutation(perm.begin(), perm.end()) ) {
pks = peaks(perm);
Tnk[pks]++;
}
for (int i=0; i < Tnk.size(); i++) cout << Tnk[i] << ", " ;
}
}
/* R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jun 26 2007 */
|
|
|
CROSSREFS
| Column k=1 yields A000431, column k=2 yields A000487, column k=3 yields A000517.
Cf. A000111, A101280.
Cf. A090672, A000182. [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 26 2009].
Cf. A185896.
Sequence in context: A051288 A120434 A187619 * A058942 A196759 A188813
Adjacent sequences: A008300 A008301 A008302 * A008304 A008305 A008306
|
|
|
KEYWORD
| tabf,nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Additional comments from Emeric Deutsch (deutsch(AT)duke.poly.edu), May 08 2004
More terms from R. J. Mathar (mathar(AT)strw.leidenuniv.nl) and Vladeta Jovovic (vladeta(AT)eunet.rs), Jun 26 2007
Corrected by Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 26 2009
|
| |
|
|
