Math 2421 Dr.

Dong XIA

What is probability?
Probability is simply how likely something is to happen.
Example If a coin is randomly flipped, how likely it lands on head or tail?

Why we should learn probability?

Nowadays, randomness becomes prevalent in real life.
e.g., the revenue of apple store at APM next month is random
e.g., the length a patient with cancer can survive is random

Probability is the fundamental tool for modelling, analyzing randomness

e.g., what is the most likely revenue of apple store at APM next month?
e.g., what is the most likely length a patient with cancer can survive?

Probability is the fundamental tool for statistics, machine learning, etc.

1
Math 2421

Chapter 1. Probability by Combinatorial Analysis

Outline

1.1 Introduction

1.2 Principle of Counting

1.3 Permutations

1.4 Combinations

1.5 Multinomial Coefficients

1.6 Number of Integer Solutions

2 Chapter 1: Combinatorial Analysis

Math 2421

1.1 Introduction

Simple intuitive examples to understand probability

Example If we randomly pick up a ball in the following box, what is the chance
of selecting a red ball?
1 2 3 we can view this chance as probability.

4 5 6
7 8 9

Solution We see there are 9 balls in the box and 4 of them are red.
Intuitively, we know the chance of selecting a red ball is 4/9.

4 4 outcomes are red balls {3,4,7,9}

=
<latexit sha1_base64="lmDa7wYI/BONiLADzTtWDkD32zM=">AAAB83icbZDLSsNAFIZP6q3WW9Wlm8EiuCpJLdQuhKIblxXsBZpQJtNJO3QyCTMToYS8hhsXirj1Zdz5Nk7b4P2HgZ//nMM58/kxZ0rb9rtVWFldW98obpa2tnd298r7B10VJZLQDol4JPs+VpQzQTuaaU77saQ49Dnt+dOreb13R6VikbjVs5h6IR4LFjCCtYlcN5CYpPUsbWYXw3LFrtoLob/GyU0FcrWH5Td3FJEkpEITjpUaOHasvRRLzQinWclNFI0xmeIxHRgrcEiVly5uztCJSUYoiKR5QqNF+n0ixaFSs9A3nSHWE/W7Ng//qw0SHZx7KRNxoqkgy0VBwpGO0BwAGjFJieYzYzCRzNyKyAQbDNpgKhkIztffm0aNem6azieEbq3qnFVrN/VK6zLHUYQjOIZTcKABLbiGNnSAQAz38AhPVmI9WM/Wy7K1YOUzh/BD1usH9PyR4w==</latexit>
9 9 possible outcomes {1,2,3,4,5,6,7,8,9}

3 Chapter 1: Combinatorial Analysis

Math 2421

1.1 Introduction

Class Discussion

If we randomly pick up 2 balls in the following box, what is the chance that the
2 selected balls are both red?

1 2 3
4 5

Choose your answer?

Choice A Choice B Choice C

1 1 1
<latexit sha1_base64="bzJUOLXg1bH1zbuyroI4eNWy3aE=">AAAB8nicbVBNSwMxEM3Wr1q/qh69BIvgqezWQu2t6MVjBVsL7VKyabYNzSZLMiuUZX+GFw+KePXXePPfmLaL3w8GHu/NMDMviAU34LrvTmFldW19o7hZ2tre2d0r7x90jUo0ZR2qhNK9gBgmuGQd4CBYL9aMRIFgt8H0cu7f3jFtuJI3MIuZH5Gx5CGnBKzUH4Sa0NTL0no2LFfcqrsA/ku8nFRQjvaw/DYYKZpETAIVxJi+58bgp0QDp4JlpUFiWEzolIxZ31JJImb8dHFyhk+sMsKh0rYk4IX6fSIlkTGzKLCdEYGJ+e3Nxf+8fgLhuZ9yGSfAJF0uChOBQeH5/3jENaMgZpYQqrm9FdMJsSmATalkQ/C+fm9aNOo5aXqfIXRrVe+sWruuV1oXeRxFdISO0SnyUAO10BVqow6iSKF79IieHHAenGfnZdlacPKZQ/QDzusHYwqRlA==</latexit>
4 <latexit sha1_base64="KSgvpOIznhqJS0eCT1F9i7H8g6Q=">AAAB8nicbVDLSsNAFJ3UV62vqks3g0VwVZJaqd0V3bisYB+QhjKZTtqhk0mYuRFKyGe4caGIW7/GnX/jtA2+D1w4nHMv997jx4JrsO13q7Cyura+UdwsbW3v7O6V9w+6OkoUZR0aiUj1faKZ4JJ1gINg/VgxEvqC9fzp1dzv3TGleSRvYRYzLyRjyQNOCRjJHQSK0NTJ0vNsWK7YVXsB/Jc4OamgHO1h+W0wimgSMglUEK1dx47BS4kCTgXLSoNEs5jQKRkz11BJQqa9dHFyhk+MMsJBpExJwAv1+0RKQq1noW86QwIT/dubi/95bgLBhZdyGSfAJF0uChKBIcLz//GIK0ZBzAwhVHFzK6YTYlIAk1LJhOB8/d40aNRz0nQ+Q+jWqs5ZtXZTr7Qu8ziK6Agdo1PkoAZqoWvURh1EUYTu0SN6ssB6sJ6tl2VrwcpnDtEPWK8fZI+RlQ==</latexit>
5 <latexit sha1_base64="IZlZ2gU5br3Z5zSn7p1DRI5/FmU=">AAAB83icbZDLSsNAFIYn9VbrrerSzWARXJVM6y27ohuXFewFmlAm00k7dDIJMxOhhLyGGxeKuPVl3Pk2TtpQvP0w8POdczhnfj/mTGnb/rRKK6tr6xvlzcrW9s7uXnX/oKuiRBLaIRGPZN/HinImaEczzWk/lhSHPqc9f3qT13sPVCoWiXs9i6kX4rFgASNYG+S6gcQkRVmK7GxYrdl1ey7416DC1ECh9rD64Y4ikoRUaMKxUgNkx9pLsdSMcJpV3ETRGJMpHtOBsQKHVHnp/OYMnhgygkEkzRMazun3iRSHSs1C33SGWE/U71oO/6sNEh1ceSkTcaKpIItFQcKhjmAeABwxSYnmM2MwkczcCskEmxi0iakyD8FxHNQ4X34Z5gQ1nYsl6TbqqFlv3J3VWtdFHGVwBI7BKUDgErTALWiDDiAgBo/gGbxYifVkvVpvi9aSVcwcgh+y3r8AyLORtg==</latexit>
10

4 Chapter 1: Combinatorial Analysis

Math 2421

1.1 Introduction

Example

Signal is receivable

Signal is not receivable

5 Chapter 1: Combinatorial Analysis

Math 2421

1.1 Introduction

Example

Solution

6 Chapter 1: Combinatorial Analysis

Math 2421

1.1 Introduction

Continue from last page…

Probability that system works =

<latexit sha1_base64="N7k6VVOy91wQ/2jomskjf9Iv/C0=">AAAB6HicbVDJSgNBEK2JW4xb1KOXxiB4CjMxEHMQgl48JmAWSIbQ06lJ2vQsdPcIIeQLvHhQxKuf5M2/sZMM7g8KHu9VUVXPiwVX2rbfrczK6tr6RnYzt7W9s7uX3z9oqSiRDJssEpHseFSh4CE2NdcCO7FEGngC2974au6371AqHoU3ehKjG9BhyH3OqDZS46KfL9hFewHylzgpKUCKej//1htELAkw1ExQpbqOHWt3SqXmTOAs10sUxpSN6RC7hoY0QOVOF4fOyIlRBsSPpKlQk4X6fWJKA6UmgWc6A6pH6rc3F//zuon2z90pD+NEY8iWi/xEEB2R+ddkwCUyLSaGUCa5uZWwEZWUaZNNzoTgfP1eNaiUU1J1PkNolYrOWbHUKBdql2kcWTiCYzgFBypQg2uoQxMYINzDIzxZt9aD9Wy9LFszVjpzCD9gvX4As42NIA==</latexit>

