Need responses for a,b, and c. Let Ln,k denote the number of ordered k-lists wit

Question

Need responses for a,b, and c.

Let Ln,k denote the number of ordered k-lists without repetition that can be formed from n. For example, L3,2 = 6, because it counts the lists 1,2; 1,3; 2,1; 2,3; 3,1; and 3,2. We have already used the Rule of Product to show that Ln,k = (n)k (a) What happens (or should happen) to (71)* when k is zero? When n is zero? What if k > n? Do these boundary cases give reasonable values for (b) Following the Stirling-numbers example in class, find a recursive formula giving Ln,k in terms of and For what values of 11 and k is your recursion valid? (c) What are the initial conditions for a recursive definition of Ln,k? Justify your answer.

Explanation / Answer

a) when k = 0, we have 1 list.

However, when n = 0, we have 0 list.

If k>n, again we have 0 list as it is impossible.

Yes, these are the boundary cases and they do give reasonable values for L_n,k .

b)

( I do not know which Sturling numbers example you are talking of.)

L_n,k = L_n-1,k + L_n-1, k-1

This recursion is valid for all n and k such that

n >= 1

k >= 1

n > k

c) The initial condition is

L_0,0 = 0 and

L_1,0 = 1

these are the initial conditions because the recursive statement reduces to the minimum value of n and k which in this case

are n-1 and k-1 respectively.

since we saw in (a) that for

n = non zero, k = 0 : 1 list

n = zero, k = zero : 0 list

hence

these are the boundary conditions.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.