counting

Question 1

THE PIGEONHOLE PRINCIPLE

and prove it:

Another name?

Answer 1

If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

Proof: We prove the pigeonhole principle using proof by contraposition.

Suppose that none of the k boxes contains more than one object. Then the total number of objects would be at most k.

This is a contradiction because there are at least k + 1 objects.

Dirichlet drawer principle

Question 2

Corollary about functions from pigeonhole Principle:

Proof:

Answer 2

A function f from a set with k + 1 or more elements to a set with k elements is not one-to-one.

Suppose that for each element y in the codomain of f we have a box that contains all elements x of the domain of f such that f(x) = y.

Because the domain contains k + 1 or more elements and the codomain contains only k elements, the pigeonhole principle tells us that one of these boxes contains two or more elements x of the domain.

This means that f cannot be one-to-one.

Question 3

Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion.

Answer 3

Let n be a positive integer. Consider the n + 1 integers 1, 11, 111, … , 11 … 1 (where the last integer in this list is the integer with n + 1 1s in its decimal expansion).

Note that there are n possible remainders when an integer is divided by n.

Because there are n + 1 integers in this list, by the pigeonhole principle there must be two with the same remainder when divided by n.

The larger of these integers less the smaller one is a multiple of n, which has a decimal expansion consisting entirely of 0s and 1s.

Question 4

THE GENERALIZED PIGEONHOLE PRINCIPLE

Proof:

Answer 4

If N objects are placed into k boxes, then there is at least one box containing at least ⌈N∕k⌉ objects.

We will use a proof by contraposition.

Suppose that none of the boxes contains more than ⌈N∕k⌉ − 1 objects. Then, the total number of objects is at most k(⌈N/k⌉− 1)< k((N/k + 1)− 1)= N, where the inequality ⌈N∕k⌉ < (N∕k) + 1 has been used. Thus, the total number of objects is less than N. This completes the proof by contraposition.

Question 5

How do we solve this common problem:

What is the minimum number of objects such that at least r of these objects must be in one of k boxes when these objects are distributed among the boxes?

Answer 5

When we have N objects, the generalized pigeonhole principle tells us there must be at least r objects in one of the boxes as long as ⌈N∕k⌉ ≥ r.

The smallest integer N with N∕k > r − 1, namely, N = k(r − 1) + 1, is the smallest integer satisfying the inequality ⌈N∕k⌉ ≥ r.

Could a smaller value of N suffice? The answer is no, because if we had k(r − 1) objects, we could put r − 1 of them in each of the k boxes and no box would have at least r objects.

Question 6

What is a subsequence?

Answer 6

Suppose that a1, a2, … , aN is a sequence of real numbers.

A subsequence of this sequence is a sequence of the form ai1 , ai2, … , aim , where 1 ≤ i1 < i2 < ⋯ < im ≤ N.

Hence, a subsequence is a sequence obtained from the original sequence by including some of the terms of the original sequence in their original order, and perhaps not including other terms.

Question 7

Theorem of Sequence and Subsequences

Answer 7

Every sequence of n^2 + 1 distinct real numbers contains a subsequence of length n + 1 that is either strictly increasing or strictly decreasing.

Question 8

Ramsey theory

Answer 8

The final example shows how the generalized pigeonhole principle can be applied to an important part of combinatorics called Ramsey theory, after the English mathematician F. P. Ramsey. In general, Ramsey theory deals with the distribution of subsets of elements of sets.

Question 9

Ramsey number

Answer 9

The Ramsey number R(m, n), where m and n are positive integers greater than or equal to 2, denotes the minimum number of people at a party such that there are either m mutual friends or n mutual enemies, assuming that every pair of people at the party are friends or enemies.

Example 13 shows that R(3, 3) ≤ 6. We conclude that R(3, 3) = 6 because in a group of five people where every two people are friends or enemies, there may not be three mutual friends or three mutual enemies (see Exercise 28).

Question 10

Ramsey number properties:

Answer 10

Note that by symmetry it can be shown that
R(m, n) = R(n, m) (see Exercise 32). We also have R(2, n) = n for every positive integer n ≥ 2
(see Exercise 31). The exact values of only nine Ramsey numbers R(m, n) with 3 ≤ m ≤ n are
known, including R(4, 4) = 18. Only bounds are known for many other Ramsey numbers, including R(5, 5), which is known to satisfy 43 ≤ R(5, 5) ≤ 49.

