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
posted by Jeroen van de Graaf @ Friday, November 30, 2007
