Combinatorics

well there are two ways you can do it the first way is to do the first one and the second is to do is the second one but instead of useing three ones use a two and a one on the one where it says 1+1+1+17 change it to 17+2+1.

In how many ways can you write 20 as a sum of three counting numbers?

One Way: 1+18+1

Not a Way: 1+1+1+17

Anybody now how to solve this?

I assume in your case, there is only a recursive method:

Let P(n,k) is the number of partitions of a positive integer n into exactly k parts:

For instance, \(7 = 5+1+1=4+2+1=3+2+2\), so \(p(7,3) = 4\)

Formula:

\(\begin{array}{|rcll|} \hline P(0,0) &=& 1 \\ P(n,0) &=& 0 \qquad n\ge 1 \\ P(n,1 )&=& 1 \\ P(n,n) &=& 1 \\ P(n,k) &=& P(n-k,k)+P(n-1,k-1) \qquad \text{ or } \qquad P(n+k,k) = \sum \limits_{j=1}^{k}P(n,j) \\ \hline \end{array} \)

In how many ways can you write 20 as a sum of three counting numbers?

p(20,3) = 33

P(n,k):

p(n,k):

n = 1 -------------------------

p(1,1) = 1

n = 2 -------------------------

p(2,1) = 1

p(2,2) = 1

n = 3 -------------------------

p(3,1) = 1

p(3,2) = 1

p(3,3) = 1

n = 4 -------------------------

p(4,1) = 1

p(4,2) = 2

p(4,3) = 1

p(4,4) = 1

n = 5 -------------------------

p(5,1) = 1

p(5,2) = 2

p(5,3) = 2

p(5,4) = 1

p(5,5) = 1

n = 6 -------------------------

p(6,1) = 1

p(6,2) = 3

p(6,3) = 3

p(6,4) = 2

p(6,5) = 1

p(6,6) = 1

n = 7 -------------------------

p(7,1) = 1

p(7,2) = 3

p(7,3) = 4

p(7,4) = 3

p(7,5) = 2

p(7,6) = 1

p(7,7) = 1

n = 8 -------------------------

p(8,1) = 1

p(8,2) = 4

p(8,3) = 5

p(8,4) = 5

p(8,5) = 3

p(8,6) = 2

p(8,7) = 1

p(8,8) = 1

n = 9 -------------------------

p(9,1) = 1

p(9,2) = 4

p(9,3) = 7

p(9,4) = 6

p(9,5) = 5

p(9,6) = 3

p(9,7) = 2

p(9,8) = 1

p(9,9) = 1

n = 10 -------------------------

p(10,1) = 1

p(10,2) = 5

p(10,3) = 8

p(10,4) = 9

p(10,5) = 7

p(10,6) = 5

p(10,7) = 3

p(10,8) = 2

p(10,9) = 1

p(10,10) = 1

n = 11 -------------------------

p(11,1) = 1

p(11,2) = 5

p(11,3) = 10

p(11,4) = 11

p(11,5) = 10

p(11,6) = 7

p(11,7) = 5

p(11,8) = 3

p(11,9) = 2

p(11,10) = 1

p(11,11) = 1

n = 12 -------------------------

p(12,1) = 1

p(12,2) = 6

p(12,3) = 12

p(12,4) = 15

p(12,5) = 13

p(12,6) = 11

p(12,7) = 7

p(12,8) = 5

p(12,9) = 3

p(12,10) = 2

p(12,11) = 1

p(12,12) = 1

n = 13 -------------------------

p(13,1) = 1

p(13,2) = 6

p(13,3) = 14

p(13,4) = 18

p(13,5) = 18

p(13,6) = 14

p(13,7) = 11

p(13,8) = 7

p(13,9) = 5

p(13,10) = 3

p(13,11) = 2

p(13,12) = 1

p(13,13) = 1

n = 14 -------------------------

p(14,1) = 1

p(14,2) = 7

p(14,3) = 16

p(14,4) = 23

p(14,5) = 23

p(14,6) = 20

p(14,7) = 15

p(14,8) = 11

p(14,9) = 7

p(14,10) = 5

p(14,11) = 3

p(14,12) = 2

p(14,13) = 1

p(14,14) = 1

n = 15 -------------------------

p(15,1) = 1

p(15,2) = 7

p(15,3) = 19

p(15,4) = 27

p(15,5) = 30

p(15,6) = 26

p(15,7) = 21

p(15,8) = 15

p(15,9) = 11

p(15,10) = 7

p(15,11) = 5

p(15,12) = 3

p(15,13) = 2

p(15,14) = 1

p(15,15) = 1

n = 16 -------------------------

p(16,1) = 1

p(16,2) = 8

p(16,3) = 21

p(16,4) = 34

p(16,5) = 37

p(16,6) = 35

p(16,7) = 28

p(16,8) = 22

p(16,9) = 15

p(16,10) = 11

p(16,11) = 7

p(16,12) = 5

p(16,13) = 3

p(16,14) = 2

p(16,15) = 1

