Basic Principles

Multiplication Principle

• If an activity can be constructed in $t$ successive steps and
  • step 1 can be done in $n_1$ ways,
  • step 2 can be done in $n_2$ ways,
  • $\dotso$
  • step $t$ can be done in $n_t$ ways,
• then the number of different possible activities is $n_1\cdot n_2\cdot \dotso \cdot n_t$

Sometimes, Multiplication Principle, followed by “subtraction” x ทั้งหมด ลบ ตรงข้าม?

• อาจจะมีถามเรื่อง Subset 03 Sets, Relations, and Functions

Addition Principle

• Used when the arrangements under consideration can be divided into “disjoint cases”.
• หากการทำงานให้เสร็จมีหลายแบบ ให้แยกคิดแต่ละวิธีด้วยการคูณ (ทำงานให้เสร็จซะก่อน)
  แล้วจึงนำมาบวก กัน เป็นวิธีทั้งหมดที่ทำได้
  • The number of all arrangement: $n_1+n_2+\dotso+n_t$

ระวังโจทย์ที่เป็นมันสามารถมีบางตัวซ้ำกันได้ อย่าลืมลบออกด้วย อย่านับซ้ำ!

• เหมือนโจทย์ปัญหา จำนวนสมาชิกใน Set แบบนั้นเลย!

Permutation and Combination

Permutation

• Definition: A permutation of $n$ distinct elements $x_1,x_2,\dotso,x_n$ is an ordering of the $n$ elements $x_1,x_2,\dotso,x_n$

Linear

Theorem: There are $n!$ permutations of $n$ elements.

• จริง ๆ นิยามของ $n!$ ก็มาจาก กฎการคูณนั่นแหละ!

Circular

• “Fixed ไว้ 1 จุด” แล้วที่เหลือคิดเหมือนเส้นตรง
• 2D
  • ถ้ามีของแตกต่างกัน $n$ สิ่ง นำมาจัดเรียงสับเปลี่ยนแบบวงกลม ได้ $(n-1)!$

  In general: There are $(n-1)!$ ways that $n$ persons can be seated around a circular table.

$r$-Permutation

(ไม่ได้ใช้บ่อยขนาดนั้น)

• การหาจำนวนวิธีเรียงสับเปลี่ยนของ $n$ สิ่ง (แตกต่างกันทั้งหมด) โดยการนำมาจัดครั้งละ $r$ สิ่ง
• ลำดับมีความสำคัญ
• $C(n,r)\cdot r!=P(n,r)$ เลือกมาก่อนแล้วจัดเรียงสลับ ๆ

$r$-Combination

• เลือก
• ลำดับไม่มีความสำคัญ

Generalized Permutations and Combinations

• In this section we consider
  • Orderings of sequences containing repetitions
  • Unordered selections in which repetitions are allowed

Generalized Permutation

• Suppose that a sequence $S$ of $n$ items has $n_1$ identical objects of type 1, $n_2$ identical objects of type 2, $\dotso$ , and $n_t$ identical objects of type $t$. Then the number of orderings of $S$ is
  • เจอของซ้ำ
  $$\boxed{\frac{n!}{n_1!\cdot n_2!\dotso n_{t}!}}$$

Generalized Combination

Stars and Bars

Distribute identical objects among a number of different recipients

• เวลาที่จะ Solve คำถามแนว $x_1+x_2+x_3=15$ แบบนี้นะ
  • กรณีไม่มี Constraint อะไร
    • ให้ใช้ Stars & Bars ปกติ
  • แต่ถ้ามี Constraint แค่ช่วงล่าง เช่น
    • Constraint $>,\ge 0$ มีความหมายเหมือนกัน (แต่ถ้าเลขอื่นต้องระวังนะ)
    • หากมี Constraint เช่น
      • Constraint $x_1\ge1$ให้เปลี่ยนสมการให้ดูง่ายกว่าเดิม $y_1=x_1-1$ แบบนี้
      • Constraint $x_1>1$ ถ้าเป็นแบบนี้เปลี่ยนเป็น $y_1=x_1-2$
  • ถ้ามี Constraint ช่วงบนด้วย
    • จัดการ ช่วงล่าง ให้เรียบร้อยก่อน แล้วค่อยหาคำตอบสมการ— แล้วค่อยเอามาลบกับช่วงที่มีช่วงบนร่วมอยู่ด้วย
    • การจะเปลี่ยนสมการช่วงบนจะดูยากนิดนึงนะ แต่มองได้แน่นอน $3\le x_2 \le 6$
      • ถ้าเป็นแบบนี้ก็ต้องเอาช่วงบนเป็น $z_2=y_2-4$ ก็คือเราไม่เอา 7 ขึ้นไปถูกมั้ย (มองให้ออก ไม่รู้จะเขียนไง555)

วิธีนี้เหมือนจะไม่ถูกต้อง 100% นะ! ทำตามวิธีครูจะแม่นกว่า!

Stars & Bars for Nested Loop

	\begin{algorithm}
	\caption{How many times is the statement $x := x + 1$ executed?}
	\begin{algorithmic}
	\For{$i := 1$ \to $5$}
		\For{$j := 1$ \to $i$}
			\State $x:= x+1$
		\EndFor
	\EndFor
	\end{algorithmic}
	\end{algorithm}	

• หลังกำแพงเวลาคิดก็จะได้ $C_{6,2}$ เลยไง! ก็ถือว่าเป็นคำตอบของข้อนี้โลดดด

	\begin{algorithm}
	\caption{How many times is the statement $x := x + 1$ executed?}
	\begin{algorithmic}
	\For{$i := 1$ \to $10$}
		\For{$j := 1$ \to $i$}
			\For{$k := 1$ \to $j$}
				\State $x:= x+1$
			\EndFor
		\EndFor
	\EndFor
	\end{algorithmic}
	\end{algorithm}	

• หลังกำแพงจะได้ $C_{12,3}$ ก็เป็นคำตอบของข้อนี้เลยทันที~~~

	\begin{algorithm}
	\caption{How many times is the statement $x := x + 1$ executed?}
	\begin{algorithmic}
	\For{$i := 3$ \to $10$}
		\For{$j := 3$ \to $i$}
			\For{$k := 3$ \to $j$}
				\State $x:= x+1$
			\EndFor
		\EndFor
	\EndFor
	\end{algorithmic}
	\end{algorithm}