|
| |
|
|
A001586
|
|
Generalized Euler numbers, or Springer numbers.
(Formerly M2908 N1169)
|
|
25
| |
|
|
1, 1, 3, 11, 57, 361, 2763, 24611, 250737, 2873041, 36581523, 512343611, 7828053417, 129570724921, 2309644635483, 44110959165011, 898621108880097, 19450718635716001, 445777636063460643, 10784052561125704811, 274613643571568682777, 7342627959965776406281
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| The Springer numbers were originally considered by Glaisher (see
references). They are a type B analog of the zigzag numbers A000111 for
the group of signed permutations.
COMBINATORIAL INTERPRETATIONS
Several combinatorial interpretations of the Springer numbers are known:
1) a(n) counts the number of Weyl chambers in the principal Springer cone
of the Coxeter group B_n of symmetries of an n dimensional cube. An
example can be found in [Arnold - The Calculus of snakes...].
2) Arnold found an alternative combinatorial interpretation of the
Springer numbers in terms of snakes. Snakes are a generalization of
alternating permutations to the group of signed permutations. A signed
permutation is a sequence (x_1,x_2,...,x_n) of integers such that
{|x_1|,|x_2|,...,|x_n|} = {1,2,...,n}. They form a group, the
hyperoctahedral group of order 2^n*n! = A000165(n), isomorphic to the
group of symmetries of the n dimensional cube.
A snake of type B_n is a signed permutation (x_1,x_2,...,x_n) such that
0 < x_1 > x_2 < ... x_n. For example, (3,-4,-2,-5,1,-6) is a snake of
type B_6. a(n) counts the number of snakes of type B_n [Arnold]. The
cases n=2 and n=3 are given in the Example section below.
3) The Springer numbers also arise in the study of the critical points of
functions; they count the topological types of odd functions with 2*n
critical values [Arnold, Theorem 35].
4) Let F_n be the set of plane rooted forests satisfying the following
conditions:
... each root has exactly one child, and each of the other internal nodes
has exactly two (ordered) children,
... there are n nodes labelled by integers from 1 to n, but some leaves
can be non-labelled (these are called empty leaves), and labels are
increasing from each root down to the leaves.
Then a(n) equals the cardinality of F_n. An example and proof are given
in [Verges, Theorem 4.5].
OTHER APPEARANCES OF THE SPRINGER NUMBERS
1) Hoffman has given a connection between Springer numbers, snakes and
the successive derivatives of the secant and tangent functions.
2) For integer N the quarter Gauss sums Q(N) are defined by
... Q(N) := sum {r = 0..floor(N/4)} exp(2*Pi*I*r^2/N).
In the cases N = 1 (mod 4) and N = 3 (mod 4) an asymptotic series for
Q(N) as N - > inf that involves the Springer numbers has been given by
Evans et al., see 1.32 and 1.33].
For a sequence of polynomials related to the Springer numbers see
A185417. For a table to recursively compute the Springer numbers see
A185418.
|
|
|
REFERENCES
| V. I. Arnold, Springer numbers and Morsification spaces. J. Algebraic Geom. 1 (1992), no. 2, 197-214.
V. I. Arnold, The calculus of snakes and the combinatorics of Bernoulli, Euler and Springer numbers of Coxeter groups, Uspekhi Mat. nauk., 47 (#1, 1992), 3-45 = Russian Math. Surveys, Vol. 47 (1992), 1-51.
D. Dumont, Further triangles of Seidel-Arnold type and continued fractions related to Euler and Springer numbers, Adv. Appl. Math., 16 (1995), 275-296.
J. W. L. Glaisher, "On the coefficients in the expansions of cos x/cos 2x and sin x/cos 2x", Quart. J. Pure and Applied Math., 45 (1914), 187-222.
J. W. L. Glaisher, On the Bernoullian function, Q. J. Pure Appl. Math., 29 (1898), 1-168.
J. W. L. Glaisher, On a set of coefficients analogous to the Eulerian numbers, Proc. London Math. Soc., 31 (1899), 216-235.
M. Josuat-Verges, J.-C. Novelli and J.-Y. Thibon, The algebraic combinatorics of snakes, Arxiv preprint arXiv:1110.5272, 2011
Ulrike Sattler, Decidable classes of formal power series with nice closure properties, Diplomarbeit im Fach Informatik, Univ. Erlangen - Nuernberg, Jul 27 1994
D. Shanks, Generalized Euler and class numbers, Math. Comp. 21 (1967), 689-694; 22 (1968), 699.
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.A. Springer, Remarks on a combinatorial problem, Nieuw Arch. Wisk. 19(3) (1971), 30-36.
Zhi-Hong Sun, Congruences involving Bernoulli polynomials, Discr. Math.,
308 (2007), 71-112.
A. Vieru, Agoh's conjecture: its proof, its generalizations, its analogues, Arxiv preprint arXiv:1107.2938, 2011.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..100
W. Y. C. Chen, N. J. Y. Fan and J. Y. T. Jia, Labeled Ballot Paths and the Springer Numbers, Sep 12, 2010. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Sep 13 2010]
M. E. Hoffman, DERIVATIVE POLYNOMIALS, EULER POLYNOMIALS, AND ASSOCIATED INTEGER SEQUENCES (see Th. 3.1)
R. Evans, M. Minei and B. Yee, Incomplete higher order Gauss sums (see 1.32 and 1.33)
M. J-Verges, Enumeration of snakes and cycle-alternating permutations
|
|
|
FORMULA
| E.g.f.: 1/(cos x - sin x).
Values at 1 of polynomials Q_n() defined in A104035. - N. J. A. Sloane, Nov 06 2009
a(n) = numerator of Euler(n,1/4). - N. J. A. Sloane, Nov 07 2009
Let B_n(x) = Sum_{k=0.. n*(n-1)/2} b(n,k)*x^k, where b(n,k) is number of n-node acyclic digraphs with k arcs, cf. A081064; then a(n) = |B_n(-2)|. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jan 25 2005
G.f. A(x)=y satisfies y'^2=2y^4-y^2, y''y=y^2+2y'^2. - Michael Somos Feb 03 2004
a(n) = (-1)^Floor(n/2) Sum_{k=0..n} 2^k C(n,k) Euler(k) [From Peter Luschny (peter(AT)luschny.de), Jul 08 2009]
From Peter Bala [Start]
(1)... a(n) = ((1+I)/2)^n*B(n,(1-I)/(1+I)), where I = sqrt(-1) and
{B(n,x)}n>=0 = [1,1+x,1+6*x+x^2,1+23*x+23*x^2+x^3,...] is the sequence of
type B Eulerian polynomials - see A060187.
This yields the explicit formula
(2)... a(n) = ((1+I)/2)^n*sum {k = 0..n} ((1-I)/(1+I))^k *
sum {j = 0..k} (-1)^(k-j)*binomial(n+1,k-j)*(2j+1)^n.
The result (2) can be used to find congruences satisfied by the Springer
numbers. For example, for odd prime p
(3)
... a(p) = 1 (mod p) when p = 8*n+1 or p = 8*n+5
... a(p) = -1 (mod p) when p = 8*n+3 or 8*n+7.
[End]
E.g.f.: 1/(cos(x)-sin(x))=1/Q(0); Q(k)=1-x/((2k+1)-x*(2k+1)/(x+(2k+2)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 19 2011
|
|
|
EXAMPLE
| Example
a(2)=3: The three snakes of type B_2 are
(1,-2), (2,1), (2,-1).
a(3)=11: The 11 snakes of type B_3 are
(1,-2,3), (1,-3,2), (1,-3,-2),
(2,1,3), (2,-1,3), (2,-3,1), (2,-3,-1),
(3,1,2), (3,-1,2), (3,-2,1), (3,-2,-1).
|
|
|
MAPLE
| a := proc(n) local k; (-1)^iquo(n, 2)*add(2^k*binomial(n, k)*euler(k), k=0..n) end; [From Peter Luschny (peter(AT)luschny.de), Jul 08 2009]
|
|
|
MATHEMATICA
| n=21; CoefficientList[Series[1/(Cos[x]-Sin[x]), {x, 0, n}], x] * Table[k!, {k, 0, n}] (* From Jean-François Alcover, May 18 2011, after M. Somos *)
Table[Abs[Numerator[EulerE[n, 1/4]]], {n, 0, 35}] (* From Harvey P. Dale, May 18 2011 *)
|
|
|
PROG
| (PARI) a(n)=if(n<0, 0, n!*polcoeff(1/(cos(x+x*O(x^n))-sin(x+x*O(x^n))), n)) (from Michael Somos)
(PARI) {a(n)=local(an); if(n<2, n>=0, an=vector(n+1, m, 1); for(m=2, n, an[m+1]=2*an[m]+an[m-1]+sum(k=0, m-3, binomial(m-2, k)*( an[k+1]*an[m-1-k]+2*an[k+2]*an[m-k]-an[k+3]*an[m-1-k] ))); an[n+1])} (from Michael Somos)
(PARI) /* Explicit formula by Peter Bala: */
{a(n)=((1+I)/2)^n*sum(k=0, n, ((1-I)/(1+I))^k*sum(j=0, k, (-1)^(k-j)*binomial(n+1, k-j)*(2*j+1)^n))}
|
|
|
CROSSREFS
| Cf. A007836.
Bisections are A000281 and A000464.
Related polynomials are given in A098432.
Cf. A079858. A185417, A185418
Sequence in context: A052442 A180112 A188458 * A126201 A020012 A126100
Adjacent sequences: A001583 A001584 A001585 * A001587 A001588 A001589
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Vladeta Jovovic (vladeta(AT)eunet.rs), Jan 25 2005
|
| |
|
|
