of n items, where order is not important, but repetition
is allowed. For example, there are 10 ways to multichoose two objects from the set A, B, C, and D,
namely: AB, AC, AD, BC, BD, CD, and AA, BB, CC,
and DD. Thus
. One can show that a multichoose coefficient equals an ordinary combinatorial coefficient:
combinatorial coefficient See COMBINATION.
combinatorics (combinatorial analysis) The branch
of mathematics concerned with the theory and practices of counting elements of sets and the construction
of specified arrangements of objects, along with the
study of COMBINATIONs and PERMUTATIONs, is called
combinatorics. GRAPH THEORY is also regarded as an
aspect of combinatorics.
The technique of “double counting,” that is, counting the same set of objects in two different ways, is a
common practice in combinatorics used to yield interesting results. For example, counting the dots in an n × n
square array along diagonals as opposed to across the
rows gives the surprising formula:
1 + 2 + 3 + … + (n – 1) + n + (n – 1) + … + 3 + 2 + 1 = n
2
Counting the number of subsets of a set of n elements, either by summing the number of subsets containing, in turn, 0, 1, 2, up to n elements, or by noting
that each subset is decided by making n choices
between two options—whether or not each element in
turn is to be in the subset—yields the formula:
EULER’S THEOREM can be considered a result in combinatorial geometry.
See also DISCRETE; FIGURATE NUMBERS.
commensurable Two quantities having a common
measure, meaning that they can be measured in terms of
whole numbers of a common unit, are said to be commensurable. For example, the quantities one month and
one week are commensurable because they can both be
measured in terms of a whole number of days. In GEOMETRY, two line segments are said to be commensurable if
there is another segment whose measure goes evenly,
without remainder, into the measures of each segment.
For instance, segments of lengths 20 and 12 in. are commensurable for they can each be evenly divided into
lengths of 1 (or 2 or 4) in. In general, two segments of
lengths a and b units are commensurable if the ratio a/b
is a RATIONAL NUMBER. As √
–
2 is irrational, segments of
length 1 and √
–
2 (respectively, the side-length and the
diagonal of a unit square) are incommensurable.
A study of the EUCLIDEAN ALGORITHM shows that
if given two commensurable line segments of lengths a
and b, say, then repeatedly subtracting the shorter
length from the longer to produce a new pair of lengths
eventually produces two line segments equal in length.
This final shared measure is the largest length that
divides evenly into the two original segments. (If a and
b are whole-number measurements, then the length of
the final measure is the GREATEST COMMON DIVISOR of
a and b.) If, on the other hand, one can demonstrate
that the process of repeatedly erasing the shorter line
segment from the longer will continue indefinitely
without ever producing two line segments equal in
length, then the original two segments cannot be commensurable. Around 425 B.C.E. Greek mathematician
THEODORUS OF CYRENE used precisely this observation to prove the irrationality of √
–
2.
In NUMBER THEORY, two real numbers a and b are
said to be commensurable if their ratio is rational. For
instance, the numbers √
–
48 and √
–
3/2 are commensurable. No one to this day knows whether or not π and
e are commensurable. The numbers log 5 (3) and log 5 (7)
are incommensurable. (If
for some whole
numbers p and q, then 7
q = 3
p
, which is absurd since
every power of 7 is 1 more than a multiple of 3.)
common denominator Two or more fractions are
said to have a common denominator if the denominator of each fraction is the same. For example, the
fractions
and
have a common denominator of
12. It is a straightforward matter to add and subtract
3
12
5
12
log
log
5
5
7
3
=
p
q
n
n
n
n
n
n
0
1
2
2 2
2 2
+
+
+ +
= × × × =
...
L
n
k
n k
k
=
+ −
1
4
2
10
=
82 combinatorial coefficient
is allowed. For example, there are 10 ways to multichoose two objects from the set A, B, C, and D,
namely: AB, AC, AD, BC, BD, CD, and AA, BB, CC,
and DD. Thus
. One can show that a multichoose coefficient equals an ordinary combinatorial coefficient:
combinatorial coefficient See COMBINATION.
combinatorics (combinatorial analysis) The branch
of mathematics concerned with the theory and practices of counting elements of sets and the construction
of specified arrangements of objects, along with the
study of COMBINATIONs and PERMUTATIONs, is called
combinatorics. GRAPH THEORY is also regarded as an
aspect of combinatorics.
The technique of “double counting,” that is, counting the same set of objects in two different ways, is a
common practice in combinatorics used to yield interesting results. For example, counting the dots in an n × n
square array along diagonals as opposed to across the
rows gives the surprising formula:
1 + 2 + 3 + … + (n – 1) + n + (n – 1) + … + 3 + 2 + 1 = n
2
Counting the number of subsets of a set of n elements, either by summing the number of subsets containing, in turn, 0, 1, 2, up to n elements, or by noting
that each subset is decided by making n choices
between two options—whether or not each element in
turn is to be in the subset—yields the formula:
EULER’S THEOREM can be considered a result in combinatorial geometry.
See also DISCRETE; FIGURATE NUMBERS.
commensurable Two quantities having a common
measure, meaning that they can be measured in terms of
whole numbers of a common unit, are said to be commensurable. For example, the quantities one month and
one week are commensurable because they can both be
measured in terms of a whole number of days. In GEOMETRY, two line segments are said to be commensurable if
there is another segment whose measure goes evenly,
without remainder, into the measures of each segment.
For instance, segments of lengths 20 and 12 in. are commensurable for they can each be evenly divided into
lengths of 1 (or 2 or 4) in. In general, two segments of
lengths a and b units are commensurable if the ratio a/b
is a RATIONAL NUMBER. As √
–
2 is irrational, segments of
length 1 and √
–
2 (respectively, the side-length and the
diagonal of a unit square) are incommensurable.
A study of the EUCLIDEAN ALGORITHM shows that
if given two commensurable line segments of lengths a
and b, say, then repeatedly subtracting the shorter
length from the longer to produce a new pair of lengths
eventually produces two line segments equal in length.
This final shared measure is the largest length that
divides evenly into the two original segments. (If a and
b are whole-number measurements, then the length of
the final measure is the GREATEST COMMON DIVISOR of
a and b.) If, on the other hand, one can demonstrate
that the process of repeatedly erasing the shorter line
segment from the longer will continue indefinitely
without ever producing two line segments equal in
length, then the original two segments cannot be commensurable. Around 425 B.C.E. Greek mathematician
THEODORUS OF CYRENE used precisely this observation to prove the irrationality of √
–
2.
In NUMBER THEORY, two real numbers a and b are
said to be commensurable if their ratio is rational. For
instance, the numbers √
–
48 and √
–
3/2 are commensurable. No one to this day knows whether or not π and
e are commensurable. The numbers log 5 (3) and log 5 (7)
are incommensurable. (If
for some whole
numbers p and q, then 7
q = 3
p
, which is absurd since
every power of 7 is 1 more than a multiple of 3.)
common denominator Two or more fractions are
said to have a common denominator if the denominator of each fraction is the same. For example, the
fractions
and
have a common denominator of
12. It is a straightforward matter to add and subtract
3
12
5
12
log
log
5
5
7
3
=
p
q
n
n
n
n
n
n
0
1
2
2 2
2 2
+
+
+ +
= × × × =
...
L
n
k
n k
k
=
+ −
1
4
2
10
=
82 combinatorial coefficient