Why counting matters

7 Chapter 1: Combinatorial Analysis

Math 2421

1.2 Principle of Counting

Concepts

Experiment
We use the concept “experiment” to denote a process whose outcome is random

Example of experiment
e.g. randomly pick a number from {10,100,1000,10000}

e.g. randomly toss a coin

e.g. randomly roll a die

8 Chapter 1: Combinatorial Analysis

Math 2421

1.2 Principle of Counting

Theorem

Experiment 1 Experiment 2
1 2 3 1 2 3
4 5 6 4 5 6
7 8 9 7 8 9
···
<latexit sha1_base64="Ah+91sEoo3ktFGxhbeguRI68HOQ=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKezGQMwt6MVjBPOAZAmzs7PJmNmZZaZXCCH/4MWDIl79H2/+jZNk8V3QUFR1090VJIIbcN13J7eyura+kd8sbG3v7O4V9w/aRqWashZVQuluQAwTXLIWcBCsm2hG4kCwTjC+nPudO6YNV/IGJgnzYzKUPOKUgJXafRoqMINiyS27C+C/xMtICWVoDopv/VDRNGYSqCDG9Dw3AX9KNHAq2KzQTw1LCB2TIetZKknMjD9dXDvDJ1YJcaS0LQl4oX6fmJLYmEkc2M6YwMj89ubif14vhejcn3KZpMAkXS6KUoFB4fnrOOSaURATSwjV3N6K6YhoQsEGVLAheF+/1y1q1YzUvc8Q2pWyd1auXFdLjYssjjw6QsfoFHmohhroCjVRC1F0i+7RI3pylPPgPDsvy9ack80coh9wXj8A1RePjg==</latexit>

···
<latexit sha1_base64="Ah+91sEoo3ktFGxhbeguRI68HOQ=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKezGQMwt6MVjBPOAZAmzs7PJmNmZZaZXCCH/4MWDIl79H2/+jZNk8V3QUFR1090VJIIbcN13J7eyura+kd8sbG3v7O4V9w/aRqWashZVQuluQAwTXLIWcBCsm2hG4kCwTjC+nPudO6YNV/IGJgnzYzKUPOKUgJXafRoqMINiyS27C+C/xMtICWVoDopv/VDRNGYSqCDG9Dw3AX9KNHAq2KzQTw1LCB2TIetZKknMjD9dXDvDJ1YJcaS0LQl4oX6fmJLYmEkc2M6YwMj89ubif14vhejcn3KZpMAkXS6KUoFB4fnrOOSaURATSwjV3N6K6YhoQsEGVLAheF+/1y1q1YzUvc8Q2pWyd1auXFdLjYssjjw6QsfoFHmohhroCjVRC1F0i+7RI3pylPPgPDsvy9ack80coh9wXj8A1RePjg==</latexit>

m-2 m-1 m n-2 n-1 n

9 Chapter 1: Combinatorial Analysis

Math 2421

1.2 Principle of Counting

Theorem

Proof

10 Chapter 1: Combinatorial Analysis

Math 2421

1.2 Principle of Counting

Example

Solution

Example

11 Chapter 1: Combinatorial Analysis

Math 2421

1.2 Principle of Counting

Theorem

Example

12 Chapter 1: Combinatorial Analysis

Math 2421

1.2 Principle of Counting

Example

and

13 Chapter 1: Combinatorial Analysis

Math 2421

1.3 Permutations

Definition

Whole experiment Experiment 1 Experiment 2 Experiment 3

c c a c a b

a b c =
<latexit sha1_base64="N7k6VVOy91wQ/2jomskjf9Iv/C0=">AAAB6HicbVDJSgNBEK2JW4xb1KOXxiB4CjMxEHMQgl48JmAWSIbQ06lJ2vQsdPcIIeQLvHhQxKuf5M2/sZMM7g8KHu9VUVXPiwVX2rbfrczK6tr6RnYzt7W9s7uX3z9oqSiRDJssEpHseFSh4CE2NdcCO7FEGngC2974au6371AqHoU3ehKjG9BhyH3OqDZS46KfL9hFewHylzgpKUCKej//1htELAkw1ExQpbqOHWt3SqXmTOAs10sUxpSN6RC7hoY0QOVOF4fOyIlRBsSPpKlQk4X6fWJKA6UmgWc6A6pH6rc3F//zuon2z90pD+NEY8iWi/xEEB2R+ddkwCUyLSaGUCa5uZWwEZWUaZNNzoTgfP1eNaiUU1J1PkNolYrOWbHUKBdql2kcWTiCYzgFBypQg2uoQxMYINzDIzxZt9aD9Wy9LFszVjpzCD9gvX4As42NIA==</latexit>

a b +
<latexit sha1_base64="4+Z89fQkWbgjtVtSKFy3YIPubVo=">AAAB6HicbVDJSgNBEK2JW4xb1KOXxiAIQpiJgZhb0IvHBMwCyRB6OjVJm56F7h4hhHyBFw+KePWTvPk3dpLB/UHB470qqup5seBK2/a7lVlZXVvfyG7mtrZ3dvfy+wctFSWSYZNFIpIdjyoUPMSm5lpgJ5ZIA09g2xtfzf32HUrFo/BGT2J0AzoMuc8Z1UZqnPXzBbtoL0D+EiclBUhR7+ffeoOIJQGGmgmqVNexY+1OqdScCZzleonCmLIxHWLX0JAGqNzp4tAZOTHKgPiRNBVqslC/T0xpoNQk8ExnQPVI/fbm4n9eN9H+hTvlYZxoDNlykZ8IoiMy/5oMuESmxcQQyiQ3txI2opIybbLJmRCcr9+rBpVySqrOZwitUtE5L5Ya5ULtMo0jC0dwDKfgQAVqcA11aAIDhHt4hCfr1nqwnq2XZWvGSmcO4Qes1w+YRY0O</latexit>

b +
<latexit sha1_base64="4+Z89fQkWbgjtVtSKFy3YIPubVo=">AAAB6HicbVDJSgNBEK2JW4xb1KOXxiAIQpiJgZhb0IvHBMwCyRB6OjVJm56F7h4hhHyBFw+KePWTvPk3dpLB/UHB470qqup5seBK2/a7lVlZXVvfyG7mtrZ3dvfy+wctFSWSYZNFIpIdjyoUPMSm5lpgJ5ZIA09g2xtfzf32HUrFo/BGT2J0AzoMuc8Z1UZqnPXzBbtoL0D+EiclBUhR7+ffeoOIJQGGmgmqVNexY+1OqdScCZzleonCmLIxHWLX0JAGqNzp4tAZOTHKgPiRNBVqslC/T0xpoNQk8ExnQPVI/fbm4n9eN9H+hTvlYZxoDNlykZ8IoiMy/5oMuESmxcQQyiQ3txI2opIybbLJmRCcr9+rBpVySqrOZwitUtE5L5Ya5ULtMo0jC0dwDKfgQAVqcA11aAIDhHt4hCfr1nqwnq2XZWvGSmcO4Qes1w+YRY0O</latexit>

put 3 distinct put 1 object put 1 object put 1 object

objects into 3 positions into 1st position into 2nd position into 3rd position

14 Chapter 1: Combinatorial Analysis

Math 2421

1.3 Permutations

Theorem

Proof The experiment is equivalent to arranging n distinct objects into n positions.

