DisMat UE 03

ex3-0.pdf
Diskrete_Mathematik_UE_03-0.pdf

3.1

Let $a$ and $b$ be positive integers. Find the number of strings s consisting 0’s and 1’s such that

1. the number of 0’s is $a$ and the number of 1’s is $b$,

2. the string $s$ does not contain two consecutive 0’s.
   For instance, for $a=b=2$, there are 3 allowed strings: $0101$, $0110$, and $1010$

fn main() {  
	run(1, 1);  
	run(1, 2);  
	run(1, 3);  
	run(1, 4);  
	run(1, 5);  
	run(1, 6);  
	  
	run(2, 1);  
	run(2, 2);  
	run(2, 3);  
	run(2, 4);  
	run(2, 5);  
	run(2, 6);  
	  
	run(3, 1);  
	run(3, 2);  
	run(3, 3);  
	run(3, 4);  
	run(3, 5);  
	run(3, 6);  
}  
  
fn run(a: u32, b: u32) {  
	println!("\na = {a}, b = {b}");  
	run_inner("", 0, 0, a, b);  
}  
  
fn run_inner(s: &str, a: u32, b: u32, max_a: u32, max_b: u32) {  
	if a == max_a && b == max_b {  
		println!("{s}");  
		return  
	}  
	  
	if a < max_a {  
		let last = s.chars().last();  
		if last.is_none() || last.unwrap() != '0' {  
			run_inner(&format!("{s}0"), a + 1, b, max_a, max_b);  
		}  
	}  
	  
	if b < max_b {  
		run_inner(&format!("{s}1"), a, b + 1, max_a, max_b);  
	}  
}  

If $a>(b+1)\to 0$

<0>1<0>1<0>1<0>1<0>  

⇒ $b+1$ gaps
⇒ choose $a$ of these gaps

\begin{array}{ll} 0 & a \leq b+1 \\ \binom{b+1}{a} & \, \textrm{sonst} \\ \end{array} \right. $$ ## 3.2 Have to proof Sterling Numbers to use the Formular ## 3.3 Given a positive integer $n$ and a prime number $p$, give a formula for the number of those $0 ≤ k ≤ n$, for which $\binom{n}{k}$ is not divisible by $p$, and prove it. in base $p$ expansion $\exists \; r \in \mathbb{N}$ such that

n = n_{r} \cdot p^{r} + … + n_{1} \cdot p^{1} + n_{0} \cdot p^{0} ; ; ; 0 \leq n_{i} \leq p - 1

hence define $k$ as

k := k_{r} \cdot p^{r} + … + k_{1} \cdot p^{1} + k_{0} \cdot p^{0} ; ; ; 0 \leq k_{i} \leq p - 1

$$FromLuc{a}^{\prime }sTheorem$$

\binom{n}{k} \mod p = 0 \Rightarrow \prod_{i=0}^{r} \binom{n_{i}}{k_{i}} \mod p = 0

\binom{n_{i}}{k_{i}} \mod p \neq 0

only if $k_{i} \leq n_{i}$ because if any $k_{i} > n_{i} \Rightarrow \binom{n_{i}}{k_{i}} = 0 \Rightarrow \binom{n}{k} = 0$ $k_i​$ can be any value from $0$ up to $n_i$​ => $n_{i} + 1$

\prod_{i=0}^{r}(n_{i} + 1)