OFFSET
0,6
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
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.
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;
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
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
<<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 *)
upDown[n_, k_] := upDown[n, k] = Module[{t, m}, t = Flatten[ Reverse[ Position[ Reverse[ IntegerDigits[k, 2]], 1]]]; m = Length[t]; (-1)^m + Sum[upDown[t[[j]], k - 2^(t[[j]]-1)]*Binomial[n, t[[j]]], {j, 1, m}]]; Table[upDown[n, k], {n, 1, 7}, {k, 0, 2^(n-1)-1}] // Flatten (* Jean-François Alcover, Jul 16 2017, after Vladimir Shevelev *)
P[n_, x_] := P[n, x] = (1/(1-x^2^(n-1)))(Product[1-x^2^k, {k, 0, (n-1)}] + Sum[Binomial[n, i] Product[1-x^2^k, {k, i, n-1}] x^2^(i-1) P[i, x], {i, 1, n-1}]) // Simplify; P[1, _] = 1; Table[CoefficientList[P[n, x], x], {n, 1, 7}] // Flatten (* Jean-François Alcover, Sep 06 2018, after Vladimir Shevelev *)
CROSSREFS
KEYWORD
AUTHOR
Mike Zabrocki, Mar 31 2001
EXTENSIONS
Definition corrected by Julian Gilbey, Jul 26 2007
T(0,0)=1 prepended by Alois P. Heinz, Sep 08 2020
STATUS
approved