···
<latexit sha1_base64="Ah+91sEoo3ktFGxhbeguRI68HOQ=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKezGQMwt6MVjBPOAZAmzs7PJmNmZZaZXCCH/4MWDIl79H2/+jZNk8V3QUFR1090VJIIbcN13J7eyura+kd8sbG3v7O4V9w/aRqWashZVQuluQAwTXLIWcBCsm2hG4kCwTjC+nPudO6YNV/IGJgnzYzKUPOKUgJXafRoqMINiyS27C+C/xMtICWVoDopv/VDRNGYSqCDG9Dw3AX9KNHAq2KzQTw1LCB2TIetZKknMjD9dXDvDJ1YJcaS0LQl4oX6fmJLYmEkc2M6YwMj89ubif14vhejcn3KZpMAkXS6KUoFB4fnrOOSaURATSwjV3N6K6YhoQsEGVLAheF+/1y1q1YzUvc8Q2pWyd1auXFdLjYssjjw6QsfoFHmohhroCjVRC1F0i+7RI3pylPPgPDsvy9ack80coh9wXj8A1RePjg==</latexit>

1 2 3 4 5 6 7 8 9 n-2 n-1 n

To fill the 1st position, there are n choices.

In total
To fill the 2nd position, there are n-1 choices.
To fill the 3rd position, there are n-2 choices. n ⇥ (n 1) ⇥ (n 2) ⇥ · · · ⇥ 1 = n!
···
<latexit sha1_base64="R1ZL8tf/BoNhH8WR8Q8V1JZqQNo=">AAACGXicbZDLSgMxFIYzXmu9VV26iRahLiwztVC7EIpuXFawF+gMJZOmbWgmMyRnhFL6Gm58FTcuFHGpK9/GtB2stx8CH/85h5Pz+5HgGmz7w1pYXFpeWU2tpdc3Nre2Mzu7dR3GirIaDUWomj7RTHDJasBBsGakGAl8wRr+4HJSb9wypXkob2AYMS8gPcm7nBIwVjtjSxd4wDTOyRPneM6FhF3aCUEnvnMuD9qZrJ23p8J/wUkgixJV25k3txPSOGASqCBatxw7Am9EFHAq2DjtxppFhA5Ij7UMSmI2eaPpZWN8ZJwO7obKPAl46n6fGJFA62Hgm86AQF//rk3M/2qtGLpn3ojLKAYm6WxRNxYYQjyJCXe4YhTE0AChipu/YtonilAwYaZNCM789rJRqZhA2fkKoV7IO6f5wnUxW7lI4kihfXSIcshBJVRBV6iKaoiiO/SAntCzdW89Wi/W66x1wUpm9tAPWe+fGl+fYQ==</latexit>

<latexit sha1_base64="Ah+91sEoo3ktFGxhbeguRI68HOQ=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKezGQMwt6MVjBPOAZAmzs7PJmNmZZaZXCCH/4MWDIl79H2/+jZNk8V3QUFR1090VJIIbcN13J7eyura+kd8sbG3v7O4V9w/aRqWashZVQuluQAwTXLIWcBCsm2hG4kCwTjC+nPudO6YNV/IGJgnzYzKUPOKUgJXafRoqMINiyS27C+C/xMtICWVoDopv/VDRNGYSqCDG9Dw3AX9KNHAq2KzQTw1LCB2TIetZKknMjD9dXDvDJ1YJcaS0LQl4oX6fmJLYmEkc2M6YwMj89ubif14vhejcn3KZpMAkXS6KUoFB4fnrOOSaURATSwjV3N6K6YhoQsEGVLAheF+/1y1q1YzUvc8Q2pWyd1auXFdLjYssjjw6QsfoFHmohhroCjVRC1F0i+7RI3pylPPgPDsvy9ack80coh9wXj8A1RePjg==</latexit>

To fill the nth position, there are 1 choices.

15 Chapter 1: Combinatorial Analysis
Math 2421

1.3 Permutations

Example

1 2 3 4 5 6 7 8 9

16 Chapter 1: Combinatorial Analysis

Math 2421

1.3 Permutations

Theorem

Proof ···
<latexit sha1_base64="Ah+91sEoo3ktFGxhbeguRI68HOQ=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKezGQMwt6MVjBPOAZAmzs7PJmNmZZaZXCCH/4MWDIl79H2/+jZNk8V3QUFR1090VJIIbcN13J7eyura+kd8sbG3v7O4V9w/aRqWashZVQuluQAwTXLIWcBCsm2hG4kCwTjC+nPudO6YNV/IGJgnzYzKUPOKUgJXafRoqMINiyS27C+C/xMtICWVoDopv/VDRNGYSqCDG9Dw3AX9KNHAq2KzQTw1LCB2TIetZKknMjD9dXDvDJ1YJcaS0LQl4oX6fmJLYmEkc2M6YwMj89ubif14vhejcn3KZpMAkXS6KUoFB4fnrOOSaURATSwjV3N6K6YhoQsEGVLAheF+/1y1q1YzUvc8Q2pWyd1auXFdLjYssjjw6QsfoFHmohhroCjVRC1F0i+7RI3pylPPgPDsvy9ack80coh9wXj8A1RePjg==</latexit>

A A B B B B C C C R R R

First, we view these n objects as all distinct objects and permute them, there are n! permutations
However, there are many objects are alike, so some permutations are essentially the same but
counted more than once.
For instance, consider the permutation ABBABBCCC……RRR
When we permute all As, or all Bs, or all Cs, … or all Rs, essentially they are the same permutation.
In other words, each permutation is counted n1 !n2 ! · · · nr ! times.
<latexit sha1_base64="oWn2HlGJ38XLgmizDE+tXK7YbNw=">AAAB/HicbZBLSwMxFIUz9VXra7RLN6lFcFVm2sLYXdGNywq2FtphyGTSNjSTDElGKEP9K25cKOLWH+LOf2P6UFrxQOBwzr3k8oUJo0o7zpeV29jc2t7J7xb29g8Oj+zjk44SqcSkjQUTshsiRRjlpK2pZqSbSILikJH7cHw96+8fiFRU8Ds9SYgfoyGnA4qRNlFgF3nglnhQLfVxJLSCPJClwC67FWcu6KyYqldzPfhTlcFSrcD+7EcCpzHhGjOkVM91Eu1nSGqKGZkW+qkiCcJjNCQ9YzmKifKz+fFTeG6SCA6ENI9rOE9XNzIUKzWJQzMZIz1Sf7tZ+F/XS/Xg0s8oT1JNOF58NEgZ1ALOSMCISoI1mxiDsKTmVohHSCKsDa/COoSGkVdfmob7C6FTrbi1SvW2Xm5eLXHkwSk4AxfABR5oghvQAm2AwQQ8gRfwaj1az9ab9b4YzVnLnSJYk/XxDSqolBU=</latexit>

17 Chapter 1: Combinatorial Analysis

Math 2421

1.3 Permutations

Example

n = 11
<latexit sha1_base64="wG3AqryCMAKCrgSztWgV7t2KfOo=">AAAB63icbVDLSgNBEOyNrxhfUY9eBoPgKezEQMxBCHrxGME8IFnC7GSSDJmdXWZmhbDkF7x4UMSrP+TNv3E2WXwXNBRV3XR3+ZHg2rjuu5NbWV1b38hvFra2d3b3ivsHbR3GirIWDUWouj7RTHDJWoYbwbqRYiTwBev406vU79wxpXkob80sYl5AxpKPOCUmleQFxoNiyS27C6C/BGekBBmag+JbfxjSOGDSUEG07mE3Ml5ClOFUsHmhH2sWETolY9azVJKAaS9Z3DpHJ1YZolGobEmDFur3iYQEWs8C33YGxEz0by8V//N6sRmdewmXUWyYpMtFo1ggE6L0cTTkilEjZpYQqri9FdEJUYQaG0/BhoC/fq9b1KoZqePPENqVMj4rV26qpcZlFkcejuAYTgFDDRpwDU1oAYUJ3MMjPDmB8+A8Oy/L1pyTzRzCDzivH1+Sjg4=</latexit>

