A089633 -id:A089633 - cp's OEIS frontend

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

Vladimir Shevelev, Jan 06 2012

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.

			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

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

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

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

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

A249452 Numbers k such that A249441(k) = 3.

Original entry on oeis.org

15, 31, 47, 63, 95, 127, 191, 255, 383, 511, 767, 1023, 1535, 2047, 3071, 4095, 6143, 8191, 12287, 16383, 24575, 32767, 49151, 65535, 98303, 131071, 196607, 262143, 393215, 524287, 786431, 1048575, 1572863, 2097151, 3145727, 4194303, 6291455, 8388607, 12582911

Offset: 1

Vladimir Shevelev, Oct 29 2014

Or k for which none of entries in the k-th row of Pascal's triangle (A007318) is divisible by 4 (cf. comment in A249441).
Using the Kummer carries theorem, one can prove that, for n>=2, a(n) has the form of either 1...1 or 101...1 in base 2.
The sequence is a subset of so-called binomial coefficient predictors (BCP) in base 2 (see Shevelev link, Th. 6 and Cor. 8), which were found also using Kummer theorem and have a very close binary structure.

E. E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93-146.
V. Shevelev, Binomial Coefficient Predictors, Journal of Integer Sequences, Vol. 14 (2011), Article 11.2.8
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A000225, A029744, A048278, A052955, A055010, A089633, A249441.

CoefficientList[Series[(15 + 16 x - 14 x^2 - 16 x^3)/(1 - x -2 x^2 + 2 x^3), {x, 0, 70}], x] (* Vincenzo Librandi, Oct 30 2014 *)
LinearRecurrence[{1,2,-2},{15,31,47,63},40] (* Harvey P. Dale, Apr 01 2019 *)

a(n)=if(n==1, 15, (n%2+2)<<(n\2+3)-1) \\ Charles R Greathouse IV, Nov 06 2014

is(n)=(n+1)>>valuation(n+1, 2)<5 && !setsearch([1, 2, 3, 5, 7, 11, 23], n) \\ Charles R Greathouse IV, Nov 06 2014

a(n) has either form 2^k - 1 or 3*2^m-1, k, m >= 4 (cf. A000225, A055010). Since, for k>=5, 2^k-1<3*2^(k-1)-1<2^(k+1)-1, we have that, for n>=1, a(2*n) = 2^(n+4)-1; a(2*n+1) = 3*2^(n+3)-1. - Vladimir Shevelev, Oct 29 2014, Nov 06 2014
a(1) = 15, and for n>1, a(n) = A052955(n+6). [Follows from above] - Antti Karttunen, Nov 03 2014
G.f.: (15+16*x-14*x^2-16*x^3)/(1-x-2*x^2+2*x^3); a(n) = 16*A029744(n)-1. - Peter J. C. Moses, Oct 30 2014

More terms from Peter J. C. Moses, Oct 29 2014

A262882 Right diagonal of A262881.

Original entry on oeis.org

0, 1, 2, 3, 3, 5, 6, 7, 7, 7, 7, 11, 11, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15, 23, 23, 23, 23, 27, 27, 29, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 47, 47, 47, 47, 47, 47, 47, 47, 55, 55, 55, 55, 59, 59, 61, 62, 63, 63, 63, 63, 63

Offset: 0

Michel Marcus, Oct 04 2015

It appears that the sequence of unique terms is A089633, and that their run lengths are 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 8, ...: A155038.

Cf. A089633, A155038, A262881.

Last /@ Table[SortBy[Range@ k, And[Total@ IntegerDigits[#, 2], k] &], {k, 67}] (* Michael De Vlieger, Oct 04 2015 *)

cmph(i, j) = if (hammingweight(i) != hammingweight(j), hammingweight(i) - hammingweight(j), i - j);
row(n) = my(v = vector(n+1, k, k-1)); vecsort(v, cmph);
lista(nn) = {for (n=0, nn, my(r = srow(n)); print1(r[#r], ", "););}

A301984 a(n) is the greatest positive number k such that the binary digits of any number in the interval 1..k appear in order but not necessarily as consecutive digits in the binary representation of n.

Original entry on oeis.org

1, 2, 1, 2, 3, 3, 1, 2, 5, 6, 3, 4, 3, 3, 1, 2, 5, 6, 5, 6, 7, 7, 3, 4, 7, 7, 3, 4, 3, 3, 1, 2, 5, 6, 5, 6, 11, 11, 5, 6, 13, 14, 7, 8, 7, 7, 3, 4, 9, 10, 7, 8, 7, 7, 3, 4, 7, 7, 3, 4, 3, 3, 1, 2, 5, 6, 5, 6, 11, 11, 5, 6, 13, 14, 11, 12, 11, 11, 5, 6, 13, 14

Offset: 1

Rémy Sigrist, Mar 30 2018

Equivalently, a(n) is the greatest positive number k such that A301983(n, k) = k.

Apparently, the k-th record value is A089633(k), and the first term with this value has index A048678(A089633(k)).

			The 13th row of A301983 is: 1, 2, 3, 5, 6, 7, 13; all numbers in the range 1..3 appear in this row, but the number 4 is missing; hence a(13) = 3.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n

Cf. A048678, A089633, A261461, A301977, A301983.

a(n) = my (b=binary(n), s=Set(1)); for (i=2, #b, s = setunion(s, Set(apply(v -> 2*v+b[i], s)))); for (u=1, oo, if (!setsearch(s,u), return (u-1)))

a(n) <= A301977(n).
a(2*n) >= a(n).
a(2*n + 1) >= a(n) (with strict inequality if a(n) is even).
a(n) = 1 iff n is positive and belongs to A000225.

cp's OEIS Frontend

A203827 Table of coefficients of up-down polynomials P_n(m) = Sum_{i=0..floor(log_2(2n))} binomial(m,i).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A249452 Numbers k such that A249441(k) = 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A262882 Right diagonal of A262881.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A301984 a(n) is the greatest positive number k such that the binary digits of any number in the interval 1..k appear in order but not necessarily as consecutive digits in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A188535 Intersection of A188341 and A188532.

Views

Author

Keywords

Comments

Links

Crossrefs