9
$\begingroup$

The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ is defined by $D(w)=\{ 1\leq i\leq n-1\,:\, a_i>a_{i+1}\}$.

Given a set $S$, let $\beta_n(S)$ denote the number of permutations $w\in\frak{S}_n$ with $D(w)=S$, and let $f(n)$ be the number of subsets $S$ of $\{1,2,\dots,n-1\}$ for which $\beta_n(S)$ is odd.

QUESTION. Is there a nice formula, recurrence, etc., for $f(n)$? The values of $f(n)$ for $1\leq n\leq 15$ are (up to some glitch in my Maple code) $$ 1,2,2,8,8,16,32,128,128,256,512,1024,2048,4096,7424. $$

Note. A closely related problem is to look at permutations $w\in \frak{S}_n$ whose descent set is contained in $S$. Let $\alpha_n(S)$ denote the number of such permutations (which is equal to a simple multinomial coefficient). Let $g(n)$ be the number of subsets $S$ of $\{1,2,\dots,n-1\}$ for which $\alpha_n(S)$ is odd. It is not hard to show that $g(n)$ is equal to the number of ordered set partitions of $\{1,2,\dots,b(n)\}$, where $b(n)$ is the number of 1's in the binary expansion of $n$. See https://oeis.org/A000670 for further information on ordered set partitions.

Improve this question
$\endgroup$
13
  • 5
    $\begingroup$ The paper "Cyclotomic factors of the descent set polynomial" by Denis Chebikin, Richard Ehrenborg, Pavlo Pylyavskyy, and Margaret Readdy, J. Combin. Theory Ser. A. 116 (2009), 247–264, sciencedirect.com/science/article/pii/S0097316508000897 may be relevant. They consider the number of odd values of $\beta_n(S)$. $\endgroup$
    – Ira Gessel
    Commented Apr 5, 2022 at 21:05
  • 1
    $\begingroup$ Thanks for this reference (which at one time I was aware of). According to their results, it suffices to find $f(n)$ for $n=2^k-1$. $\endgroup$
    – Richard Stanley
    Commented Apr 5, 2022 at 23:14
  • 1
    $\begingroup$ I can confirm 7424. $\endgroup$
    – Mikhail Tikhomirov
    Commented Apr 6, 2022 at 17:13
  • 1
    $\begingroup$ I confirm $f(31) = 2^{17} \cdot 3 \cdot 307$ with the breakdown by size of $S$ having g.f. $q^{30} + 285q^{28} + 1980q^{27} + 14215q^{26} + 71760q^{25} + 291715q^{24} + 971640q^{23} + 2742385q^{22} + 6685520q^{21} + 14204349q^{20} + 26215940q^{19} + 42026655q^{18} + 58640480q^{17} + 71505675q^{16} + 76363152q^{15} + 71505675q^{14} + 58640480q^{13} + 42026655q^{12} + 26215940q^{11} + 14204349q^{10} + 6685520q^{9} + 2742385q^{8} + 971640q^{7} + 291715q^{6} + 71760q^{5} + 14215q^{4} + 1980q^{3} + 285q^{2} + 1$. Code and more data. $\endgroup$
    – Peter Taylor
    Commented Apr 6, 2022 at 21:38
  • 2
    $\begingroup$ I get $f(63) = 2^{36} \cdot 11 \cdot 1031 \cdot 2939$, thus the ratio $f(n) / 2^{n - 1}$ for any number with Hamming weight $6$ is $11 \cdot 1031 \cdot 2939 / 2^{26} \sim 0.49734$. $\endgroup$
    – Mikhail Tikhomirov
    Commented Apr 6, 2022 at 21:49

0

Reset to default

You must log in to answer this question.