Question 11

THE PRODUCT RULE

Answer 11

Suppose that a procedure can be broken down into a sequence of
two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first
task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.

Question 12

An extended version of the product rule:

Answer 12

Suppose that a procedure is carried
out by performing the tasks T1, T2, … , Tm in sequence. If each task Ti
, i = 1, 2, … , n, can be
done in ni ways, regardless of how the previous tasks were done, then there are n1 ⋅ n2 ⋅⋯⋅ nm
ways to carry out the procedure. This version of the product rule can be proved by mathematical
induction from the product rule for two tasks

Question 13

THE SUM RULE

Answer 13

If a task can be done either in one of n1 ways or in one of n2 ways, where
none of the set of n1 ways is the same as any of the set of n2 ways, then there are n1 + n2
ways to do the task.

Question 14

The product rule is often phrased in terms of sets in this way:

Answer 14

If A1, A2, … , Am are finite
sets, then the number of elements in the Cartesian product of these sets is the product of the
number of elements in each set. To relate this to the product rule, note that the task of choosing an element in the Cartesian product A1 × A2 × ⋯ × Am is done by choosing an element
in A1, an element in A2, … , and an element in Am. By the product rule it follows that
|A1 × A2 × ⋯ × Am| = |A1| ⋅ |A2| ⋅⋯⋅ |Am|.

Question 15

We can extend the sum rule to more than two tasks. ?

Answer 15

Suppose that a task can be done in one
of n1 ways, in one of n2 ways, … , or in one of nm ways, where none of the set of ni ways of
doing the task is the same as any of the set of nj ways, for all pairs i and j with 1 ≤ i < j ≤ m.
Then the number of ways to do the task is n1 + n2 + ⋯ + nm.

Question 16

The sum rule can be phrased in terms of sets as:

Answer 16

If A1, A2, … , Am are pairwise disjoint
finite sets, then the number of elements in the union of these sets is the sum of the numbers of
elements in the sets. To relate this to our statement of the sum rule, note there are |Ai
| ways to
choose an element from Ai for i = 1, 2, … , m. Because the sets are pairwise disjoint, when we
select an element from one of the sets Ai
, we do not also select an element from a different set
Aj
. Consequently, by the sum rule, because we cannot select an element from two of these sets
at the same time, the number of ways to choose an element from one of the sets, which is the
number of elements in the union, is
|A1 ∪ A2 ∪ ⋯ ∪ Am| = |A1| + |A2| + ⋯ + |Am| when Ai ∩ Aj = for all i, j.

This equality applies only when the sets in question are pairwise disjoint.

Question 17

The Subtraction Rule (Inclusion–Exclusion for Two Sets)

Answer 17

If a task can be done in either n1 ways or n2 ways, then the
number of ways to do the task is n1 + n2 minus the number of ways to do the task that are
common to the two different ways.

Question 18

The subtraction rule is also known as the principle of inclusion–exclusion, especially when
it is used to count the number of elements in the union of two sets.

Answer 18

Because there are |A1 ∪ A2| ways to select an element
in either A1 or in A2, and |A1 ∩ A2| ways to select an element common to both sets, we have
|A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|.

The subtraction rule, or the principle of inclusion–exclusion, can be generalized to find the
number of ways to do one of n different tasks or, equivalently, to find the number of elements
in the union of n sets, whenever n is a positive integer

Question 19

THE DIVISION RULE

Application:

Answer 19

There are n∕d ways to do a task if it can be done using a procedure
that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to
way w.

Remark: The division rule comes in handy when it appears that a task can be done in n different
ways, but it turns out that for each way of doing the task, there are d equivalent ways of doing it. Under these circumstances, we can conclude that there are n∕d inequivalent ways of doing
the task.

Question 20

restate the division rule in terms of sets:

Answer 20

“If the finite set A is the union of n pairwise

disjoint subsets each with d elements, then n = |A|∕d.”

Question 21

formulate the division rule in terms of functions:

Answer 21

“If f is a function from A
to B where A and B are finite sets, and that for every value y ∈ B there are exactly d values
x ∈ A such that f(x) = y (in which case, we say that f is d-to-one), then |B| = |A|∕d.”