p(16,16) = 1

n = 17 -------------------------

p(17,1) = 1

p(17,2) = 8

p(17,3) = 24

p(17,4) = 39

p(17,5) = 47

p(17,6) = 44

p(17,7) = 38

p(17,8) = 29

p(17,9) = 22

p(17,10) = 15

p(17,11) = 11

p(17,12) = 7

p(17,13) = 5

p(17,14) = 3

p(17,15) = 2

p(17,16) = 1

p(17,17) = 1

n = 18 -------------------------

p(18,1) = 1

p(18,2) = 9

p(18,3) = 27

p(18,4) = 47

p(18,5) = 57

p(18,6) = 58

p(18,7) = 49

p(18,8) = 40

p(18,9) = 30

p(18,10) = 22

p(18,11) = 15

p(18,12) = 11

p(18,13) = 7

p(18,14) = 5

p(18,15) = 3

p(18,16) = 2

p(18,17) = 1

p(18,18) = 1

n = 19 -------------------------

p(19,1) = 1

p(19,2) = 9

p(19,3) = 30

p(19,4) = 54

p(19,5) = 70

p(19,6) = 71

p(19,7) = 65

p(19,8) = 52

p(19,9) = 41

p(19,10) = 30

p(19,11) = 22

p(19,12) = 15

p(19,13) = 11

p(19,14) = 7

p(19,15) = 5

p(19,16) = 3

p(19,17) = 2

p(19,18) = 1

p(19,19) = 1

n = 20 -------------------------

p(20,1) = 1

p(20,2) = 10

p(20,3) = 33

p(20,4) = 64

p(20,5) = 84

p(20,6) = 90

p(20,7) = 82

p(20,8) = 70

p(20,9) = 54

p(20,10) = 42

p(20,11) = 30

p(20,12) = 22

p(20,13) = 15

p(20,14) = 11

p(20,15) = 7

p(20,16) = 5

p(20,17) = 3

p(20,18) = 2

p(20,19) = 1

p(20,20) = 1

...

In how many ways can you write 20 as a sum of three counting numbers?

p(20,3) = 33

\(\begin{array}{|r|ll|} \hline & 20 = \\ \hline 1 & 1+1+18 \\ 2 & 1+2+17 \\ 3 & 1+3+16 \\ 4 & 1+4+15 \\ 5 & 1+5+14 \\ 6 & 1+6+13 \\ 7 & 1+7+12 \\ 8 & 1+8+11 \\ 9 & 1+9+10 \\ \hline 10 & 2+2+16 \\ 11 & 2+3+15 \\ 12 & 2+4+14 \\ 13 & 2+5+13 \\ 14 & 2+6+12 \\ 15 & 2+7+11 \\ 16 & 2+8+10 \\ 17 & 2+9+9 \\ \hline 18 & 3+3+14 \\ 19 & 3+4+13 \\ 20 & 3+5+12 \\ 21 & 3+6+11 \\ 22 & 3+7+10 \\ 23 & 3+8+9 \\ \hline 24 & 4+4+12 \\ 25 & 4+5+11 \\ 26 & 4+6+10 \\ 27 & 4+7+9 \\ 28 & 4+8+8 \\ \hline 29 & 5+5+10 \\ 30 & 5+6+9 \\ 31 & 5+7+8 \\ \hline 32 & 6+6+8 \\ 33 & 6+7+7 \\ \hline \end{array}\)

First Position Number        +    _____    +      _______

       1                                          18                     1

       1                                          17                     2

       1                                          16                     3

       1                                          15                     4

       1                                          14                     5

       1                                          13                     6

       1                                          12                     7

       1                                          11                     8

       1                                          10                     9

       1                                          9                      10      (repeats from here)

      2                                          16                    2

      2                                          15                    3

      2                                          14                    4

      2                                          13                    5

      2                                          12                    6

      2                                          11                    7

      2                                          10                    8

      2                                            9                    9 

      2                                            8                  10      ( repeats from here)     

     3                                           14                    3

     3                                           13                    4

     3                                           12                    5

     3                                           11                    6

     3                                           10                    7

     3                                            9                     8

     3                                            8                     9      (repeats from here ) 

     4                                            12                   4

     4                                            11                   5

     4                                            10                   6

     4                                             9                    7

     4                                             8                    8

     4                                             7                    9       (repeats from here )   

     5                                           10                    5   

     5                                            9                     6

     5                                            8                     7

     5                                            7                     8     (repeats from here )

     6                                            8                     6

     6                                            7                     7

     6                                            6                     8    (repeats from here )

Everything else from this point forward is a repeat

So we have     9 + 8  + 6 + 5 + 3 + 2  =  17 + 11 + 5   =  33 possibilities

From Mathworld: http://mathworld.wolfram.com/PartitionFunctionP.html

There is this exact formula:1/(72)[6n^2-7-9(-1)^n+16cos(2/3Pi*n)], where n=20....(63)

=33. This can be simplified to: Nearest integer P[20, 3] =1/12(20)^2 =33.................(66)