Let d and n be positive integers such that d divides n. An endofunction is a function whose domain is equal to its codomain. Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$[n]=\{1,2,\ldots ,n\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> and T be an endofunction on [n]. A subset W of [n] of cardinality n/d is d-splitting if <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$W \cup TW \cup \cdots \cup T^{d-1}W =[n]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>W</mi> <mo>∪</mo> <mi>T</mi> <mi>W</mi> <mo>∪</mo> <mo>⋯</mo> <mo>∪</mo> <msup> <mi>T</mi> <mrow> <mi>d</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mi>W</mi> <mo>=</mo> <mrow> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. Let <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\sigma (d;T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>σ</mi> <mo stretchy="false">(</mo> <mi>d</mi> <mo>;</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> denote the number of d-splitting subsets for an endofunction T. If <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\sigma (2;T)>0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>σ</mi> <mo stretchy="false">(</mo> <mn>2</mn> <mo>;</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, then we show that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\sigma (2;T)=g_T(-1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>σ</mi> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mo>;</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mi>g</mi> <mi>T</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$g_T(t)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>g</mi> <mi>T</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the generating function for the number of T-invariant subsets of [n]. More generally, let <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$g_T(t_1,\ldots ,t_d)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>g</mi> <mi>T</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>t</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>t</mi> <mi>d</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> be the generating function for the number of d-flags of T-invariant subsets. We prove that if T is an endofunction whose graph is either a cycle, a tree, or a certain composition of cycles and trees such that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\sigma (d;T)>0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>σ</mi> <mo stretchy="false">(</mo> <mi>d</mi> <mo>;</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, then <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\sigma (d;T)=g_T(\zeta ,\zeta ^2,\ldots ,\zeta ^d)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>σ</mi> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mo>;</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mi>g</mi> <mi>T</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ζ</mi> <mo>,</mo> <msup> <mi>ζ</mi> <mn>2</mn> </msup> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msup> <mi>ζ</mi> <mi>d</mi> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\zeta $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ζ</mi> </math></EquationSource> </InlineEquation> is a primitive <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$d^{th}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>d</mi> <mrow> <mi mathvariant="italic">th</mi> </mrow> </msup> </math></EquationSource> </InlineEquation> root of unity.

Enumeration of splitting subsets of endofunctions on finite sets

期刊论文
发表日期：

2025年10月25日

查看全文

Divya Aggarwal

摘要

Let d and n be positive integers such that d divides n. An endofunction is a function whose domain is equal to its codomain. Let $[n]=\{1,2,\ldots ,n\}$ $[n] = {1, 2, \dots, n}$ and T be an endofunction on [n]. A subset W of [n] of cardinality n/d is d-splitting if $W \cup TW \cup \cdots \cup T^{d-1}W =[n]$ $W \cup T W \cup \dots \cup T^{d - 1} W = [n]$ . Let $\sigma (d;T)$ $σ (d; T)$ denote the number of d-splitting subsets for an endofunction T. If $\sigma (2;T)>0$ $σ (2; T) > 0$ , then we show that $\sigma (2;T)=g_T(-1)$ $σ (2; T) = g_{T} (- 1)$ , where $g_T(t)$ $g_{T} (t)$ is the generating function for the number of T-invariant subsets of [n]. More generally, let $g_T(t_1,\ldots ,t_d)$ $g_{T} (t_{1}, \dots, t_{d})$ be the generating function for the number of d-flags of T-invariant subsets. We prove that if T is an endofunction whose graph is either a cycle, a tree, or a certain composition of cycles and trees such that $\sigma (d;T)>0$ $σ (d; T) > 0$ , then $\sigma (d;T)=g_T(\zeta ,\zeta ^2,\ldots ,\zeta ^d)$ $σ (d; T) = g_{T} (ζ, ζ^{2}, \dots, ζ^{d})$ , where $\zeta $ $ζ$ is a primitive $d^{th}$ $d^{th}$ root of unity.