Stanford Math Circle 78 grade
Counting
November 2022
3
26
Let
S
be a set with
n
elements. In how many different ways can one select two not necessarily
distinct subsets of
S
so that the union of the two subsets is
S
?
The order of selection does not
matter; for example, the pair of subsets
{
a
,
c
}
,
{
b
,
c
,
d
,
e
,
f
}
represents the same selection as the pair
{
b
,
c
,
d
,
e
,
f
}
,
{
a
,
c
}
.
27
(USAMO 72) A random number generator randomly generates the integers 1
,
2
,...,
9 with equal
probability. Find the probability that after
n
numbers are generated, the product is a multiple of 10.
28
Let
a
1
,
a
2
,...,
a
n
be an ordered sequence of
n
distinct objects. A
derangement
of this sequence
is a permutation that leaves no object in its original place. For example, if the original sequence
is 1
,
2
,
3
,
4, then 2
,
4
,
3
,
1 is not a derangement, but 2
,
1
,
4
,
3 is. Let
D
n
denote the number of an
n
element sequence. Show that
D
n
=
n
!
✓
1

1
1!
+
1
2!

···
+(

1
)
n
1
n
!
◆
.
29
How many nonnegative integer solutions are there to
a
+
b
+
c
+
d
=
17, provided that
d
12?
30
Use a combinatorial argument to show that for all positive integers
n
,
m
,
k
with
n
and
m
greater than
or equal to
k
,
k
Â
j
=
0
✓
n
j
◆✓
m
k

j
◆
=
✓
n
+
m
k
◆
.
This is known as the
Vandermonde Convolution Formula
.
31
Decide whether there exist 10,000 tendigit numbers divisible by seven, all of which can be obtained
from one another by a reordering of their digits.
7.
11.13=1001
0000000*05
→
1000000005
2334509881