Exercise 2.11 - The-Art-of-Counting-2025/Exercise GitHub Wiki

Statement

$S\cup T=\emptyset$ ใจใ—ใฆใ€้ †ๅˆ— $\pi\in P(S)$ ใจ $\sigma \in P(T)$ ใ‚’่€ƒใˆใ‚‹ใ€‚ $\pi$ ใจ $\sigma$ ใฎ shuffle (ๅค‰ใช่จ˜ๅทใฎใ‚„ใค) ใ‚’ๆฌกใงๅฎš็พฉ๏ผš

$\pi\ {\tiny\text{shuffle}}\ \sigma=\lbrace \tau\in P(S\uplus T)\mid\pi \text{ and }\sigma\text{ ใฏ }\tau\text{ ใฎ้ƒจๅˆ†ๅˆ— }\rbrace$

ไพ‹ใˆใฐใ€ $31{\tiny\text{shuffle}}24=\lbrace 3124,3214,3241,2314,2341,2431\rbrace$ ใงใ‚ใ‚‹ใ€‚

้ †ๅˆ—ใฎ็ทšๅฝข็ตๅˆใ‚’ใ€ใใ‚Œใ‚‰ใŒใƒ™ใ‚ฏใƒˆใƒซใงใ‚ใ‚‹ใฎใจๅŒๆง˜ใซใ—ใฆใจใ‚‹ใ€‚ไพ‹ใˆใฐ

$6(3124)-7(3241)-9(3124)+(3241)=-3(3124)-6(3241)$

ใใ—ใฆใ€้ †ๅˆ—ใฎ้›†ๅˆใฏใ€ใใฎ่ฆ็ด ใฎไฟ‚ๆ•ฐใ‚’ใ™ในใฆ $1$ ใจใ—ใฆ็ทๅ’Œใ‚’ใจใฃใŸใ‚‚ใฎใ‚’่กจใ™ใ€‚ใ™ใ‚‹ใจใ€ๆฌกใฎใ‚ˆใ†ใซๆ›ธใ๏ผš

$31\ {\tiny\text{shuffle}}\ 24=3124+3214+3241+2314+2341+2431$

ใใ—ใฆใ“ใฎใจใใ€ $31\ {\tiny\text{shuffle}}\ 24$ ใŒ้›†ๅˆใ‚’่กจใ™ใ‹ๅ’Œใ‚’่กจใ™ใฎใ‹ใฏใ€ๆ–‡่„ˆใงๅŒบๅˆฅใ™ใ‚‹ใจใ™ใ‚‹ใ€‚

ๆฌกๅผใ‚’่จผๆ˜Žใ›ใ‚ˆ๏ผš

image

ใ“ใ“ใงใ€็ทๅ’Œใฏ $w _ 1\cdot w _ 2\cdot\ldots\cdot w _ k =12\ldots n$ ใชใ‚‹้€ฃ็ตๅ…จไฝ“ใ‚’ใ‚ใŸใ‚‹ใ‚‚ใฎใจใ™ใ‚‹ใ€‚ไพ‹ใˆใฐใ€ $n=3$ ใฎใจใใ€้€ฃ็ตๅ…จไฝ“ใฏ $123=1\cdot 2\cdot 3=1\cdot 23=12\cdot 3=123$ ใงใ‚ใ‚‹ใ€‚

Hint : $w _ 1\ {\tiny\text{shuffle}}\ \cdots \ {\tiny\text{shuffle}}\ w _ k$ ใซๅซใพใ‚Œใ‚‹้ †ๅˆ— $v$ ใ‚’่€ƒใˆใ€ๆฌกใฎ (i) (ii) ใ‚’ๆบ€ใŸใ™ๆœ€ๅคงใฎ $j\geq 0$ ใ‚’ใจใ‚‹ใ€‚

(i) $|w _ 1|=|w _ 2|=\ldots =|w _ j|=1$ (ใ“ใฎใจใ $w _ i=i$ ใงใ‚ใ‚‹)

(ii) $j\ldots 21$ ใฏ $v$ ใฎ้ƒจๅˆ†ๅˆ—ใงใ‚ใ‚‹ใ€‚

$v$ ๅ†…ใซใŠใ‘ใ‚‹ $j$ ใจ $j+1$ ใฎไฝ็ฝฎ้–ขไฟ‚ใ‚’ไฝฟใฃใฆใ€ merge/split ใ‚’่กŒใ„ใ€็•ฐใชใ‚‹็ฌฆๅทใ‚’ใ‚‚ใค shuffle ใจใ—ใฆๅ†ๅบฆ $v$ ใŒ็พใ‚Œใ‚‹ๅ ดๅˆใ‚’่ฆ‹ใคใ‘ใ‚ˆใ€‚

Solution (Hint ใฎ้€šใ‚Šใซใ‚„ใ‚‹)

้ †ๅˆ— $v\neq n\ldots 21$ ใ‚’ๅ›บๅฎšใ™ใ‚‹ใ€‚

