This site is supported by donations to The OEIS Foundation.

 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)...>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,...,infty}P_n(m)*x^n and t(x)=sum{n=0,...,infty}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 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 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)=Binom(2*m-1, m-1); P_{2^m-1}(2*m+1)=Binom(2*m, m).    If m is 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}Binom(m,k_i)*P_(n-2^(k_i-1))(k_i) and (Recursion 2) for h>k_1, P_(n+2^(h-1))(m)=Binom (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 A143519 A029376 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 | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .