+0

# Combinatorics

+1
110
5

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?

Guest Dec 6, 2017
Sort:

#1
+20
0

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.

kevanportman123  Dec 6, 2017
#2
0

Thank you, but I would prefer not to list every single combination and then count them all up, as that would take a long time. I would believe there is some sort of combinatorical way to solve this problem, I just don't know how.

Guest Dec 6, 2017
#3
+18934
+2

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}$$

heureka  Dec 8, 2017
#4
+82590
+1

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

CPhill  Dec 8, 2017
#5
+1

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)

Guest Dec 8, 2017

### 24 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details