

A060351


If the binary expansion of n has k bits, let S be the subset of [k1] such that i is in S if the ith 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.


19



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

a(n) is the number of permutations in the symmetric group S_k such that n = 2^(k1) + the sum of 2^(i1), 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) = 916+114 = 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 n1 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 "updown 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), 116123.


LINKS



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^r1} {n,i} = n*(n1)*...*(nr+1).
For n >= 1, 0 <= k < 2^(n1), {n,k} <= {n,r_n}, where r_n=(2^n2)/3, if n is odd, r_n=(2^n1)/3, if n is even.
Equality holds iff k=r_n or 2^(n1)r_n1, 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 ShevelevSpilker 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;
...
Consider {4,2} (see comments). k=010 (41 binary digits).
So {4,2} is the number of downupdown 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 ith row contains ceiling(2^(i1)) entries with row sum i!, i>=0.
(End)
The binary expansion of n=11 is 1011, which has k=4 digits. Of the first k1=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^(i1)), 2) = 1 and irem(iquo(2*k, 2^(i1)), 2) =0 then out := out+(n1)!/(i1)!/(ni)!* ct(floor(irem(k, 2^(i1))+2^(i2)))*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(uj, o+j1, t+1)*x^floor(2^(t1)), j=1..u)+
add(b(u+j1, oj, t+1), j=1..o)))
end:
T:= n> (p> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
# 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(uj, o+j1, iquo(t, 2)), j=1..u),
add(b(u+j1, oj, iquo(t, 2)), j=1..o)))
end:
T:= (n, k)> b(n, 0, 2*k):
seq(seq(T(n, k), k=0..ceil(2^(n1))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^(n1)1}] // Flatten (* JeanFrançois Alcover, Jul 16 2017, after Vladimir Shevelev *)
P[n_, x_] := P[n, x] = (1/(1x^2^(n1)))(Product[1x^2^k, {k, 0, (n1)}] + Sum[Binomial[n, i] Product[1x^2^k, {k, i, n1}] x^2^(i1) P[i, x], {i, 1, n1}]) // Simplify; P[1, _] = 1; Table[CoefficientList[P[n, x], x], {n, 1, 7}] // Flatten (* JeanFrançois Alcover, Sep 06 2018, after Vladimir Shevelev *)


CROSSREFS



KEYWORD



AUTHOR



EXTENSIONS

Definition corrected by Julian Gilbey, Jul 26 2007


STATUS

approved



