# Calculate : 1

For example, this group <1,2,3,4,5> would be analysed lượt thích this:

1-2, 1-3, 1-4, 1-52-3, 2-4, 2-53-4, 3-54-5By creating little diagrams lượt thích this I"ve figured out the pattern which is as follows:

Users - Comparisons2 - 13 - 3 (+2)4 - 6 (+3)5 - 10 (+4)6 - 15 (+5)7 - 21 (+6)8 - 28 (+7)9 - 36 (+8)I need to be able khổng lồ take any number of users, and calculate how many comparisons it will take to lớn compare every user with every other user.

Bạn đang xem: Calculate : 1

Can someone please tell me what the formula for this is?

combinatorics summation

giới thiệu

Cite

Follow

edited May 2, 2014 at 15:23

MJD

62.4k3636 gold badges277277 silver badges490490 bronze badges

asked May 2, năm trước at 15:21

OwenOwen

14111 gold badge11 silver badge66 bronze badges

$endgroup$

12

| Show 7 more comments

## 7 Answers 7

Sorted by: Reset to default

Highest score (default) Date modified (newest first) Date created (oldest first)

16

$egingroup$

You want lớn know how many ways there are khổng lồ choose $2$ users froma phối of $n$ users.

Generally, the number of ways to choose $k$ elements from a phối oforder $n$ (that is, all elements in the mix are distinct) is denotedby $$inomnk$$

and is equivalent to $$fracn!(n-k)!k!$$

In the case of $k=2$ the latter equals to lớn $$fracn!(n-2)!2!=fracn(n-1)2$$

which is also the sum of $1+2+...+n-1$.

For more information see Binomial coefficient & Arithmetic progression

nói qua

Cite

Follow

answered May 2, năm trước at 15:28

BelgiBelgi

22k1515 gold badges8686 silver badges149149 bronze badges

$endgroup$

showroom a comment |

13

$egingroup$

The sum of $0+cdots + n-1$ is $$frac12(n-1)n.$$

Here $n$ is the number of users; there are 0 comparisons needed for the first user alone, 1 for the second user (to compare them to the first), 2 for the third user, và so on, up khổng lồ the $n$th user who must be compared with the $n-1$ previous users.

For example, for $9$ people you are adding up $0+1+2+3+4+5+6+7+8$, which is equal lớn $$frac12cdot 8cdot 9= frac722 = 36$$ and for $10$ people you may compute $$frac12cdot9cdot10 = frac902 = 45.$$

cốt truyện

Cite

Follow

answered May 2, năm trước at 15:25

community wiki

MJD

$endgroup$

địa chỉ cửa hàng a comment |

5

$egingroup$

The following way lớn getting the solution is beautiful & said to have been found by young Gauss in school. The idea is that the order of adding $1+2+cdots+n=S_n$ does not change the value of the sum. Therefore:

$$1 + 2 + ldots + (n-1) + n=S_n$$$$n + (n-1) + ldots + 2 + 1=S_n$$

Adding the two equations term by term gives

$$(n+1)+(n+1)+ldots+(n+1)=2S_n$$

so $n(n+1)=2S_n$. For $n$ persons, there are $S_n-1$ possibilities, as others answers have shown already nicely.

tóm tắt

Cite

Follow

answered May 2, năm trước at 15:33

binkyhorsebinkyhorse

80411 gold badge77 silver badges1111 bronze badges

$endgroup$

add a comment |

0

$egingroup$

The discrete sum up to lớn a finite value $N$ is given by,

$$sum_n=1^N n = frac12N(N+1)$$

**Proof:**

The proof by induction roughly boils down to:

$$S_N = 1+ 2 +dots+N$$

$$S_N+1= 1+ 2 + dots + N + (N+1) = underbracefrac12N(N+1)_S_N + (N+1)$$

assuming that the induction hypothesis is true. The right hand side:

$$fracN(N+1)2+(N+1)=frac(N+1)(N+2)2$$

which is precisely the induction hypothesis applied khổng lồ $S_N+1$.

Just for your own curiosity, the case $N=infty$ is of course divergent. However, with the use of the zeta function, it may be regularized to yield,

$$sum_n=1^inftyn = zeta(-1)=-frac112$$

mô tả

Cite

Follow

answered May 2, năm trước at 15:31

JPhyJPhy

1,6411010 silver badges2222 bronze badges

$endgroup$

showroom a bình luận |

0

$egingroup$

$$N=2: 1 + 2 = (1 + 2) = 1 imes3$$

$$N=4: 1 + 2 + 3 + 4 = (1 + 4) + (2 + 3) = 2 imes5$$