n1 = 1
<latexit sha1_base64="LINGOjjcP6MhWuKgMrwczD7Fjp8=">AAAB7HicbVBNSwMxEJ2tX7V+VT16CRbBU9nUQu1BKHrxWMFtC+1Ssmm2Dc1mlyQrlNLf4MWDIl79Qd78N6bt4veDgcd7M8zMCxLBtXHddye3srq2vpHfLGxt7+zuFfcPWjpOFWUejUWsOgHRTHDJPMONYJ1EMRIFgrWD8dXcb98xpXksb80kYX5EhpKHnBJjJU/28QXuF0tu2V0A/SU4IyXI0OwX33qDmKYRk4YKonUXu4nxp0QZTgWbFXqpZgmhYzJkXUsliZj2p4tjZ+jEKgMUxsqWNGihfp+YkkjrSRTYzoiYkf7tzcX/vG5qwnN/ymWSGibpclGYCmRiNP8cDbhi1IiJJYQqbm9FdEQUocbmU7Ah4K/f6xa1akbq+DOEVqWMz8qVm2qpcZnFkYcjOIZTwFCDBlxDEzygwOEeHuHJkc6D8+y8LFtzTjZzCD/gvH4AFgaOdw==</latexit>
n2 = 4
<latexit sha1_base64="DSZh0CkHDgj3THVIXf52Te281/8=">AAAB7HicbVBNS8NAEJ3Ur1q/qh69LBbBU0lqoPYgFL14rGDaQhvKZrtpl242YXcjlNDf4MWDIl79Qd78N27b4PeDgcd7M8zMCxLOlLbtd6uwsrq2vlHcLG1t7+zulfcP2ipOJaEeiXksuwFWlDNBPc00p91EUhwFnHaCydXc79xRqVgsbvU0oX6ER4KFjGBtJE8MahfuoFyxq/YC6C9xclKBHK1B+a0/jEkaUaEJx0r1HDvRfoalZoTTWamfKppgMsEj2jNU4IgqP1scO0MnRhmiMJamhEYL9ftEhiOlplFgOiOsx+q3Nxf/83qpDs/9jIkk1VSQ5aIw5UjHaP45GjJJieZTQzCRzNyKyBhLTLTJp2RCcL5+bxjU3Zw0nM8Q2rWqc1at3biV5mUeRxGO4BhOwYE6NOEaWuABAQb38AhPlrAerGfrZdlasPKZQ/gB6/UDHBiOew==</latexit>
n3 = 4
<latexit sha1_base64="30sh1SQ3t1YCJFDYOOpqrbF82II=">AAAB7HicbVBNa8JAEJ3YL2s/tO2xl6VS6EkSFayHgrSXHi00KmiQzbrRxc0m7G4KEvwNvfTQUnrtD+qt/6arhn4/GHi8N8PMPD/mTGnbfrdya+sbm1v57cLO7t5+sXRw2FFRIgl1ScQj2fOxopwJ6mqmOe3FkuLQ57TrT68WfveOSsUicatnMfVCPBYsYARrI7liWLuoD0tlu2Ivgf4SJyNlyNAelt4Go4gkIRWacKxU37Fj7aVYakY4nRcGiaIxJlM8pn1DBQ6p8tLlsXN0apQRCiJpSmi0VL9PpDhUahb6pjPEeqJ+ewvxP6+f6ODcS5mIE00FWS0KEo50hBafoxGTlGg+MwQTycytiEywxESbfAomBOfr96ZBo56RpvMZQqdacWqV6k293LrM4sjDMZzAGTjQgBZcQxtcIMDgHh7hyRLWg/Vsvaxac1Y2cwQ/YL1+AB2ejnw=</latexit>
n4 = 2
<latexit sha1_base64="+kqrz1fFEV6fHhVGvPGX9GJc1HM=">AAAB7HicbVBNS8NAEJ3Ur1q/qh69LBbBU0lqoPYgFL14rGDaQhvKZrtpl242YXcjlNDf4MWDIl79Qd78N27b4PeDgcd7M8zMCxLOlLbtd6uwsrq2vlHcLG1t7+zulfcP2ipOJaEeiXksuwFWlDNBPc00p91EUhwFnHaCydXc79xRqVgsbvU0oX6ER4KFjGBtJE8M3IvaoFyxq/YC6C9xclKBHK1B+a0/jEkaUaEJx0r1HDvRfoalZoTTWamfKppgMsEj2jNU4IgqP1scO0MnRhmiMJamhEYL9ftEhiOlplFgOiOsx+q3Nxf/83qpDs/9jIkk1VSQ5aIw5UjHaP45GjJJieZTQzCRzNyKyBhLTLTJp2RCcL5+bxjU3Zw0nM8Q2rWqc1at3biV5mUeRxGO4BhOwYE6NOEaWuABAQb38AhPlrAerGfrZdlasPKZQ/gB6/UDHByOew==</latexit>

18 Chapter 1: Combinatorial Analysis

Math 2421 Dr. Dong XIA

1.3 Permutations
Seating in circle

Example

10 1 2 9
10
1 1 2 3
9
8
7 6 5
3
4
8
7
6 5
2

4
3 ···
<latexit sha1_base64="Ah+91sEoo3ktFGxhbeguRI68HOQ=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKezGQMwt6MVjBPOAZAmzs7PJmNmZZaZXCCH/4MWDIl79H2/+jZNk8V3QUFR1090VJIIbcN13J7eyura+kd8sbG3v7O4V9w/aRqWashZVQuluQAwTXLIWcBCsm2hG4kCwTjC+nPudO6YNV/IGJgnzYzKUPOKUgJXafRoqMINiyS27C+C/xMtICWVoDopv/VDRNGYSqCDG9Dw3AX9KNHAq2KzQTw1LCB2TIetZKknMjD9dXDvDJ1YJcaS0LQl4oX6fmJLYmEkc2M6YwMj89ubif14vhejcn3KZpMAkXS6KUoFB4fnrOOSaURATSwjV3N6K6YhoQsEGVLAheF+/1y1q1YzUvc8Q2pWyd1auXFdLjYssjjw6QsfoFHmohhroCjVRC1F0i+7RI3pylPPgPDsvy9ack80coh9wXj8A1RePjg==</latexit>
10
9
8
7 6
4
5

10!
Rotating it clock wisely = 9!
gives the same arrangements <latexit sha1_base64="3piXVFmHXXeaxkqN0t5D8Tf/6wE=">AAAB+nicbVDLSgMxFL1TX7W+prp0k1oEV2WmCupCKLpxWcE+oC0lk2ba0ExmSDJKGedT3LhQxK1f4s6/MW1noa0H7uVwzr3k5ngRZ0o7zreVW1ldW9/Ibxa2tnd29+ziflOFsSS0QUIeyraHFeVM0IZmmtN2JCkOPE5b3vhm6rceqFQsFPd6EtFegIeC+YxgbaS+Xez6EpPEdUqpaenVZalvl52KMwNaJm5GypCh3re/uoOQxAEVmnCsVMd1It1LsNSMcJoWurGiESZjPKQdQwUOqOols9NTdGyUAfJDaUpoNFN/byQ4UGoSeGYywHqkFr2p+J/XibV/0UuYiGJNBZk/5Mcc6RBNc0ADJinRfGIIJpKZWxEZYZOFNmkVTAju4peXSbNacU8r1buzcu06iyMPh3AEJ+DCOdTgFurQAAKP8Ayv8GY9WS/Wu/UxH81Z2c4B/IH1+QNRlZK7</latexit>
10

19 Chapter 1: Combinatorial Analysis

Math 2421

1.3 Permutations

Seating in circle

Theorem

Proof

n 1 2 n-1
n
1 1 2 3
n-1
.
.
.
7 6 5
3
4
.
.
.
7
6 5
2