้€ฃ็ต $w _ 1\cdot w _ 2\cdot\ldots\cdot w _ k$ ใงใ‚ใฃใฆ $v\in w _ 1\ {\tiny\text{shuffle}}\ \ldots\ {\tiny\text{shuffle}}\ w _ k$ ใชใ‚‹ใ‚‚ใฎๅ…จไฝ“ใ‚’ๅฎš็พฉๅŸŸใŠใ‚ˆใณๅ€คๅŸŸ $D$ ใจใ™ใ‚‹ๅ†™ๅƒ $f:D\mapsto D$ ใ‚’ๅฎš็พฉใ™ใ‚‹ใ€‚

$d=(w _ i,\ldots ,w _ k)\in D$ ใซใคใ„ใฆใ€ ใพใš Hint ใฎ้€šใ‚Šใซ $j$ ใ‚’ใจใ‚‹ใ€‚ใ“ใฎใจใ $f(d)$ ใ‚’ๆฌกใฎๆ‰‹้ †ใงๆฑบใ‚ใ‚‹ใ€‚

  • (case Split) $j=0$ ใพใŸใฏ $j+1$ ใŒ $j$ ใ‚ˆใ‚Šใ‚‚ๅ‰ใซ็พใ‚Œใ‚‹ใชใ‚‰ใฐใ€ $|w _ {j+1}|\geq 2$ ใงใ‚ใ‚‹๏ผˆใชใœใชใ‚‰ใ€ (ii) ใฏ $j+1$ ใซใคใ„ใฆๆบ€ใŸใ•ใ‚Œใฆใ„ใ‚‹๏ผ‰ใ€‚ $w _ {j+1}$ ใ‹ใ‚‰ $j+1$ ใ‚’ๅˆ‡ใ‚Š้›ขใ—ใฆๅพ—ใ‚‰ใ‚Œใ‚‹้•ทใ• $k+1$ ใฎ้€ฃ็ตใ‚’ $f(d)$ ใจใ™ใ‚‹ใ€‚

  • (case Merge) $j+1$ ใŒ $j$ ใ‚ˆใ‚Šใ‚‚ๅพŒใซ็พใ‚Œใ‚‹ใชใ‚‰ใฐใ€ใ€€$w _ j$ ใจ $w _ {j+1}$ ใ‚’้€ฃ็ตใ—ใฆๅพ—ใ‚‰ใ‚Œใ‚‹้•ทใ• $k-1$ ใฎ้€ฃ็ตใ‚’ $f(d)$ ใจใ™ใ‚‹ใ€‚

$d$ ใจ $f(d)$ ใฏใ€ $k$ ใฎๅถๅฅ‡ใŒ็•ฐใชใ‚‹ใ‹ใ‚‰ใ€ $f$ ใฏ sign-alternating ใ€‚

$f$ ใŒ involution ใงใ‚ใ‚‹ใ“ใจใ‚’็คบใ™ใ€‚

  • $j=1$ ใ‹ใค case Merge ใฎๅพŒใ€ $f(d)$ ใซใŠใ„ใฆ $j=0$ ใจใชใ‚‹ใ€‚ ($|w _ 1| \geq 2$)
  • $j\geq 2$ ใ‹ใค case Merge ใฎๅพŒใ€ $f(d)$ ใซใŠใ„ใฆ $j+1$ ใฏ $j$ ใ‚ˆใ‚Šใ‚‚ๅ‰ใซ็พใ‚ใ‚Œใ€ case Split ใฎๆกไปถใ‚’ๆบ€ใŸใ™ใ€‚ใชใœใชใ‚‰ใ€ $f(d)$ ใซใŠใ„ใฆ $(j+1)j\ldots 21$ ใŒ้ƒจๅˆ†ๅˆ—ใงใ‚ใ‚‹ใ‹ใ‚‰ใ€‚
  • case Split ใฎๅพŒใ€ $f(d)$ ใซใŠใ„ใฆ $j+1$ ใฏ $j$ ใฎๅพŒใซ็พใ‚Œใ‚‹ใ€‚ใชใœใชใ‚‰ใ€ $j$ ใฏ $1$ ใ ใ‘ๅข—ๅŠ ใ™ใ‚‹ใ€‚

ใ‚ˆใฃใฆใ€ $f(f(d))$ ใจใ—ใŸใจใ็‰‡ๆ–นใฎ $f$ ใฏ case Split ใงใ‚ใฃใฆใ‚‚ใ†ไธ€ๆ–นใฏ case Merge ใงใ‚ใ‚Šใ€ใ‚ˆใฃใฆ $f(f(d))=d$ ใ€‚

ใคใพใ‚Š $f$ ใฏ sign-alternating involution ใงใ‚ใ‚‹ใ€‚ sign-alternating involution ใฎๅญ˜ๅœจใซใ‚ˆใ‚Šใ€ไธŽๅผใซใŠใ„ใฆ $v\neq n\ldots 21$ ใชใ‚‹ $v$ ใฎไฟ‚ๆ•ฐใฏ $0$ ใงใ‚ใ‚‹ใ€‚

