Chapter A and B from "Combinatorics, a problem-oriented approach"

CHAPTER A

Standard Problem 1:

Find the number of strings of a given length k
using n distinct symbols

Ans: n**k


Find the number of strings of a given length k
using n distinct symbols, if no repetition is allowed.

Ans: n*(n-1)...(n-k+1)

###################
Permutations

###################

Rearrangement: any orderdering including the original 1

Derangement: rearrengement which leaves no element in
it original position.





CHAPTER B

DEFINITION:
combination = list of elements (symbols) in which the order is not taken into account

Standard Problem 3:

Find the number of combinations of a given length k consisting
of distinct symbols from a set of size n.

Ans: BinCoeff(n, k) since
- Distinct ==> n * (n-1) ... (n-k+1)
- Order not taken into account ==> k! strings represent
the same combination, so divide by k!.

####################

Pascal's triangle etc

The commutative property makes
BA equivalent to AB etc etc.

There must be a link to the change-problem here.

####################
B15:
Rearrange 3 As and 7 Bs such that no two consecutive A repeat.

Solution: start with BBBBBBBB and observe that the 3 As
can be put in 8 different places: 8*7*6 / 3*2*1

==>
Standard Problem 4

Find the number bitstrings with
m 0s and n 1s such that there are no consecutive 1s.

Ans:
BinCoeff(m+1, n)

####################
Find all k=5-digit combinations from the set {1,2,3}, #{}=n=3
with at least one symbol each.

Put them in lexicographical order and observe where
the < can be placed:

111<2<3
11<22<3
11<2<33
1<222<3
1<22<33
1<2<333

BinCoeff(4,2) = 6

==>
Standard Problem 5

Find the number of combinations of a given length k
using symbols from a given set of size n, not
allowing missing symbols.

BinCoeff(k-1, n-1)

####################
B21
20 letter combinations of A, B and C with at least
1 A, 2 Bs and 3 Cs

A+ (< B)B+ (< CC)C+

Well, instead of putting two "<"
we can put one "< B" and one "< CC",
which can be done in (19-3)=16 choose 2
ways.
####################
Find all k=2-digit combinations from the set {1,2,3}, #{}=n=3
allowing missing elements.

Adding 123 it reduces to the previous case:
11+123=11123
22+123=12233
33+123=12333
12+123=11223
13+123=11233
23+123=12233

==>
Standard Problem 6

Find the number of combinations of a given length k
using symbols from a given set of size n, allowing
repetition and missing symbols.

Ans:
BinCoeff(k+n-1, n-1)

####################
A symbol A dominates consistently if for any
initial segment (prefix) A occurs at least
1/2 of the time.

B25
0000=0
0001=0
0010=0
0011=0
0100=0
0101=0
0110=x
0111=x

B26
A-dominates sequences of 3 As and 3 Bs:
000111
001110x
001101
001011
010011
010101
so 5 are 0-dominated
and 20-5 = 15 are not.

There is a one-to-one correspondence with
with all sequences of length 6 including 4 As
and 2 Bs:

For each rearrangement of AAAABB:
- find the smallest initial segment
in which A outnumbers B
- flip the symbols in that segment

A-AAABB --> B-AAABB
BAA-AAB --> ABB-AAB
B27
BBAAA-A --> AABBB-A
ABA-ABA --> BAB-ABA

ABB-BAA < - BAA-BAA
ABABB-A < - BABAA-A

Why is this 1-to-1???

==>
Standard Problem 7

Find the number of 0-dominated bitstrings with
m 0s and n 1s.

Ans: BinCoeff(m+n, m) - BinCoeff(m+n, m+1)



B29