|
| |
|
|
A060351
|
|
If the binary expansion of n has k bits, then let S be the subset of [k-1] such that i in S if the i-th bit of n is a 1 (with the first bit being the 0-th bit); a(n) is the number of permutations of [k] with descent set S.
|
|
6
| |
|
|
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; 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.org/abs/0801.0072v1. E.g. a(20)-a(21)+a(22)-a(23)= 9-16+11-4=0. - Vladimir Shevelev (shevelev(AT)bgu.ac.il), Jan 07 2008
|
|
|
LINKS
| Wouter Meeussen, Table of n, a(n) for n = 1..4095
|
|
|
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 A076263 A008302
Adjacent sequences: A060348 A060349 A060350 * A060352 A060353 A060354
|
|
|
KEYWORD
| easy,nonn,changed
|
|
|
AUTHOR
| Mike Zabrocki (zabrocki(AT)mathstat.yorku.ca), Mar 31 2001
|
|
|
EXTENSIONS
| Definition corrected by Julian Gilbey, Jul 26 2007
|
| |
|
|