Question 22

Tree Diagrams:

Answer 22

A tree consists of a root, a number
of branches leaving the root, and possible additional branches leaving the endpoints of other
branches.
To use trees in counting, we use a branch
to represent each possible choice. We represent the possible outcomes by the leaves, which are
the endpoints of branches not having other branches starting at them.

Question 23

A permutation of a set of n distinct objects is?

Answer 23

A permutation of a set of n distinct objects is an ordered arrangement of these objects.

Question 24

r-permutation?

Answer 24

We also are interested in ordered arrangements of some of the elements of a set. An ordered arrangement of r elements of a set is called an r-permutation.
The number of r-permutations of a set with n elements is denoted by P(n, r). We can find P(n, r)
using the product rule.

Question 25

Theorem.

We now use the product rule to find a formula for P(n, r)

Answer 25

If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are
P(n, r) = n(n − 1)(n − 2) ⋯ (n − r + 1)
r-permutations of a set with n distinct elements.

Question 26

P(n,0) ?

Answer 26

Note that P(n, 0) = 1 whenever n is a nonnegative integer because there is exactly one way to
order zero elements.

That is, there is exactly one list with no elements in it, namely the empty list.

Question 27

Corollary:

Formula for r permutation:

Answer 27

If n and r are integers with 0 ≤ r ≤ n, then

P(n, r) = n!/(n − r)!

Question 28

Ex 8: How many different committees of three students can be formed from a group of four students?

An approach to solve this?

Answer 28

Example 8 illustrates that many counting problems can be solved by finding the number of
subsets of a particular size of a set with n elements, where n is a positive integer

Question 29

r Combination:

definition and denotion

Answer 29

An r-combination of elements of a set is an unordered selection of r elements from the set.
Thus, an r-combination is simply a subset of the set with r elements.

The number of r-combinations of a set with n distinct elements is denoted by C(n, r). Note
that C(n, r) is also denoted by (^n vr)
and is called a binomial coefficient.

Question 30

Theorem

to calculate r combination.

Answer 30

The number of r-combinations of a set with n elements, where n is a nonnegative integer and
r is an integer with 0 ≤ r ≤ n, equals
C(n, r) = n!/r! (n − r)!

We can determine the number of r-combinations of a set with n elements using the formula
for the number of r-permutations of a set.
Note that the r-permutations of a set can be
obtained by first forming r-combinations and then ordering the elements in these combinations.

Question 31

Proof of:

C(n, r) = n!/r! (n − r)!

Answer 31

P(n, r) = C(n, r) ⋅ P(r, r).
thats why.
OR division Rule
each of the C(n, r) r-combinations of a set with n elements
corresponds to exactly P(r, r) r-permutations. Hence, by the division rule, C(n, r) = P(n,r)/P(r,r).

Because the
order of elements in a combination does not matter and there are P(r, r) ways to order r elements
in an r-combination of n elements

Question 32

Computation Of C(n,r):

Answer 32

It’s not helpful with C(n, r) = n!/r! (n − r)!.
Cuz t it is practical to compute exact values of factorials
exactly only for small integer values, and when floating point arithmetic is used, the formula may produce a non int.
So, make it : C(n,r) = n(n − 1) ⋯ (n − r + 1)/r!

Then factor out common factors in
the numerator n(n − 1) ⋯ (n − r + 1) and in the denominator r!.

Question 33

Corollary 2:

a key identity enjoyed by the numbers C(n, k).

Answer 33

Let n and r be nonnegative integers with r ≤ n. Then C(n, r) = C(n, n − r).

Question 34

combinatorial proof:

Answer 34

A combinatorial proof of an identity is a proof that uses counting arguments to prove that
both sides of the identity count the same objects but in different ways or a proof that is based
on showing that there is a bijection between the sets of objects counted by the two sides of
the identity. These two types of proofs are called double counting proofs and bijective proofs,
respectively

Question 35

a bijective proof to show that C(n, r) = C(n, n − r)

Answer 35

Suppose that S is a set with n elements. The function that maps a subset A
of S to Abar is a bijection between subsets of S with r elements and subsets with n − r elements
(as the reader should verify). The identity C(n, r) = C(n, n − r) follows because when there is a
bijection between two finite sets, the two sets must have the same number of elements.

Question 36