$$N=6: 1 + 2 + 3 + 4 + 5 + 6 = (1 + 6) + (2 + 5) + (3 + 4) = 3 imes7$$

$$N=8: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8= (1 + 8) + (2 + 7) + (3 + 6)+ (4 + 5) = 4 imes9$$

More generally, $N/2 imes(N + 1)$.

For odd $N$, sum the $N-1$ first terms (using the even formula) together with $N$, giving $(N-1)/2 imes N+N=N imes(N+1)/2$.

Xem thêm: Ioe: Hấp Dẫn - Luyện Thi Ioe Tiếng Anh Lớp 5 Vòng 1 Đến Vòng 35

giới thiệu

Cite

Follow

edited May 2, năm trước at 15:47

answered May 2, 2014 at 15:41

user65203user65203

$endgroup$

7

$egingroup$

corsiKa: the formula explicitly shows the sum from 1 to lớn $N$ inclusive (triangular numbers) and is perfectly correct. It is NOT the formula for the number of comparisons between $N$ users. $endgroup$

–user65203

May 2, năm trước at 21:38

$egingroup$ The sum must be taken from $1$ lớn $Users-1$ inclusive. $endgroup$

–user65203

May 2, 2014 at 21:51

| Show 2 more comments

0

$egingroup$

Here is another way khổng lồ find the sum of the first $n$ squares that generalizes to lớn sums of higher powers.

$(k+1)^2 - k^2 = 2k+1$

$sum_k=1^n ( (k+1)^2 - k^2 ) = sum_k=1^n (2k+1)$

$(n+1)^2 - 1^2 = 2 sum_k=1^n k + n$

$sum_k=1^n k = frac (n+1)^2 - 1 - n 2 = fracn^2+n2$

chia sẻ

Cite

Follow

answered May 3, năm trước at 7:11

user21820user21820

54.1k77 gold badges8585 silver badges231231 bronze badges

$endgroup$

địa chỉ a phản hồi |

-1

$egingroup$

This is kind of a pseudo code:

Say you have n number of people, & you labeled them.

for i in (1,2,3,...,n), person i need to compare with all the people who has a number larger (strictly), so person i need to compare (n-i) times.

so adding up would be(n-1) + (n-2) + ... + 3 + 2 + 1...

which would be the sum from 1 to lớn (n-1)

giới thiệu

Cite

Follow

answered May 2, năm trước at 15:26

TYZTYZ

36711 silver badge1212 bronze badges

$endgroup$

showroom a comment |

## Your Answer

Thanks for contributing an answer to american-home.com.vnematics Stack Exchange!

Please be sure to*answer the question*. Provide details & share your research!

But *avoid* …

Use american-home.com.vnJax to format equations. american-home.com.vnJax reference.

To learn more, see our tips on writing great answers.

Xem thêm: Ngữ Văn Lớp 6 Bài 1 - Soạn Văn Lớp 6 Bài 1: Truyện

Draft saved

Draft discarded

### Sign up or log in

Sign up using Google

Sign up using Facebook

Sign up using thư điện tử and Password

Submit

### Post as a guest

Name

thư điện tử Required, but never shown

### Post as a guest

Name

Required, but never shown

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to lớn our terms of service, privacy policy và cookie policy

## Not the answer you're looking for? Browse other questions tagged combinatorics summation or ask your own question.

The Overflow Blog

Featured on Meta

Linked

130

Proof $1+2+3+4+cdots+n = fracn imes(n+1)2$

98

What is the term for a factorial type operation, but with summation instead of products?

8

Formula for the number of connections needed khổng lồ connect every node in a set?

Related

2

Scheduling a team based activity with 10 different teams and X different games. Every team must meet each other ONCE but never twice,

1

Finding the minimum wins in a round-robin tournament.

1

Formulating an equation for a group sorting program.

0

Number of distinguishable permutations with repetition và restrictions

1

Understanding a Proof in COMBINATORICA 3 ( 3 - 4 ) (1983) 325--329

2

Finding statistical data for repeated surveys in a population

0

In how many ways can 'i' Indian, 'j' chinese, 'k' mexicans, 'l' americans và 'm' canadians be arranged in groups?

0

The probability that any of the teams certainly win. The number of encounters which make this probability 98%.

2

The american-home.com.vn of password policy anti-patterns

Hot Network Questions more hot questions

Question feed

Subscribe lớn RSS

Question feed to subscribe to this RSS feed, copy and paste this URL into your RSS reader.

american-home.com.vnematics

Company

Stack Exchange Network

Site thiết kế / logo sản phẩm © 2022 Stack Exchange Inc; user contributions licensed under cc by-sa. Rev2022.7.1.42502

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.