login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A203827 Table of coefficients of up-down polynomials P_n(m) = Sum_{i=0..floor(log_2(2n))} binomial(m,i). 1
1, -1, 1, -1, 0, 1, 1, -1, 1, -1, 0, 0, 1, 1, -1, 0, 2, 1, 0, -1, 2, -1, 1, -1, 1, -1, 0, 0, 0, 1, 1, -1, 0, 0, 3, 1, 0, -1, 0, 5, -1, 1, -1, 0, 3, 1, 0, 0, -1, 3, -1, 1, 0, -2, 5, -1, 0, 1, -2, 3, 1, -1, 1, -1, 1, -1, 0, 0, 0, 0, 1, 1, -1, 0, 0, 0, 4, 1, 0, -1, 0, 0, 9 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,17

COMMENTS

For a permutation s = (s_1,...,s_m), the number n = Sum_{j=1..m-1} b_j*2^(m-i-1), where b_j=1, if s_(j+1) > s_j, and b_j=0, if s_(j+1) < s_j, is called index of s. Up-down polynomial P_n(m) gives the number of permutations with index n.

If n = 2^(k_1-1) + 2^(k_2-1) + ... + 2^(k_r-1), k_1 > ... > k_r >= 1, then k_1,k_2,...,k_r are only positive roots of the polynomial P_n(m).

If F(m,x) = Sum_{n>=0} P_n(m)*x^n and t(x) = Sum_{n>=0} t_n*x^n (|x|<1), where t_n = (-1)^A010060(n), then F(m,x)/t(x) is a rational function.

The sequence {n_k} for which P_(n_k)(m) has a root m=-1 begins 2, 5, 8, 11, 23, ...

If n is in A089633, then P_n(m) has only real roots.

Remark from the author. Ivan Niven posed the problem of enumeration of permutations of n elements with a given up-down structure. He introduced (n-1)-dimensional parameter (Niven's signature) and did the enumeration in a determinant form, but did not find simple relations. Therefore, the title of his paper includes the word "problem". Instead of his many-dimensional parameter, the author introduced one-dimensional parameter (index). It allowed us to find many simple relations and properties for the enumeration numbers which is called up-down coefficients since they have many close properties with the binomial coefficients. In particular, they give a decomposition of Eulerian numbers. Many other relations will appear in the paper by the author and U. Spilker (to appear), where, in particular, we prove that the enumeration numbers are maximal when the index corresponds to the alternating (or Andre) permutations.

REFERENCES

I. Niven, A combinatorial problem of finite sequences, Nieuw Arch. Wisk. 16(1968), 116-123.

LINKS

Table of n, a(n) for n=0..82.

V. Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS 12 (2012), article #A1.

FORMULA

Sum_{n=0..2^(m-1)} P_n(m) = m!;

Sum_{n=0..2^m-1} (-1)^n*P_n(m) = 0.

P_{2^m-1}(2*m) = binomial(2*m-1, m-1);

P_{2^m-1}(2*m+1) = binomial(2*m, m).

If m is an odd prime, then

(1) P_n(m) == t_n (mod m), where t_n = (-1)^A010060(n);

(2) P_((2^(m+1)-4)/6)(m) == (-1)^((m-1)/2) (mod m);

(3) P_((2^(2*m+1)-2)/6)(2*m) == 1 (mod 2*m).

For m >= 1, P_((2^(2^m+1)-2)/6)(2^m) == 1 (mod 2^m).

P_((4^m-1)/3)(2*m) = |E_(2*m)| (cf. A000364);

P_((2^(2*m-1)-1)/3) = |B_(2*m)|*4^m(4^m-1)/(2*m) (cf. A002105).

If n = 2^(k_1-1) + 2^(k_2-1) + ... + 2^(k_r-1), k_1 > k_2 > ... > k_r >= 1, then

(Recursion 1) P_n(m) = (-1)^r + Sum_{i=1..r} binomial(m,k_i)*P_(n-2^(k_i-1))(k_i) and

(Recursion 2) for h > k_1, P_(n+2^(h-1))(m) = binomial(m,h)*P_n(h) - P_n(m).

EXAMPLE

Table begins

   1

  -1  1

  -1  0  1

   1 -1  1

  -1  0  0  1

   1 -1  0  2

   1  0 -1  2

  -1  1 -1  1

  -1  0  0  0  1

   1 -1  0  0  3

   1  0 -1  0  5

  -1  1 -1  0  3

   1  0  0 -1  3

  -1  1  0 -2  5

  -1  0  1 -2  3

   1 -1  1 -1  1

  -1  0  0  0  0  1

   1 -1  0  0  0  4

   1  0 -1  0  0  9

CROSSREFS

Cf. A010060, A000984, A000364, A002105, A008292.

Sequence in context: A094713 A123517 A178948 * A194289 A237194 A143519

Adjacent sequences:  A203824 A203825 A203826 * A203828 A203829 A203830

KEYWORD

sign,tabf

AUTHOR

Vladimir Shevelev, Jan 06 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 10 13:04 EDT 2020. Contains 335576 sequences. (Running on oeis4.)