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, 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

Offset: 0

Author

Vladimir Shevelev, Jan 06 2012

Keywords

• sign
• tabf

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.

Examples

			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
		

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.

Crossrefs

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

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