4
3 ···
<latexit sha1_base64="Ah+91sEoo3ktFGxhbeguRI68HOQ=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKezGQMwt6MVjBPOAZAmzs7PJmNmZZaZXCCH/4MWDIl79H2/+jZNk8V3QUFR1090VJIIbcN13J7eyura+kd8sbG3v7O4V9w/aRqWashZVQuluQAwTXLIWcBCsm2hG4kCwTjC+nPudO6YNV/IGJgnzYzKUPOKUgJXafRoqMINiyS27C+C/xMtICWVoDopv/VDRNGYSqCDG9Dw3AX9KNHAq2KzQTw1LCB2TIetZKknMjD9dXDvDJ1YJcaS0LQl4oX6fmJLYmEkc2M6YwMj89ubif14vhejcn3KZpMAkXS6KUoFB4fnrOOSaURATSwjV3N6K6YhoQsEGVLAheF+/1y1q1YzUvc8Q2pWyd1auXFdLjYssjjw6QsfoFHmohhroCjVRC1F0i+7RI3pylPPgPDsvy9ack80coh9wXj8A1RePjg==</latexit>
n
n-1
.
.
.
7 6
4
5

Rotating it clock wisely

gives the same arrangements

20 Chapter 1: Combinatorial Analysis

Math 2421

1.3 Permutations

Seating in circle

Example

10 1 2 2 1
10
9 equivalent 3
3 9
8 4 4 8
7 6 5 5 7
6

First, like arranging n objects in a round table, there are (n-1)! arrangements

In addition, for a necklace, we can flip it reversely, e.g., like a mirror. They are
actually the same necklace
Mirror the necklaces gives the same one

(n 1)!
Therefore, the answer is
<latexit sha1_base64="O/VBzIhh4Ev+NLFToC/AEWg4ETI=">AAAB+XicbZDLSsNAFIZP6q3WW9Slm2gR6sKS1ELtrujGZQV7gTaUyXTSDp1MwsykUELexI0LRdz6Ju58G6dt8P7DwM9/zuGc+byIUals+93IrayurW/kNwtb2zu7e+b+QVuGscCkhUMWiq6HJGGUk5aiipFuJAgKPEY63uR6Xu9MiZA05HdqFhE3QCNOfYqR0tHANPu+QDgp8XPn7DhNKunALNpleyHrr3EyU4RMzYH51h+GOA4IV5ghKXuOHSk3QUJRzEha6MeSRAhP0Ij0tOUoINJNFpen1qlOhpYfCv24shbp94kEBVLOAk93BkiN5e/aPPyv1ouVf+kmlEexIhwvF/kxs1RozTFYQyoIVmymDcKC6lstPEYahdKwChqC8/X3ulatmpm68wmhXSk7F+XKbbXYuMpw5OEITqAEDtSgATfQhBZgmMI9PMKTkRgPxrPxsmzNGdnMIfyQ8foBPKaTAg==</latexit>
2

21 Chapter 1: Combinatorial Analysis

Math 2421

1.4 Combinations

Example

Basically, in combinations, we do not care about the order the items

are chosen or arranged.

22 Chapter 1: Combinatorial Analysis

Math 2421

1.4 Combinations

Theorem

denoted by

called “n choose r”

Properties

23 Chapter 1: Combinatorial Analysis

Math 2421

1.4 Combinations

Example

24 Chapter 1: Combinatorial Analysis

Math 2421

1.4 Combinations

Example

n-m functional antennas

X X X X m defective antennas

✓ ◆
In total, there are n-m+1 slots to place the defective antennas. n m+1
We need to choose m places to put the defective antennas. m
<latexit sha1_base64="uhg2GLelVjKfDhtginodxz2JwRw=">AAAB+XicbVDLSgNBEJyNrxhfqx69DAZBEMNuFPQY9OIxgnlAEsLspJMMmccyMxsIS/7EiwdFvPon3vwbJ8keNLGgoajqprsrijkzNgi+vdza+sbmVn67sLO7t3/gHx7VjUo0hRpVXOlmRAxwJqFmmeXQjDUQEXFoRKP7md8YgzZMySc7iaEjyECyPqPEOqnr+6m8FBdhmw6VMoDFtOsXg1IwB14lYUaKKEO163+1e4omAqSlnBjTCoPYdlKiLaMcpoV2YiAmdEQG0HJUEgGmk84vn+Izp/RwX2lX0uK5+nsiJcKYiYhcpyB2aJa9mfif10ps/7aTMhknFiRdLOonHFuFZzHgHtNALZ84Qqhm7lZMh0QTal1YBRdCuPzyKqmXS+FVqfx4XazcZXHk0Qk6RecoRDeogh5QFdUQRWP0jF7Rm5d6L96797FozXnZzDH6A+/zB75gkxU=</latexit>

25 Chapter 1: Combinatorial Analysis

 Math 2421

1.4 Combinations
Useful Combinatorial Identities

Theorem

Algebraic Proof

Combinatorial Proof

26 Chapter 1: Combinatorial Analysis

Math 2421

1.4 Combinations
Useful Combinatorial Identities

Binomial Theorem

Combinatorial Proof

27 Chapter 1: Combinatorial Analysis

Math 2421

1.4 Combinations
Useful Combinatorial Identities

Example

Example

Proof

28 Chapter 1: Combinatorial Analysis

Math 2421

1.4 Combinations
Useful Combinatorial Identities

Example

Proof

29 Chapter 1: Combinatorial Analysis

Math 2421

1.5 Multinomial Coefficients

Example

Proof

30 Chapter 1: Combinatorial Analysis

Math 2421

1.5 Multinomial Coefficients

Example

Another Proof n1 n2

⇢
⇢
<latexit sha1_base64="t0mujrsvit7fRMGI/102MrxNyrg=">AAAB7nicbVBNS8NAEJ3Ur1q/qh69LBbBU0lqofZW9OKxgv2AJpTNdpMu3WzC7kYooT/CiwdFvPp7vPlv3LZRrPpg4PHeDDPz/IQzpW37wyqsrW9sbhW3Szu7e/sH5cOjropTSWiHxDyWfR8rypmgHc00p/1EUhz5nPb8yfXc791TqVgs7vQ0oV6EQ8ECRrA2Us/1WRi62bBccar2Asj+Q76sCuRoD8vv7igmaUSFJhwrNXDsRHsZlpoRTmclN1U0wWSCQzowVOCIKi9bnDtDZ0YZoSCWpoRGC/XnRIYjpaaRbzojrMfqtzcX//MGqQ4uvYyJJNVUkOWiIOVIx2j+OxoxSYnmU0MwkczcisgYS0y0Sai0GkLToFHPSdP5DqFbqzoX1dptvdK6yuMowgmcwjk40IAW3EAbOkBgAg/wBM9WYj1aL9brsrVg5TPHsALr7RN7n4/s</latexit>
<latexit sha1_base64="yed20aBZHavRZSaiDXRrapC/jyw=">AAAB6nicbVBNSwMxEJ2tX7V+VT16CRbBU9mthdpb0YvHirYW2qVk02wbmk2WJCuUpT/BiwdFvPqLvPlvTNtVrPpg4PHeDDPzgpgzbVz3w8mtrK6tb+Q3C1vbO7t7xf2DtpaJIrRFJJeqE2BNORO0ZZjhtBMriqOA07tgfDnz7+6p0kyKWzOJqR/hoWAhI9hY6Ub0K/1iySu7cyD3D/mySpCh2S++9waSJBEVhnCsdddzY+OnWBlGOJ0WeommMSZjPKRdSwWOqPbT+alTdGKVAQqlsiUMmqs/J1IcaT2JAtsZYTPSv72Z+J/XTUx47qdMxImhgiwWhQlHRqLZ32jAFCWGTyzBRDF7KyIjrDAxNp3Ccgh1i1o1I3XvO4R2peydlSvX1VLjIosjD0dwDKfgQQ0acAVNaAGBITzAEzw73Hl0XpzXRWvOyWYOYQnO2ycmOI33</latexit>

