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.
1, 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
Offset: 0
Examples
Interpreted as a triangle:
1;
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:
{0,0}
{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 ceiling(2^(i-1)) entries with row sum i!, i>=0.
(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
References
- I. Niven, A combinatorial problem of finite sequences, Nieuw Arch. Wisk. (3) 16 (1968), 116-123.
Links
- Alois P. Heinz, Rows n = 0..14, flattened (rows n=1..12 from Wouter Meeussen)
- N. G. de Bruijn, Permutations with given ups and downs, Nieuw Arch. 18 (1970), 61-65.
- Vladimir Shevelev, On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure, arXiv:0801.0072 [math.CO], 2007-2010. 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.
- Vladimir Shevelev and J. Spilker, Up-down coefficients for permutations, Elem. Math. 68 (2013), 115-127.
Crossrefs
Programs
-
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=0..64); # second Maple program: b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1, add(b(u-j, o+j-1, t+1)*x^floor(2^(t-1)), j=1..u)+ add(b(u+j-1, o-j, t+1), j=1..o))) end: T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)): seq(T(n), n=0..7); # Alois P. Heinz, Sep 08 2020 # third Maple program: b:= proc(u, o, t) option remember; `if`(u+o=0, `if`(t=0, 1, 0), `if`(irem(t, 2)=0, add(b(u-j, o+j-1, iquo(t, 2)), j=1..u), add(b(u+j-1, o-j, iquo(t, 2)), j=1..o))) end: T:= (n, k)-> b(n, 0, 2*k): seq(seq(T(n, k), k=0..ceil(2^(n-1))-1), n=0..7); # Alois P. Heinz, Sep 12 2020 -
Mathematica
<
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
Extensions
Definition corrected by Julian Gilbey, Jul 26 2007
T(0,0)=1 prepended by Alois P. Heinz, Sep 08 2020
Comments