ๆœ€ๅพŒใซใ€ $(n\ldots 21)$ ใŒ shuffle ใง็”Ÿๆˆใ•ใ‚Œใ‚‹ใซใฏใ€ใ™ในใฆใฎ $i$ ใง $|w _ i|=1$ ใงใชใ‘ใ‚Œใฐใชใ‚‰ใšใ€ๅพ“ใฃใฆไฟ‚ๆ•ฐใฏ $(-1)^n$ ใงใ‚ใ‚‹ใ€‚

Solution (j ใฎๅ–ใ‚Šๆ–นใ‚’ๅค‰ใˆใ‚‹)

้ †ๅˆ— $v\neq n\ldots 21$ ใ‚’ๅ›บๅฎšใ™ใ‚‹ใ€‚

้€ฃ็ต $w _ 1\cdot w _ 2\cdot\ldots\cdot w _ k$ ใงใ‚ใฃใฆ $v\in w _ 1\ {\tiny\text{shuffle}}\ \ldots\ {\tiny\text{shuffle}}\ w _ k$ ใชใ‚‹ใ‚‚ใฎๅ…จไฝ“ใ‚’ๅฎš็พฉๅŸŸใŠใ‚ˆใณๅ€คๅŸŸ $D$ ใจใ™ใ‚‹ๅ†™ๅƒ $f:D\mapsto D$ ใ‚’ๅฎš็พฉใ™ใ‚‹ใ€‚

$v$ ใซๅฏพใ—ใฆใ€ $j\ldots 21$ ใŒ $v$ ใฎ้ƒจๅˆ†ๅˆ—ใงใ‚ใ‚‹ใ‚ˆใ†ใชๆœ€ๅคงใฎ $j$ ใ‚’ใจใ‚‹ใ€‚ $|w _ 1|=\ldots =|w _ {j-1}| = 1$ ใงใ‚ใ‚‹ใ€‚ $d=(w _ i,\ldots ,w _ k)\in D$ ใซใคใ„ใฆใ€ $f(d)$ ใ‚’ๆฌกใฎๆ‰‹้ †ใงๆฑบใ‚ใ‚‹ใ€‚

  • (case Split) $|w _ j|\geq 2$ ใงใ‚ใ‚‹ใจใใ€ $w _ j$ ใ‹ใ‚‰ $j$ ใ‚’ๅˆ‡ใ‚Š้›ขใ—ใฆๅพ—ใ‚‰ใ‚Œใ‚‹้•ทใ• $k+1$ ใฎ้€ฃ็ตใ‚’ $f(d)$ ใจใ™ใ‚‹ใ€‚ $f(d)$ ใซใŠใ„ใฆใ€ $|w _ j|=1$ ใงใ‚ใ‚‹ใ€‚

  • (case Merge) $|w _ j|=1$ ใงใ‚ใ‚‹ใจใใ€ $w _ j$ ใจ $w _ {j+1}$ ใ‚’้€ฃ็ตใ—ใฆๅพ—ใ‚‰ใ‚Œใ‚‹้•ทใ• $k-1$ ใฎ้€ฃ็ตใ‚’ $f(d)$ ใจใ™ใ‚‹ใ€‚ $f(d)$ ใซใŠใ„ใฆใ€ $|w _ j|\geq 2$ ใงใ‚ใ‚‹ใ€‚

$d$ ใจ $f(d)$ ใฏใ€ $k$ ใฎๅถๅฅ‡ใŒ็•ฐใชใ‚‹ใ‹ใ‚‰ใ€ $f$ ใฏ sign-alternating ใ€‚ไปฅไธŠใซใ‚ˆใฃใฆใ€ $f$ ใŒ involution ใงใ‚ใ‚‹ใ“ใจใ‚‚ๆ˜Žใ‚‰ใ‹ใ€‚ใคใพใ‚Š $f$ ใฏ sign-alternating involution ใงใ‚ใ‚‹ใ€‚

sign-alternating involution ใŒๆง‹ๆˆใ•ใ‚ŒใŸใฎใงใ€ไธŽๅผใซใŠใ„ใฆ $v\neq n\ldots 21$ ใชใ‚‹ $v$ ใฎไฟ‚ๆ•ฐใฏ $0$ ใงใ‚ใ‚‹ใ€‚

ๆœ€ๅพŒใซใ€ $(n\ldots 21)$ ใŒ shuffle ใง็”Ÿๆˆใ•ใ‚Œใ‚‹ใซใฏใ€ใ™ในใฆใฎ $i$ ใง $|w _ i|=1$ ใงใชใ‘ใ‚Œใฐใชใ‚‰ใšใ€ๅพ“ใฃใฆไฟ‚ๆ•ฐใฏ $(-1)^n$ ใงใ‚ใ‚‹ใ€‚

image

by Nachia (thanks to leaf1415)