<latexit sha1_base64="HJWjW4t9OCIQKyPdRulsg+2AYIU=">AAAB6nicbVBNSwMxEJ2tX7V+VT16CRbBU9mthdpb0YvHirYW2qVk02wbmk2WJCuUpT/BiwdFvPqLvPlvTNtVrPpg4PHeDDPzgpgzbVz3w8mtrK6tb+Q3C1vbO7t7xf2DtpaJIrRFJJeqE2BNORO0ZZjhtBMriqOA07tgfDnz7+6p0kyKWzOJqR/hoWAhI9hY6Ub0vX6x5JXdOZD7h3xZJcjQ7BffewNJkogKQzjWuuu5sfFTrAwjnE4LvUTTGJMxHtKupQJHVPvp/NQpOrHKAIVS2RIGzdWfEymOtJ5Ege2MsBnp395M/M/rJiY891Mm4sRQQRaLwoQjI9HsbzRgihLDJ5Zgopi9FZERVpgYm05hOYS6Ra2akbr3HUK7UvbOypXraqlxkcWRhyM4hlPwoAYNuIImtIDAEB7gCZ4d7jw6L87rojXnZDOHsATn7RMktI32</latexit>
<latexit sha1_base64="t0mujrsvit7fRMGI/102MrxNyrg=">AAAB7nicbVBNS8NAEJ3Ur1q/qh69LBbBU0lqofZW9OKxgv2AJpTNdpMu3WzC7kYooT/CiwdFvPp7vPlv3LZRrPpg4PHeDDPz/IQzpW37wyqsrW9sbhW3Szu7e/sH5cOjropTSWiHxDyWfR8rypmgHc00p/1EUhz5nPb8yfXc791TqVgs7vQ0oV6EQ8ECRrA2Us/1WRi62bBccar2Asj+Q76sCuRoD8vv7igmaUSFJhwrNXDsRHsZlpoRTmclN1U0wWSCQzowVOCIKi9bnDtDZ0YZoSCWpoRGC/XnRIYjpaaRbzojrMfqtzcX//MGqQ4uvYyJJNVUkOWiIOVIx2j+OxoxSYnmU0MwkczcisgYS0y0Sai0GkLToFHPSdP5DqFbqzoX1dptvdK6yuMowgmcwjk40IAW3EAbOkBgAg/wBM9WYj1aL9brsrVg5TPHsALr7RN7n4/s</latexit>

···
<latexit sha1_base64="Ah+91sEoo3ktFGxhbeguRI68HOQ=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKezGQMwt6MVjBPOAZAmzs7PJmNmZZaZXCCH/4MWDIl79H2/+jZNk8V3QUFR1090VJIIbcN13J7eyura+kd8sbG3v7O4V9w/aRqWashZVQuluQAwTXLIWcBCsm2hG4kCwTjC+nPudO6YNV/IGJgnzYzKUPOKUgJXafRoqMINiyS27C+C/xMtICWVoDopv/VDRNGYSqCDG9Dw3AX9KNHAq2KzQTw1LCB2TIetZKknMjD9dXDvDJ1YJcaS0LQl4oX6fmJLYmEkc2M6YwMj89ubif14vhejcn3KZpMAkXS6KUoFB4fnrOOSaURATSwjV3N6K6YhoQsEGVLAheF+/1y1q1YzUvc8Q2pWyd1auXFdLjYssjjw6QsfoFHmohhroCjVRC1F0i+7RI3pylPPgPDsvy9ack80coh9wXj8A1RePjg==</latexit>

1 2 3 4 5 6 7 8 9 n-2 n-1 n

The problem can be cast to arranging n objects in a line and then the first n1 objects <latexit sha1_base64="BdXfHL9lWeDxwbokiN6DdIfxI0c=">AAAB6nicbVDLTgIxFL2DL8QX6tJNIzFxRWYGFNgR3bjEKEgCE9IpHWjodCZtx4RM+AQ3LjTGrV/kzr+xAxgf8SRNTs65N73n+DFnStv2h5VbWV1b38hvFra2d3b3ivsHHRUlktA2iXgkuz5WlDNB25ppTruxpDj0Ob3zJ5eZf3dPpWKRuNXTmHohHgkWMIK1kW7EwBkUS3bZrti1Rh0ZYp+7Z+6cVGqugxxDMpRgidag+N4fRiQJqdCEY6V6jh1rL8VSM8LprNBPFI0xmeAR7RkqcEiVl85PnaETowxREEnzhEZz9edGikOlpqFvJkOsx+qvl4n/eb1EB3UvZSJONBVk8VGQcKQjlOVGQyYp0XxqCCaSmVsRGWOJiTbtFEwJX0lN9oZBrbokje8SOm7ZqZTd62qpebGsIw9HcAyn4EANmnAFLWgDgRE8wBM8W9x6tF6s18VozlruHMIvWG+fcxmOLA==</latexit>

belong to 1st group; the second n2 objects belong to the 2nd group; ….. <latexit sha1_base64="ORBUgVptKT2R9mEDR17sMW694aQ=">AAAB6nicbVDLTgIxFL2DL8QX6tJNIzFxRWYGFNgR3bjEKEgCE9IpHWjodCZtx4RM+AQ3LjTGrV/kzr+xAxgf8SRNTs65N73n+DFnStv2h5VbWV1b38hvFra2d3b3ivsHHRUlktA2iXgkuz5WlDNB25ppTruxpDj0Ob3zJ5eZf3dPpWKRuNXTmHohHgkWMIK1kW7EwB0US3bZrti1Rh0ZYp+7Z+6cVGqugxxDMpRgidag+N4fRiQJqdCEY6V6jh1rL8VSM8LprNBPFI0xmeAR7RkqcEiVl85PnaETowxREEnzhEZz9edGikOlpqFvJkOsx+qvl4n/eb1EB3UvZSJONBVk8VGQcKQjlOVGQyYp0XxqCCaSmVsRGWOJiTbtFEwJX0lN9oZBrbokje8SOm7ZqZTd62qpebGsIw9HcAyn4EANmnAFLWgDgRE8wBM8W9x6tF6s18VozlruHMIvWG+fdJ2OLQ==</latexit>

There are n! different arrangements of n objects in a line.

However, for each arrangement, no matter how you permute the first n1objects, they are <latexit sha1_base64="BdXfHL9lWeDxwbokiN6DdIfxI0c=">AAAB6nicbVDLTgIxFL2DL8QX6tJNIzFxRWYGFNgR3bjEKEgCE9IpHWjodCZtx4RM+AQ3LjTGrV/kzr+xAxgf8SRNTs65N73n+DFnStv2h5VbWV1b38hvFra2d3b3ivsHHRUlktA2iXgkuz5WlDNB25ppTruxpDj0Ob3zJ5eZf3dPpWKRuNXTmHohHgkWMIK1kW7EwBkUS3bZrti1Rh0ZYp+7Z+6cVGqugxxDMpRgidag+N4fRiQJqdCEY6V6jh1rL8VSM8LprNBPFI0xmeAR7RkqcEiVl85PnaETowxREEnzhEZz9edGikOlpqFvJkOsx+qvl4n/eb1EB3UvZSJONBVk8VGQcKQjlOVGQyYp0XxqCCaSmVsRGWOJiTbtFEwJX0lN9oZBrbokje8SOm7ZqZTd62qpebGsIw9HcAyn4EANmnAFLWgDgRE8wBM8W9x6tF6s18VozlruHMIvWG+fcxmOLA==</latexit>

the same divisions; similarly, you can permute the second n2 objects, they are also the <latexit sha1_base64="ORBUgVptKT2R9mEDR17sMW694aQ=">AAAB6nicbVDLTgIxFL2DL8QX6tJNIzFxRWYGFNgR3bjEKEgCE9IpHWjodCZtx4RM+AQ3LjTGrV/kzr+xAxgf8SRNTs65N73n+DFnStv2h5VbWV1b38hvFra2d3b3ivsHHRUlktA2iXgkuz5WlDNB25ppTruxpDj0Ob3zJ5eZf3dPpWKRuNXTmHohHgkWMIK1kW7EwB0US3bZrti1Rh0ZYp+7Z+6cVGqugxxDMpRgidag+N4fRiQJqdCEY6V6jh1rL8VSM8LprNBPFI0xmeAR7RkqcEiVl85PnaETowxREEnzhEZz9edGikOlpqFvJkOsx+qvl4n/eb1EB3UvZSJONBVk8VGQcKQjlOVGQyYp0XxqCCaSmVsRGWOJiTbtFEwJX0lN9oZBrbokje8SOm7ZqZTd62qpebGsIw9HcAyn4EANmnAFLWgDgRE8wBM8W9x6tF6s18VozlruHMIvWG+fdJ2OLQ==</latexit>

