<p>Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(S_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> denote the symmetric group of order <i>n</i>. Say that two subsets <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(x, y\subseteq S_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>⊆</mo> <msub> <mi>S</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> are <i>equivalent</i> if there exist permutations <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(g_1, g_2\in S_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>g</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>g</mi> <mn>2</mn> </msub> <mo>∈</mo> <msub> <mi>S</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(g_1xg_2=y\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>g</mi> <mn>1</mn> </msub> <mi>x</mi> <msub> <mi>g</mi> <mn>2</mn> </msub> <mo>=</mo> <mi>y</mi> </mrow> </math></EquationSource> </InlineEquation>, where multiplication is understood elementwise. Recently, [Tripathi, 2024] and [Kushwaha and Tripathi, 2025] asked for the asymptotics of <i>T</i>(<i>n</i>,&#xa0;<i>k</i>), the number of subsets of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(S_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> of size <i>k</i> up to this equivalence. It is easy to see that <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(T(n,0)=T(n, 1)=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>T</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(T(n, 2)=p(n)-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>2</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>p</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, where <i>p</i>(<i>n</i>) is the number of integer partitions of <i>n</i>. In this work, we show that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(T(n,k) = \Lambda _n(k)(1+o_n(1))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mi mathvariant="normal">Λ</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <msub> <mi>o</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(3\le k\le n!-3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>3</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>n</mi> <mo>!</mo> <mo>-</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\Lambda _n(k)=\frac{1}{n!^2}\left( {\begin{array}{c}n!\\ k\end{array}}\right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="normal">Λ</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mfrac> <mn>1</mn> <mrow> <mi>n</mi> <msup> <mo>!</mo> <mn>2</mn> </msup> </mrow> </mfrac> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mi>n</mi> <mo>!</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mi>k</mi> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. Furthermore, we prove that <Equation ID="Equ11"> <EquationSource Format="TEX">\( \frac{1}{\Lambda _n(n!/2)}T\!\left( n,\left[ \sqrt{\tfrac{n!}{4}}x+\tfrac{n!}{2}\right] \right) ~\xrightarrow {n\rightarrow \infty }~ \exp \!\left( -\tfrac{x^2}{2}\right) \,, \)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mfrac> <mn>1</mn> <mrow> <msub> <mi mathvariant="normal">Λ</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>!</mo> <mo stretchy="false">/</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </mfrac> <mi>T</mi> <mspace width="-0.166667em" /> <mfenced close=")" open="("> <mi>n</mi> <mo>,</mo> <mfenced close="]" open="["> <msqrt> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mn>4</mn> </mfrac> </mstyle> </msqrt> <mi>x</mi> <mo>+</mo> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mn>2</mn> </mfrac> </mstyle> </mfenced> </mfenced> <mspace width="3.33333pt" /> <mover> <mo stretchy="false">→</mo> <mrow> <mi>n</mi> <mo stretchy="false">→</mo> <mi>∞</mi> </mrow> </mover> <mspace width="3.33333pt" /> <mo>exp</mo> <mspace width="-0.166667em" /> <mfenced close=")" open="("> <mo>-</mo> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <msup> <mi>x</mi> <mn>2</mn> </msup> <mn>2</mn> </mfrac> </mstyle> </mfenced> <mspace width="0.166667em" /> <mo>,</mo> </mrow> </math></EquationSource> </Equation>uniformly over <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\mathbb {R}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">R</mi> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Number of orbits of k-subsets of permutations

  • Ludovick Bouthat,
  • Raghavendra Tripathi

摘要

Let \(S_{n}\) S n denote the symmetric group of order n. Say that two subsets \(x, y\subseteq S_{n}\) x , y S n are equivalent if there exist permutations \(g_1, g_2\in S_{n}\) g 1 , g 2 S n such that \(g_1xg_2=y\) g 1 x g 2 = y , where multiplication is understood elementwise. Recently, [Tripathi, 2024] and [Kushwaha and Tripathi, 2025] asked for the asymptotics of T(nk), the number of subsets of \(S_{n}\) S n of size k up to this equivalence. It is easy to see that \(T(n,0)=T(n, 1)=1\) T ( n , 0 ) = T ( n , 1 ) = 1 and \(T(n, 2)=p(n)-1\) T ( n , 2 ) = p ( n ) - 1 , where p(n) is the number of integer partitions of n. In this work, we show that \(T(n,k) = \Lambda _n(k)(1+o_n(1))\) T ( n , k ) = Λ n ( k ) ( 1 + o n ( 1 ) ) for \(3\le k\le n!-3\) 3 k n ! - 3 , where \(\Lambda _n(k)=\frac{1}{n!^2}\left( {\begin{array}{c}n!\\ k\end{array}}\right) \) Λ n ( k ) = 1 n ! 2 n ! k . Furthermore, we prove that \( \frac{1}{\Lambda _n(n!/2)}T\!\left( n,\left[ \sqrt{\tfrac{n!}{4}}x+\tfrac{n!}{2}\right] \right) ~\xrightarrow {n\rightarrow \infty }~ \exp \!\left( -\tfrac{x^2}{2}\right) \,, \) 1 Λ n ( n ! / 2 ) T n , n ! 4 x + n ! 2 n exp - x 2 2 , uniformly over \(\mathbb {R}\) R .