|
| |
|
|
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.
|
|
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^(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
|
|
|
|
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;
...
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)):
# 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
|
|
|
|
EXTENSIONS
|
Definition corrected by Julian Gilbey, Jul 26 2007
|
|
|
STATUS
|
approved
|
| |
|
|