same divisions;….

31 Chapter 1: Combinatorial Analysis

Math 2421

1.5 Multinomial Coefficients

Notations

Example

32 Chapter 1: Combinatorial Analysis

Math 2421

1.5 Multinomial Coefficients

Example

Example

33 Chapter 1: Combinatorial Analysis

Math 2421 Dr. Dong XIA

1.5 Multinomial Coefficients

Multinomial Theorem

34 Chapter 1: Combinatorial Analysis

Math 2421

1.6 Number of Integer Solutions

Theorem

Proof

1 1 1 1 1 1 1 1 1 1 n ones

^<latexit sha1_base64="YAx0QlCk2VKsmnPHarCE8OYVVQg=">AAAB7XicbVBNS8NAEJ34WetX1aOXxSJ4KkkV9Fj04rGC/YA2lM1m0q7dZMPuRiml/8GLB0W8+n+8+W/ctjlo64OBx3szzMwLUsG1cd1vZ2V1bX1js7BV3N7Z3dsvHRw2tcwUwwaTQqp2QDUKnmDDcCOwnSqkcSCwFQxvpn7rEZXmMrk3oxT9mPYTHnFGjZWa3ScM+9grld2KOwNZJl5OypCj3it9dUPJshgTwwTVuuO5qfHHVBnOBE6K3UxjStmQ9rFjaUJj1P54du2EnFolJJFUthJDZurviTGNtR7Fge2MqRnoRW8q/ud1MhNd+WOepJnBhM0XRZkgRpLp6yTkCpkRI0soU9zeStiAKsqMDahoQ/AWX14mzWrFO69U7y7Ktes8jgIcwwmcgQeXUINbqEMDGDzAM7zCmyOdF+fd+Zi3rjj5zBH8gfP5A5YRjyI=</latexit>
^
<latexit sha1_base64="YAx0QlCk2VKsmnPHarCE8OYVVQg=">AAAB7XicbVBNS8NAEJ34WetX1aOXxSJ4KkkV9Fj04rGC/YA2lM1m0q7dZMPuRiml/8GLB0W8+n+8+W/ctjlo64OBx3szzMwLUsG1cd1vZ2V1bX1js7BV3N7Z3dsvHRw2tcwUwwaTQqp2QDUKnmDDcCOwnSqkcSCwFQxvpn7rEZXmMrk3oxT9mPYTHnFGjZWa3ScM+9grld2KOwNZJl5OypCj3it9dUPJshgTwwTVuuO5qfHHVBnOBE6K3UxjStmQ9rFjaUJj1P54du2EnFolJJFUthJDZurviTGNtR7Fge2MqRnoRW8q/ud1MhNd+WOepJnBhM0XRZkgRpLp6yTkCpkRI0soU9zeStiAKsqMDahoQ/AWX14mzWrFO69U7y7Ktes8jgIcwwmcgQeXUINbqEMDGDzAM7zCmyOdF+fd+Zi3rjj5zBH8gfP5A5YRjyI=</latexit>
^
<latexit sha1_base64="YAx0QlCk2VKsmnPHarCE8OYVVQg=">AAAB7XicbVBNS8NAEJ34WetX1aOXxSJ4KkkV9Fj04rGC/YA2lM1m0q7dZMPuRiml/8GLB0W8+n+8+W/ctjlo64OBx3szzMwLUsG1cd1vZ2V1bX1js7BV3N7Z3dsvHRw2tcwUwwaTQqp2QDUKnmDDcCOwnSqkcSCwFQxvpn7rEZXmMrk3oxT9mPYTHnFGjZWa3ScM+9grld2KOwNZJl5OypCj3it9dUPJshgTwwTVuuO5qfHHVBnOBE6K3UxjStmQ9rFjaUJj1P54du2EnFolJJFUthJDZurviTGNtR7Fge2MqRnoRW8q/ud1MhNd+WOepJnBhM0XRZkgRpLp6yTkCpkRI0soU9zeStiAKsqMDahoQ/AWX14mzWrFO69U7y7Ktes8jgIcwwmcgQeXUINbqEMDGDzAM7zCmyOdF+fd+Zi3rjj5zBH8gfP5A5YRjyI=</latexit>
^
<latexit sha1_base64="YAx0QlCk2VKsmnPHarCE8OYVVQg=">AAAB7XicbVBNS8NAEJ34WetX1aOXxSJ4KkkV9Fj04rGC/YA2lM1m0q7dZMPuRiml/8GLB0W8+n+8+W/ctjlo64OBx3szzMwLUsG1cd1vZ2V1bX1js7BV3N7Z3dsvHRw2tcwUwwaTQqp2QDUKnmDDcCOwnSqkcSCwFQxvpn7rEZXmMrk3oxT9mPYTHnFGjZWa3ScM+9grld2KOwNZJl5OypCj3it9dUPJshgTwwTVuuO5qfHHVBnOBE6K3UxjStmQ9rFjaUJj1P54du2EnFolJJFUthJDZurviTGNtR7Fge2MqRnoRW8q/ud1MhNd+WOepJnBhM0XRZkgRpLp6yTkCpkRI0soU9zeStiAKsqMDahoQ/AWX14mzWrFO69U7y7Ktes8jgIcwwmcgQeXUINbqEMDGDzAM7zCmyOdF+fd+Zi3rjj5zBH8gfP5A5YRjyI=</latexit>
r-1 separators

Choose r-1 from n-1 places to put the separators

35 Chapter 1: Combinatorial Analysis

Math 2421

1.6 Number of Integer Solutions

Theorem

Proof

36 Chapter 1: Combinatorial Analysis

Math 2421

1.6 Number of Integer Solutions

Example

✓ ◆
23
= 1771
<latexit sha1_base64="vfGF6EoSwkitaU5zsefZRL3ukWQ=">AAAB+3icbVBNS8NAEN3Ur1q/Yj16WSyCp5K0Qr0IRS8eK9gPaEPZbCft0k027G7EEvJXvHhQxKt/xJv/xm2bg7Y+GHi8N8PMPD/mTGnH+bYKG5tb2zvF3dLe/sHhkX1c7iiRSAptKriQPZ8o4CyCtmaaQy+WQEKfQ9ef3s797iNIxUT0oGcxeCEZRyxglGgjDe1yWqsP6EQIBbieXbuNhju0K07VWQCvEzcnFZSjNbS/BiNBkxAiTTlRqu86sfZSIjWjHLLSIFEQEzolY+gbGpEQlJcubs/wuVFGOBDSVKTxQv09kZJQqVnom86Q6Ila9ebif14/0cGVl7IoTjREdLkoSDjWAs+DwCMmgWo+M4RQycytmE6IJFSbuEomBHf15XXSqVXderV2f1lp3uRxFNEpOkMXyEUN1ER3qIXaiKIn9Ixe0ZuVWS/Wu/WxbC1Y+cwJ+gPr8wfQLpL9</latexit>
3

37 Chapter 1: Combinatorial Analysis

Math 2421

1.6 Number of Integer Solutions

Example

How do we arrange them so that no two defectives are consecutive?

Fix the defective ones

and insert functional
ones into them

38 Chapter 1: Combinatorial Analysis

Math 2421

1.6 Number of Integer Solutions

Example

