login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060351 If the binary expansion of n has k bits, let S be the subset of [k-1] such that i is in S if the i-th bit of n is a 1 (with the first bit being the least significant bit); a(n) is the number of permutations of [k] with descent set S. 12
1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 3, 3, 5, 3, 1, 1, 4, 9, 6, 9, 16, 11, 4, 4, 11, 16, 9, 6, 9, 4, 1, 1, 5, 14, 10, 19, 35, 26, 10, 14, 40, 61, 35, 26, 40, 19, 5, 5, 19, 40, 26, 35, 61, 40, 14, 10, 26, 35, 19, 10, 14, 5, 1, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

a(n) is the number of permutations in the symmetric group S_k such that n = 2^(k-1) + the sum of 2^(i-1), where i is a descent of the permutation and k = number of digits in the binary expansion of n.

If n=4m then a(n)-a(n+1)+a(n+2)-a(n+3)=0. This follows from Theorem 10 of my paper arXiv:0801.0072v1. E.g. a(20)-a(21)+a(22)-a(23)= 9-16+11-4=0. - Vladimir Shevelev, Jan 07 2008

Denote by {n,k} the number of permutations of {0,1,...n} such that the binary expansion of k with n-1 digits (the expansion is allowed to begin with 0's) indicates a fixed distribution of "up"(1) and "down"(0) points. The numbers {n,k} are called "up-down coefficients" of permutations, since they have many similar properties to binomial coefficients C(n,k) (see Shevelev et al. references). The sequence lists the rows numbers {n,k} as a triangle read by rows (see example).- Vladimir Shevelev, Feb 13 2014

REFERENCES

N. G. de Bruijn, Permutations with given ups and downs, Nieuw Arch. 18 (1970), 61-65.

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

LINKS

Wouter Meeussen, Table of n, a(n) for n = 1..4095

Vladimir Shevelev, On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure, arXiv:math.CO/0801.0072. See remarks following Theorem 22.

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

V. Shevelev and J. Spilker, Up-down coefficients for permutations, Elem. Math. 68 (2013), 115-127.

FORMULA

{n+1,2*k} + {n+1,2*k+1) = (n+1)*{n,k},

{n+2,4*k} + {n+2,4*k+2} = {n+2, 4*k+1} + {n+2,4*k+1} + {n+2,4*k+3} = (n+2)*(n+1)/2 * {n,k}, etc.

Sum_{i=0,...,2^r-1} {n,i} = n*(n-1)*...*(n-r+1).

For n>=1, 0<=k<2^{n-1), {n,k}<={n,r_n}, where r_n=(2^n-2)/3, if n is odd, r_n=(2^n-1)/3, if n is even.

Equality holds iff k=r_n or 2^(n-1)-r_n-1, which corresponds the case of alternating permutations. De Bruijn mentioned that Niven knew the latter result, but he never published this statement. A proof can be found in the Shevelev and Spilker reference (Section 5).

Many other equalities, recursions and unequalities can be found in Shevelev and Shevelev-Spilker references. - Vladimir Shevelev, Feb 13 2014

EXAMPLE

Interpreted as a triangle:

1;

1, 1;

1, 2, 2, 1;

1, 3, 5, 3, 3, 5, 3, 1'

1, 4, 9, 6, 9, 16, 11, 4, 4, 11, 16, 9, 6, 9, 4, 1;

1, 5, 14, 10, 19, 35, 26, 10, 14, 40, 61, 35, 26, 40, 19, 5, 5, 19, 40, 26, 35, 61, 40, 14, 10, 26, 35, 19, 10, 14, 5, 1;

...

From Vladimir Shevelev, Feb 13 2014: (Start)

Consider {4,2} (see comments). k=010 (4-1 binary digits).

So {4,2} is the number of down-up-down permutations of {1,2,3,4}. We have 5 such permutations (2,1,4,3),(3,1,4,2),(3,2,4,1),(4,1,3,2) and (4,2,3,1). Thus {4,2}=5.

Over rows, the sequence has the form:

{1,0}

{2,0} {2,1}

{3,0} {3,1} {3,2} {3,3}

{4,0} {4,1} {4,2} {4,3} {4,4} {4,5} {4,6} {4,7}

.......

such that the i-th row contains 2^(i-1) entries with row sum i!, i=1,2,...

(End)

The binary expansion of n=11 is 1011, which has k=4 digits. Of the first k-1=3 bits, starting from the least significant bit on the right, the first and second are 1, so S={1,2}. The a(11)=3 permutations of [k]={1,2,3,4} with descent set S={1,2} are {3,2,1,4}, {4,2,1,3}, and {4,3,1,2}. - Danny Rorabaugh, Apr 02 2015

MAPLE

ct := proc(k) option remember; local i, out, n; if k=0 then RETURN(1); fi; n := floor(evalf(log[2](k)))+1; if k=2^n or k=2^(n+1)-1 then RETURN(1); fi; out := 0; for i from 1 to n do if irem(iquo(k, 2^(i-1)), 2) = 1 and irem(iquo(2*k, 2^(i-1)), 2) =0 then out := out+(n-1)!/(i-1)!/(n-i)!* ct(floor(irem(k, 2^(i-1))+2^(i-2)))*ct(iquo(k, 2^i)); fi; od; out; end: seq(ct(i), i=1..64)

MATHEMATICA

<<DiscreteMath`Combinatorica`; binDescents[perm_List]:= FromDigits[Sign[Rest[perm] - Drop[perm, -1]]/2 + 1/2, 2]; Table[CoefficientList[Apply[Plus, ((Length[#1]*x^#1 & )[Flatten[Outer[binDescents[TableauxToPermutation[#1, #2]] & , {FirstLexicographicTableau[#1]}, Tableaux[#1], 1]]] & ) /@ Partitions[w], {0, 1}], x], {w, 2, 7}] (* Wouter Meeussen, Jan 30 2012 *)

CROSSREFS

Cf. A060350.

Sequence in context: A034254 A157103 A135966 * A076037 A215563 A076263

Adjacent sequences:  A060348 A060349 A060350 * A060352 A060353 A060354

KEYWORD

easy,base,nonn,tabf

AUTHOR

Mike Zabrocki, Mar 31 2001

EXTENSIONS

Definition corrected by Julian Gilbey, Jul 26 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 28 04:43 EDT 2017. Contains 288813 sequences.