

A203827


Table of coefficients of updown 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..m1} b_j*2^(mi1), 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. Updown polynomial P_n(m) gives the number of permutations with index n.
If n = 2^(k_11) + 2^(k_21) + ... + 2^(k_r1), 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 updown structure. He introduced (n1)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 manydimensional parameter, the author introduced onedimensional parameter (index). It allowed us to find many simple relations and properties for the enumeration numbers which is called updown 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), 116123.


LINKS



FORMULA

Sum_{n=0..2^(m1)} P_n(m) = m!;
Sum_{n=0..2^m1} (1)^n*P_n(m) = 0.
P_{2^m1}(2*m) = binomial(2*m1, m1);
P_{2^m1}(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)^((m1)/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^m1)/3)(2*m) = E_(2*m) (cf. A000364);
P_((2^(2*m1)1)/3) = B_(2*m)*4^m(4^m1)/(2*m) (cf. A002105).
If n = 2^(k_11) + 2^(k_21) + ... + 2^(k_r1), k_1 > k_2 > ... > k_r >= 1, then
(Recursion 1) P_n(m) = (1)^r + Sum_{i=1..r} binomial(m,k_i)*P_(n2^(k_i1))(k_i) and
(Recursion 2) for h > k_1, P_(n+2^(h1))(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



KEYWORD

sign,tabf


AUTHOR



STATUS

approved