x1
<latexit sha1_base64="rOQ5oVTuyyayRkj+VAOOHMwqB6c=">AAAB6nicbVDLTgJBEOz1ifhCPXqZSEw8kV0kkSPRi0eM8khgQ2aHASbMzm5meo1kwyd48aAxXv0ib/6Ns8BBwUo6qVR1p7sriKUw6Lrfztr6xubWdm4nv7u3f3BYODpumijRjDdYJCPdDqjhUijeQIGSt2PNaRhI3grGN5nfeuTaiEg94CTmfkiHSgwEo2il+6ee1ysU3ZLrVr1KmWQkA/GWSREWqPcKX91+xJKQK2SSGtPx3Bj9lGoUTPJpvpsYHlM2pkPesVTRkBs/nZ06JedW6ZNBpG0pJDP190RKQ2MmYWA7Q4ojs+xl4n9eJ8FB1U+FihPkis0XDRJJMCLZ36QvNGcoJ5ZQpoW9lbAR1ZShTSdvQ1h5eZU0yyXvslS+qxRr14s4cnAKZ3ABHlxBDW6hDg1gMIRneIU3RzovzrvzMW9dcxYzJ/AHzucPJKGNtA==</latexit>
0 x2
<latexit sha1_base64="PNz300+E4DlDhejnDWxSTi2Gd3U=">AAAB6nicbVBNSwMxEJ34WetX1aOXYBE8ld21YI9FLx4r2g9ol5JNs21oNrskWbEs/QlePCji1V/kzX9jtu1BWx8MPN6bYWZekAiujeN8o7X1jc2t7cJOcXdv/+CwdHTc0nGqKGvSWMSqExDNBJesabgRrJMoRqJAsHYwvsn99iNTmsfywUwS5kdkKHnIKTFWun/qe/1S2ak4Ts2tejgnObC7TMqwQKNf+uoNYppGTBoqiNZd10mMnxFlOBVsWuylmiWEjsmQdS2VJGLaz2anTvG5VQY4jJUtafBM/T2RkUjrSRTYzoiYkV72cvE/r5uasOZnXCapYZLOF4WpwCbG+d94wBWjRkwsIVRxeyumI6IINTadog1h5eVV0vIq7mXFu6uW69eLOApwCmdwAS5cQR1uoQFNoDCEZ3iFNyTQC3pHH/PWNbSYOYE/QJ8/JiWNtQ==</latexit>
0 x3
<latexit sha1_base64="bEfSEorWe0BnfKSJiznQJjvjqKA=">AAAB6nicbVBNTwIxEJ3FL8Qv1KOXRmLiiewCiRyJXjxilI8ENqRbutDQdjdt10g2/AQvHjTGq7/Im//GLnBQ8CWTvLw3k5l5QcyZNq777eQ2Nre2d/K7hb39g8Oj4vFJW0eJIrRFIh6pboA15UzSlmGG026sKBYBp51gcpP5nUeqNIvkg5nG1Bd4JFnICDZWun8aVAfFklt23bpXq6CMZEDeKinBEs1B8as/jEgiqDSEY617nhsbP8XKMMLprNBPNI0xmeAR7VkqsaDaT+enztCFVYYojJQtadBc/T2RYqH1VAS2U2Az1qteJv7n9RIT1v2UyTgxVJLFojDhyEQo+xsNmaLE8KklmChmb0VkjBUmxqZTsCGsvbxO2pWyVy1X7mqlxvUyjjycwTlcggdX0IBbaEILCIzgGV7hzeHOi/PufCxac85y5hT+wPn8ASepjbY=</latexit>
0 … 0 xm
<latexit sha1_base64="kkadkj7HMT6A/uxYiv/EXuUuBlw=">AAAB6nicbVBNTwIxEJ3FL8Qv1KOXRmLiiewiCRyJXjxilI8ENqRbutDQdjdt10g2/AQvHjTGq7/Im//GLnBQ8CWTvLw3k5l5QcyZNq777eQ2Nre2d/K7hb39g8Oj4vFJW0eJIrRFIh6pboA15UzSlmGG026sKBYBp51gcpP5nUeqNIvkg5nG1Bd4JFnICDZWun8aiEGx5JZdt+5VKygjGZC3SkqwRHNQ/OoPI5IIKg3hWOue58bGT7EyjHA6K/QTTWNMJnhEe5ZKLKj20/mpM3RhlSEKI2VLGjRXf0+kWGg9FYHtFNiM9aqXif95vcSEdT9lMk4MlWSxKEw4MhHK/kZDpigxfGoJJorZWxEZY4WJsekUbAhrL6+TdqXsXZUrd9VS43oZRx7O4BwuwYMaNOAWmtACAiN4hld4c7jz4rw7H4vWnLOcOYU/cD5/AH+RjfA=</latexit>
0 xm+1
<latexit sha1_base64="q5+lM9rKZjioIwkk+W/V2Q12aQs=">AAAB7nicbVBNSwMxEJ2tX7V+VT16CRZBEMpuW7DHohePFewHtEvJptk2NMkuSVYsS3+EFw+KePX3ePPfmG170NYHA4/3ZpiZF8ScaeO6305uY3Nreye/W9jbPzg8Kh6ftHWUKEJbJOKR6gZYU84kbRlmOO3GimIRcNoJJreZ33mkSrNIPphpTH2BR5KFjGBjpc7TIBVX3mxQLLll1617tQrKSAbkrZISLNEcFL/6w4gkgkpDONa657mx8VOsDCOczgr9RNMYkwke0Z6lEguq/XR+7gxdWGWIwkjZkgbN1d8TKRZaT0VgOwU2Y73qZeJ/Xi8xYd1PmYwTQyVZLAoTjkyEst/RkClKDJ9agoli9lZExlhhYmxCBRvC2svrpF0pe9Vy5b5Watws48jDGZzDJXhwDQ24gya0gMAEnuEV3pzYeXHenY9Fa85ZzpzCHzifPx3Qj2w=</latexit>

0 represents a defective antennas

x1
<latexit sha1_base64="rOQ5oVTuyyayRkj+VAOOHMwqB6c=">AAAB6nicbVDLTgJBEOz1ifhCPXqZSEw8kV0kkSPRi0eM8khgQ2aHASbMzm5meo1kwyd48aAxXv0ib/6Ns8BBwUo6qVR1p7sriKUw6Lrfztr6xubWdm4nv7u3f3BYODpumijRjDdYJCPdDqjhUijeQIGSt2PNaRhI3grGN5nfeuTaiEg94CTmfkiHSgwEo2il+6ee1ysU3ZLrVr1KmWQkA/GWSREWqPcKX91+xJKQK2SSGtPx3Bj9lGoUTPJpvpsYHlM2pkPesVTRkBs/nZ06JedW6ZNBpG0pJDP190RKQ2MmYWA7Q4ojs+xl4n9eJ8FB1U+FihPkis0XDRJJMCLZ36QvNGcoJ5ZQpoW9lbAR1ZShTSdvQ1h5eZU0yyXvslS+qxRr14s4cnAKZ3ABHlxBDW6hDg1gMIRneIU3RzovzrvzMW9dcxYzJ/AHzucPJKGNtA==</latexit>

represents x1 consecutive working antennas <latexit sha1_base64="rOQ5oVTuyyayRkj+VAOOHMwqB6c=">AAAB6nicbVDLTgJBEOz1ifhCPXqZSEw8kV0kkSPRi0eM8khgQ2aHASbMzm5meo1kwyd48aAxXv0ib/6Ns8BBwUo6qVR1p7sriKUw6Lrfztr6xubWdm4nv7u3f3BYODpumijRjDdYJCPdDqjhUijeQIGSt2PNaRhI3grGN5nfeuTaiEg94CTmfkiHSgwEo2il+6ee1ysU3ZLrVr1KmWQkA/GWSREWqPcKX91+xJKQK2SSGtPx3Bj9lGoUTPJpvpsYHlM2pkPesVTRkBs/nZ06JedW6ZNBpG0pJDP190RKQ2MmYWA7Q4ojs+xl4n9eJ8FB1U+FihPkis0XDRJJMCLZ36QvNGcoJ5ZQpoW9lbAR1ZShTSdvQ1h5eZU0yyXvslS+qxRr14s4cnAKZ3ABHlxBDW6hDg1gMIRneIU3RzovzrvzMW9dcxYzJ/AHzucPJKGNtA==</latexit>

39 Chapter 1: Combinatorial Analysis