|
| |
|
|
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,...,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
|
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)=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
|
| |
|
|
