<<DiscreteMath`Combinatorica`

Off[General::"spell1"]

Problem 19

Clear[wa, n];

    
wa[0] = 1; wa[1] = 2; wa[2] = 4; wa[3] = 8; 
    wa[4] = 16;

wa[n_] := wa[n] = 2*wa[n - 1] + wa[n - 5]

Table[wa[k], {k, 1, 10}]

Problem 22

{{1, 3}, {1, 2, 3}}

{{1, 4}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}}

{{1, 5}, {1, 2, 5}, {1, 3, 5}, {1, 2, 3, 5}, {1, 4, 5}, {1, 2, 4, 
        5}, {1, 3, 4, 5}, {1, 2, 3, 4, 5}}

{{1, 6}, {1, 2, 6}, {1, 3, 6}, {1, 2, 3, 6}, {1, 4, 6}, {1, 2, 4, 
        6}, {1, 3, 4, 6}, {1, 2, 3, 4, 6}, {1, 5, 6}, {1, 2, 5, 6}, {1, 3, 5, 
        6}, {1, 2, 3, 5, 6}, {1, 4, 5, 6}, {1, 2, 4, 5, 6}, {1, 3, 4, 5, 
        6}, {1, 2, 3, 4, 5, 6}}

This can be explained by bit strings of length n - 2. The positions belong to the numbers 2,  ... , n - 1. 1-s will tell you which numbers to include in the sequence.

Clear[ns, n];

    
ns[2] = 1; ns[3] = 2; ns[n_] := ns[n] = 2 ns[n - 1]

Table[ns[k], {k, 2, 10}]

Problem 23

The problem is to find a recurrence realtion for the number of bit strings of length n which contain at least one occurence of the string 00.

Mathematica can select all such bit strings.