Double counting proof for C(n, r) = C(n, n − r)

Answer 36

Alternatively, we can reformulate this argument as a double counting proof. By definition,
the number of subsets of S with r elements equals C(n, r). But each subset A of S is also determined by specifying which elements are not in A, and so are in A. Because the complement of
a subset of S with r elements has n − r elements, there are also C(n, n − r) subsets of S with r
elements. It follows that C(n, r) = C(n, n − r).

Question 37

Binomial Expression:

Answer 37

Sum of 2 terms such as x + y.

terms can be products of constants or variables.

Question 38

Obtain Expansion of (x + y)^3 using combinatorial proof:

Answer 38

= (x + y)(x + y)(x + y)
when this is expanded, all products of a term in the
first sum, a term in the second sum, and a term in the third sum are added.

Terms of the form x^3,x^2y, xy^2, and y^3 arise.

To obtain a term of the form x3, an x must be chosen in each of the sums, andthis can be done in only one way.
Thus, the x^3 term in the product has a coefficient of 1. To obtain a term of the form x^2y, an x must be chosen in two of the three sums (and consequently a y in the other sum).
Hence, the number of such terms is the number of 2-combinations of three objects, namely,
(3
2).
Similarly, the number of terms of the form xy2 is the number of ways to pick one of the three
sums to obtain an x (and consequently take a y from each of the other two sums). This can be done in
(3
1) ways.
Finally, the only way to obtain a y3 term is to choose the y for each of the three sums
in the product, and this can be done in exactly one way.
Consequently, it follows that
(x + y)^3 = (x + y)(x + y)(x + y) = (xx + xy + yx + yy)(x + y)
= xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy
= x^3 + 3x^2y + 3xy^2 + y^3.

Question 39

Theorem 1:

THE BINOMIAL THEOREM

Answer 39

Let x and y be variables, and let n be a nonnegative integer.
Then

(x + y)^n = page 437

Question 40

Proof of the bionomial thm :

Answer 40

We use a combinatorial proof. The terms in the product when it is expanded are of the
form x^(n−j)y^j for j = 0, 1, 2, … , n. To count the number of terms of this form, note that to
obtain such a term it is necessary to choose n − j xs from the n binomial factors (so that the
other j terms in the product are ys). Therefore, the coefficient of x^(n−j)y^j is
( n
n−j), which is equal to
(n
j).
This proves the theorem.

Question 41

Corollary 1:

Sum of coefficients : and proof:

Answer 41

Let n be a nonnegative integer. Then
2^n = C(n,r)
where r goes from 0 to n.

1. Binomial them with x=1, y=1. (1 +1)^n = 2^n

OR

think of it as set with n elements has total 2^n subsets.
that’s the cardinality of Power set.

Question 42

Corollary 2:

Sum of coeffiecients of x - y:

look in book.

Answer 42

= 0
x = 1, y = -1.
so, (1 + (-1) )^n = 0^n

this implies sum of coefficients with odd r = Sum with even r.

Also, ways of picking subsets with even cardinality = ways of picking subsets with odd cardinality…?

Question 43

Corollary 3:

sum of coefficients * 2^k

Answer 43

= 3^n

Bionomial thm for x= 1, y = 2.

(1 + 2)^n = 3^n

Question 44

Pascal’s Identity :

Answer 44

Let n and k be positive integers with n ≥ k. Then

C ( n+1 , k) = C ( n , k-1 ) + C ( n , k )

Question 45

Proof of Pascal’s Identity :

Answer 45

We will use a combinatorial proof. Suppose that T is a set containing n + 1 elements. Let
a be an element in T, and let S = T − {a}. Note that there are
(n+1
k)
subsets of T containing k elements. However, a subset of T with k elements either contains a together with k − 1 elements
of S, or contains k elements of S and does not contain a. Because there are
( n
k−1) subsets of k − 1 elements of S, there are
( n
k−1)
subsets of k elements of T that contain a. And there are (n
k)
subsets of k elements of T that do not contain a, because there are
(n
k)
subsets of k elements of S.

Or algebrically as well.

Question 46

About recursive definition of Binomial Coefficients:

Answer 46

Pascal’s identity, together with the initial conditions
(n
0)=
(n
n) = 1 for all integers n,
can be used to recursively define binomial coefficients. This recursive definition is useful in the computation of binomial coefficients because only addition, and not multiplication, of integers
is needed to use this recursive definition.