Select[Strings[{0, 1}, 3], 
      MemberQ[Partition[#, 2, 1], {0, 0}] &]

Select[Strings[{0, 1}, 4], 
      MemberQ[Partition[#, 2, 1], {0, 0}] &]

Length[
      Select[Strings[{0, 1}, 4], 
        MemberQ[Partition[#, 2, 1], {0, 0}] &]]

Table[
      Length[Select[Strings[{0, 1}, k], 
          MemberQ[Partition[#, 2, 1], {0, 0}] &]], {k, 1, 15}]

Let n ≥ 3.  Denote by S the set of all bit strings of length n which contain at least one occurence of the string 00.  The set S is a disjoint union of three sets: the set (Subscript[S, 00]), the set (Subscript[S, 10]), and the set (Subscript[S, 1]). The set (Subscript[S, 00]) is the set of all bit strings in S which end with 00, The set (Subscript[S, 10]) is the set of all bit strings in S which end with 10 and the set (Subscript[S, 1]) is the set of all bit strings in S which end with 1. The cardinality of  (Subscript[S, 00]) is (2^(n - 2)), the cardinality of  (Subscript[S, 10]) is (Subscript[a, n - 2]), the cardinality of  (Subscript[S, 1]) is (Subscript[a, n - 1]).

The corresponding recursion is

Clear[rs23];  rs23[0] = 0;  rs23[1] = 0;
rs23[n_] := rs23[n] = 
        (2^(n - 2)) + rs23[n - 1] + rs23[n - 2]

The logic here is that (2^(n - 2)) strings end with  00,  rs[n-2] strings end with 10 and  rs[n-1] strings end with 1.

Table[rs23[k], {k, 0, 18}]

A closed form using the Fibonacci numbers:

Table[2^k - Fibonacci[k + 2], {k, 0, 18}]

Problem 24

The problem is to find a recurrence realtion for the number of bit strings of length n which contain at least one occurences of the string 000.

Mathematica can select all such strings.

Select[Strings[{0, 1}, 4], 
      MemberQ[Partition[#, 3, 1], {0, 0, 0}] &]

Length[
      Select[Strings[{0, 1}, 4], 
        MemberQ[Partition[#, 3, 1], {0, 0, 0}] &]]

Select[Strings[{0, 1}, 5], 
      MemberQ[Partition[#, 3, 1], {0, 0, 0}] &]

Length[
      Select[Strings[{0, 1}, 5], 
        MemberQ[Partition[#, 3, 1], {0, 0, 0}] &]]

Table[
      Length[Select[Strings[{0, 1}, k], 
          MemberQ[Partition[#, 3, 1], {0, 0, 0}] &]], {k, 1, 16}]

Let n ≥ 3.  Denote by S the set of all bit strings of length n which contain at least one occurence of the string 000.  The set S is a disjoint union of four sets: the set (Subscript[S, 000]), the set (Subscript[S, 100]), the set (Subscript[S, 10])  and the set (Subscript[S, 1]). The set (Subscript[S, 000]) is the set of all bit strings in S which end with 000, The set (Subscript[S, 100]) is the set of all bit strings in S which end with 100, the set (Subscript[S, 10]) is the set of all bit strings in S which end with 10, the set (Subscript[S, 1]) is the set of all bit strings in S which end with 1. The cardinality of  (Subscript[S, 000]) is (2^(n - 3)), the cardinality of  (Subscript[S, 100]) is (Subscript[a, n - 3]), the cardinality of  (Subscript[S, 10]) is (Subscript[a, n - 2]), the cardinality of  (Subscript[S, 1]) is (Subscript[a, n - 1]).

The corresponding recursion is

Clear[rs24];  rs24[0] = 0;  rs24[1] = 0;  
    rs24[2] = 0;
rs24[n_] := rs24[n] = 
        (2^(n - 3)) + rs24[n - 3] + rs24[n - 2] + rs24[n - 1]

Table[rs24[k], {k, 0, 19}]

Problem 25

The problem is to find a recurrence realtion for the number of bit strings of length n which do not contain any occurences of the string 000.

Mathematica can select all such strings.

Select[Strings[{0, 1}, 4], 
      Not[MemberQ[Partition[#, 3, 1], {0, 0, 0}]] &]

Length[
      Select[Strings[{0, 1}, 4], 
        Not[MemberQ[Partition[#, 3, 1], {0, 0, 0}]] &]]

Table[
      Length[Select[Strings[{0, 1}, k], 
          Not[MemberQ[Partition[#, 3, 1], {0, 0, 0}]] &]], {k, 0, 
        12}]

Let n ≥ 3.  Denote by S the set of all bit strings of length n which do not contain any occurences of the string 000.  The set S is a disjoint union of three sets: the set (Subscript[S, 100]), the set (Subscript[S, 10])  and the set (Subscript[S, 1]).  The set (Subscript[S, 100]) is the set of all bit strings in S which end with 100, the set (Subscript[S, 10]) is the set of all bit strings in S which end with 10, the set (Subscript[S, 1]) is the set of all bit strings in S which end with 1.  The cardinality of  (Subscript[S, 100]) is (Subscript[a, n - 3]), the cardinality of  (Subscript[S, 10]) is (Subscript[a, n - 2]), the cardinality of  (Subscript[S, 1]) is (Subscript[a, n - 1]).

The corresponding recursion is

Clear[rs25];  rs25[0] = 1;  rs25[1] = 2;  
    rs25[2] = 4;
rs25[n_] := rs25[n] = 
        rs25[n - 3] + rs25[n - 2] + rs25[n - 1]

The logic here is that rs[n-3] strings end with 100, rs[n-2] strings end with 10 and  rs[n-1] strings end with 1.

Table[rs25[k], {k, 0, 22}]

Problem 26

The problem is to find a recurrence realtion for the number of bit strings of length n which contain at least one occurence of the string 01.

Easily we calculate (Subscript[a, 0]) = 0,  (Subscript[a, 1]) = 0,  (Subscript[a, 2]) = 1,  (Subscript[a, 3]) = 4. Below is the Mathematica code confirming these calculations and calculating more values.

Select[Strings[{0, 1}, 4], 
      MemberQ[Partition[#, 2, 1], {0, 1}] &]

Length[
      Select[Strings[{0, 1}, 4], 
        MemberQ[Partition[#, 2, 1], {0, 1}] &]]

Table[
      Length[Select[Strings[{0, 1}, k], 
          MemberQ[Partition[#, 2, 1], {0, 1}] &]], {k, 1, 8}]

Now reasoning which leads to the recursion.

Reasoning I.

Let n ≥ 2.  Denote by S the set of all bit strings of length n which contain at least one occurence of the string 01.  The set S is a disjoint union of two sets: the set (Subscript[S, f])  and the set (Subscript[S, l]).  The set (Subscript[S, f]) is the set of all bit strings of length n  in which the first occurence of 01 is at the position k  where k ≤ n - 2.  (Here we mean that the bit 0 in 01 is at the position k.)  The set (Subscript[S, l]) is the set of all bit strings of length n  in which the first occurence of 01 is at the position n - 1, that is 0 is at the position n - 1 and 1 is at the position n.

The cardinality of the set (Subscript[S, f]) is 2  (Subscript[a, n - 1]). To justify this claim, observe that each string in (Subscript[S, f]) is obtained by appending 0 or 1 at the end of  a bit strings of length n - 1 which contain at least one occurence of the string 01.

The cardinality of the set (Subscript[S, l]) is n - 1.  The justification for this claim is as follows. If the first occurence of 01 is at the last two bits, then the first n - 2 positions do not include any 01 strings.  There are n - 1 such bit strings: all n - 2 bits are 0, 1-s up to k, then zeros, k = 1,  ... , n - 3, all n - 2 bits are 1.

The recursion corresponding to this disjoint union is

Clear[rs26a, n];
rs26a[0] = 0; 
    rs26a[n_] := rs26a[n] = 2  rs26a[n - 1] + n - 1

Table[rs26a[k], {k, 0, 18}]

We will present a different reasoning that leads to the same recursion.

Let n ≥ 2.  Denote by S the set of all bit strings of length n which contain at least one occurence of the string 01.  The set S is a disjoint union of two sets: the set (Subscript[S, 0])  and the set (Subscript[S, 1]).  The set (Subscript[S, 0]) is the set of all bit strings S which end with 0. The set (Subscript[S, 1]) is the set of all bit strings in S which end with 1.

The cardinality of the set (Subscript[S, 0]) is (Subscript[a, n - 1]).  To justify this claim, observe that each string in (Subscript[S, 0]) is obtained by appending 0 at the end of  a bit strings of length n - 1 which contain at least one occurence of the string 01.

The cardinality of the set (Subscript[S, 1]) is a little more complicated. There are two kinds of bit strings in (Subscript[S, 1]).  The first kind are bit strings which are obtained by appending 1 at the end of  a bit strings of length n - 1 which contain at least one occurence of the string 01. There are (Subscript[a, n - 1]) bitstrings of this kind. The second kind are bit strings that end with 01 but do not contain the string 01 otherwise. There are n - 1 strings like that. They are  00...01, 100..01, and so on to, 11...101; counting 0s they can have n - 1 zeros, n - 2 zeros, up to only 1 zero.

The recursion corresponding to this disjoint union is the same as one defined in rs26a.

Reasoning II.

Let n ≥ 2.  Denote by S the set of all bit strings of length n which contain at least one occurence of the string 01.  The set S is a disjoint union of three sets the set (Subscript[S, 0]), the set (Subscript[S, 01]) and the set (Subscript[S, 11]).  The set (Subscript[S, 0]) is the set of all bit strings in S which end with 0.  These bit strings are all obtained by appending 0 to bit strings of length n - 1 which contain at least one occurence of the string 01.  There are exactly (Subscript[a, n - 1]) such strings.  The set (Subscript[S, 01]) is the set of all bit strings of length n  which end by 01. There are exactly (2^(n - 2)) such bit strings.  The set (Subscript[S, 11]) is the set of all bit strings of length n  which end by 11. These bit strings are all obtained by appending 1 to bit strings of length n - 1 which contain at least one occurence of the string 01 and which end by 1. Since there are (Subscript[a, n - 2]) bit strings of length n - 1 which contain at least one occurence of the string 01 and which end by 0,  there are exactly (Subscript[a, n - 1]) - (Subscript[a, n - 2]) bit strings of length n - 1 which contain at least one occurence of the string 01 and which end by 1.

The recursion corresponding to this disjoint union is

Clear[rs26b];  rs26b[0] = 0;  
    rs26b[1] = 0; 
rs26b[n_] := rs26b[n] = 
        rs26b[n - 1] + (2^(n - 2)) + rs26b[n - 1] - 
          rs26b[n - 2]

Table[rs26b[k], {k, 0, 18}]

Closed form for the sequence

Table[2^n - (n + 1), {n, 0, 18}]

Problem 27

Count the number of ways to climb  n  stairs if we can take either 1 or 2 stairs at the time.

For example 3 stairs:

{{1, 2}, {2, 1}, {1, 1, 1}}

or 4 stairs

{{1, 1, 2}, {2, 2}, {1, 2, 1}, {2, 1, 1}, {1, 1, 1, 1}}

Select[
      Flatten[Table[Strings[{1, 2}, k], {k, 1, 5}], 
        1], (Total[#] == 5) &]

Length[
      Select[Flatten[Table[Strings[{1, 2}, k], {k, 1, 5}], 
          1], (Total[#] == 5) &]]

Table[
      Length[Select[
          Flatten[Table[Strings[{1, 2}, k], {k, 1, n}], 
            1], (Total[#] == n) &]], {n, 1, 12}]

Clear[rs27]; rs27[1] = 1;  rs27[2] = 2;
rs27[n_] := rs27[n] = rs27[n - 1] + rs27[n - 2]

Table[rs27[k], {k, 1, 12}]

Problem 28

Select[
      Flatten[Table[Strings[{1, 2, 3}, k], {k, 1, 4}], 
        1], (Total[#] == 4) &]

Select[
      Flatten[Table[Strings[{1, 2, 3}, k], {k, 1, 5}], 
        1], (Total[#] == 5) &]

Length[
      Select[Flatten[Table[Strings[{1, 2, 3}, k], {k, 1, 5}], 
          1], (Total[#] == 5) &]]

Table[
      Length[Select[
          Flatten[Table[Strings[{1, 2, 3}, k], {k, 1, n}], 
            1], (Total[#] == n) &]], {n, 1, 12}]

Clear[rs28]; rs28[1] = 1;  rs28[2] = 2; 
    rs28[3] = 4;
rs28[n_] := rs28[n] = 
        rs28[n - 1] + rs28[n - 2] + rs28[n - 3]

Table[rs28[k], {k, 1, 12}]

29

a0 = 1; a1 = 3; a2 = 8;

{{}, {0}, {1}, {2}}

Length[{{1, 0}, {2, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 2}, {2, 1}, {2, 
          2}}]

Split the set of all ternary strings of length n with no consecutive 0s into disjoint subsets: beginning with 1, begining with 2 and beginning with 0. How many of each?

Clear[ts]; ts[0] = 1; ts[1] = 3; 
    ts[n_] := ts[n] = 2*ts[n - 1] + 2*ts[n - 2]

Table[ts[k], {k, 1, 10}]