Question 47

Pascals triangle :

Answer 47

Pascal’s identity shows that when two adjacent binomial coefficients in this triangle
are added, the binomial coefficient in the next row between these two coefficients is produced.

The nth row consists of binomial coefficients of C( n,k ), k = 0,1,….,n.

Question 48

VANDERMONDE’S IDENTITY

and its proof:

Answer 48

Let m, n, and r be nonnegative integers with r not exceeding either m or n. Then

C( m+n , r ) = ∑ C ( m , r-k ).C( n , k )
for k going from 0 to r.

Well consider two sets one with m elements and ither with n.
LHS has union of these and make ur way forward, wink.

Question 49

COROLLARY 4:

from VANDERMONDE’s Identity :

and proof:

Answer 49

If n is a nonnegative integer, then

C( 2n, n) = ∑( C( n,k) ) ^2
for k going from 0 to n.

Vandermonde's identity m=r = n
and C (n,k) = C(n, n-k )

Question 50

We can prove combinatorial identities by counting bit strings with different properties, as the proof of Theorem 4 will demonstrate.

Proof:

Answer 50

Let n and r be nonnegative integers with r ≤ n. Then

C ( n+1, r+1 ) = ∑ C ( j, r)
j from r to n.

LHS = Bit string of n+1 length with r+1 1s.
We show that the RHS counts the same objects by considering the cases corresponding to the possible locations of the final 1 in a string with r + 1 ones. This final one must
occur at position r + 1, r + 2, … , or n + 1.
Furthermore, if the last one is the kth bit there must
be r ones among the first k − 1 positions. Consequently, there are
(k −1
r) such bit strings. Summing over k with r + 1 ≤ k ≤ n + 1, we find that there are
∑( k − 1 ,r ) = ∑ C ( j, r)
k runs from r+1 to n+1 and j runs from r to n
bit strings of length n containing exactly r + 1 ones. (Note that the last step follows from the
change of variables j = k − 1.) Because the left-hand side and the right-hand side count the
same objects, they are equal. This completes the proof.

Question 51

Generating the Next Permutation in Lexicographic Order.

Theory only: not generation process in English, like pre requisites.

Answer 51

Any set with n elements can be placed in one-to-one correspondence with the set {1, 2, 3, … , n}.We can list the permutations of any set of n elements by generating the permutations of the n
smallest positive integers and then replacing these integers with the corresponding elements.
Many different algorithms have been developed to generate the n! permutations of this set.

This is based on lexicographic ordering of the
set of permutations of {1, 2, 3, … , n}.
In this ordering, the permutation a1a2 ⋯ an precedes the
permutation of b1b2 ⋯ bn, if for some k, with 1 ≤ k ≤ n, a1 = b1, a2 = b2, … , ak−1 = bk−1, and
ak < bk.

Question 52

Generating the Next Permutation in Lexicographic Order.

Generation process theory not genralised, but process details and jist.

Answer 52

An algorithm for generating the permutations of {1, 2, … , n} can be based on a procedure that constructs the next permutation in lexicographic order following a given permutation
a1a2 ⋯ an.

First, suppose that an−1 < an. Interchange an−1
and an to obtain a larger permutation. No other permutation is both larger than the original permutation and smaller than the permutation obtained by interchanging an−1 and an.
if an−1 > an then larger permutatn can’t be obtained by interchanging them.

If an−2 < an−1, then the last three integers in the
permutation can be rearranged to obtain the next largest permutation. Put the smaller of the two
integers an−1 and an that is greater than an−2 in position n − 2. Then, place the remaining integer
and an−2 into the last two positions in increasing order.

if an−2 > an−1 (and an−1 > an) then again permuting last 3 ints won’t give a larger permutatn.

Question 53

Generating the Next Permutation in Lexicographic Order.

Generalized :

Answer 53

A general method can be described for producing the next larger permutation in increasing order
following a given permutation a1a2 ⋯ an. First, find the integers aj and aj+1 with aj < aj+1 and
aj+1 > aj+2 > ⋯ > an,
that is, the last pair of adjacent integers in the permutation where the first integer in the pair
is smaller than the second.

Then, the next larger permutation in lexicographic order is obtained by putting in the jth position the least integer among aj+1, aj+2, … , and an that is greater
than aj and listing in increasing order the rest of the integers aj
, aj+1, … , an in positions j + 1 to
n.

It is easy to see that there is no other permutation larger than the permutation a1a2 ⋯ an but
smaller than the new permutation produced. (The verification of this fact is left as an exercise
for the reader.)

To produce the n! permutations of the integers 1, 2, 3, … , n, begin with the smallest permutation in lexicographic order, namely, 123 ⋯ n, and successively apply the procedure described
for producing the next larger permutation of n! − 1 times. This yields all the permutations of
the n smallest integers in lexicographic order.

Question 54

ALGORITHM 1 Generating the Next Permutation in Lexicographic Order

Algorithm 1 displays the procedure for finding the next permutation in lexicographic order
after a permutation that is not n n − 1 n − 2 … 2 1, which is the largest permutation.

Answer 54

procedure next permutation(a1a2 … an: permutation of
{1, 2, … , n} not equal to n n − 1 … 2 1)
j := n − 1
while aj > aj+1
    j := j − 1
{j is the largest subscript with aj < aj+1}
k := n
while aj > ak
   k := k − 1
{ak is the smallest integer greater than aj to the right of aj
}
interchange aj and ak
r := n
s := j + 1
while r > s
    interchange ar and as
    r := r − 1
    s := s + 1
{this puts the tail end of the permutation after the jth position in increasing order}
{a1a2 … an is now the next permutation}

Question 55

Generating Combinations

Pre req for generating combination, what is step before that :

Answer 55

How can we generate all the combinations of the elements of a finite set? Because a combination is just a subset, we can use the correspondence between subsets of {a1, a2,… , an} and bit strings
of length n.
Recall that the bit string corresponding to a subset has a 1 in position k if ak is in the subset,
or 0 if ak absent. If all the bit strings of length n can be listed,
then by the correspondence between subsets and bit strings, a list of all the subsets is obtained.
Recall that a bit string of length n is also the binary expansion of an integer between 0 and
(2^n) − 1. The 2^n bit strings can be listed in order of their increasing size as integers in their binary
expansions. To produce all binary expansions of length n, start with the bit string with
n zeros. Then, successively find the next expansion until the bit string 111 … 11 is obtained.
At each stage the next binary expansion is found by locating the first position from the right that is
not a 1, then changing all the 1s to the right of this position to 0s and making this first 0 (from
the right) a 1.

Question 56

ALGORITHM 2 Generating the Next Larger Bit String.

Answer 56

procedure next bit string(bn−1 bn−2…b1b0: bit string not equal to 11…11)
i := 0
while bi = 1
bi := 0
i := i + 1
bi := 1
{bn−1 bn−2…b1b0 is now the next bit string}

Question 57

Next, an algorithm for generating the r-combinations of the set {1, 2, 3, … , n} , logic for it:

Answer 57

An r-combination can be represented by a sequence containing the elements in the
subset in increasing order. The r-combinations can be listed using lexicographic order on
these sequences.

In this lexicographic ordering, the first r-combination is {1, 2, … , r − 1, r}
and the last r-combination is {n − r + 1, n − r + 2, … , n − 1, n}.

The next r-combination
after a1a2 ⋯ ar can be obtained in the following way: First, locate the last element ai in
the sequence such that ai ≠ n − r + i. Then, replace ai with ai + 1 and aj with ai + j − i + 1,
for j = i + 1, i + 2, … , r. It is left for the reader to show that this produces the next larger
r-combination in lexicographic order

Question 58

ALGORITHM 3 Generating the Next r-Combination in Lexicographic Order.

Answer 58

procedure next r-combination({a1, a2,… , ar}: proper subset of
{1, 2, … , n} not equal to {n − r + 1, … , n} with
a1 < a2 < ⋯ < ar)
i := r
while ai = n − r + i
i := i − 1
ai := ai + 1
for j := i + 1 to r
aj := ai + j − i
{{a1, a2,… , ar} is now the next combination}

Question 59

strictly increasing

Answer 59

A sequence is called strictly increasing if each term is larger than the one that precedes it,

Question 60

strictly decreasing

Answer 60

A sequence is called strictly decreasing if each term is smaller than the one that
precedes it.