Subsets Without Consecutive Integers

Solution

The total number of subsets of { $1,2,3, \ldots, 14$ } which contains no consecutive integers $= (14+2)^{\text{th}} = (16)^{\text{th}}$ Fibonacci number $= \boxed{987}$ .

Generalisation

Let $S(n)$ be a function to generate the number of subsets of { $1,2, \dots, n$ } which contains no pair of consecutive integers. First, split $S(n)$ into $2$ separate groups: one that contains the number $n$ and the other that doesn't.

• The group that does not contain $n$ is $S(n-1)$ because it doesn't contain $n$ .

• The group that does contain $n$ is $S(n-2)$ because it doesn't contain $n-1$ (hence minus $1$ from $n$ ) and must contain $n$ (here, minus $1$ from $n-1 = n-2$ because $n$ is fixed and the number of subsets in this group is simply $S(n-2)$ .

From these, we can infer that $S(n) = S(n-1) + S(n-2)$ . Thus, the function $S$ is recurring. And it looks just like the Fibonacci sequences! However, $S(1) = 2$ ( $1$ 0-subset and $1$ 1- subset) and $S(2) = 3$ ; whereas the Fibonacci sequences begin with $f(1) = 1, f (2) = 1, f(3) = 2, f(4) = 3$ . Notice here that the $S$ function is $2$ values behind the Fibonacci sequence. As such, we can conclude that $S(n) = f(n+2)$ .

Note: I have referred to this link when writing this solution.

In general, there are $\binom{n + k - 1}{k}$ ways to select a subset of size $k$ from the set $\{ 1, 2, 3, ..., n \}$ of size $n$ , given that there is no pair of consecutive elements in this subset.

This formula can be reached by the following logic: From the set, we wish to have elements that "divide" the $k$ elements we will choose. Thus, there are $n - k$ elements that can serve as "dividers." From these $n - k$ dividers, there are $n - k + 1$ slots that we can insert the $k$ elements, so in total, there are $\binom{n + k - 1}{k}$ ways to select $k$ non-consecutive elements from a set of size $n$ .

We count the number of sets of size 1, size 2, and so on until size 7. (The biggest subset has 7 elements because it contains exactly half the elements of the set.)

The answer is thus $\binom{14 - 0 + 1}{0} + \binom{14 - 1 + 1}{1} + \binom{14 - 2 + 1}{2} + \cdots + \binom{14 - 7 + 1}{7}$ $= \binom{15}{0} + \binom{14}{1} + \binom{13}{2} + \binom{12}{3} + \cdots + \binom{8}{7}$ $= \boxed{987}$ .

We prove that $\{1, 2, ..., n\}$ has $f(n)$ subsets, $\forall n\in\mathbb N$ , where $f(1)=2,f(2)=3, f(k+2)=f(k)+f(k+1), \forall k\in\mathbb N, k\ge 1$ , by inducting on $n$ .

Base case: $n=1$ . So that we can choose $\emptyset, \{1\}$ . For $n=2, \emptyset, \{1\}, \{2\}$ is valid but not $\{1, 2\}$ .

Inductive step: let it to be true for some positive integer $k\ge 2$ . Then for selecting subset of $\{1,2,\ldots ,k+1\}$ , we have $f(k)$ choices to choose subsets not containing $k+1$ , since there are $f(k)$ choices to choose these subsets from set $\{1,2,\ldots ,k\}$ . For those subsets containing $k+1$ , notice that we cannot choose number $k$ since $k, k+1$ are consecutive. In this case, a subset $S$ containing $k+1$ is valid if and only $S=Q\cup \{k+1\}$ , where $Q$ is a subset of $\{1,2,\ldots ,k-1\}$ not containing consecutive integers. So there are $f(k-1)$ choices in this case. In total, the number of valid subsets is $f(k)+f(k-1)=f(k+1)$ as desired.

Now $f(1)=2,$ $f(2)=3,$ $f(3)=2+3=5,$ $f(4)=3+5=8,$ $f(5)=5+8=13,$ $f(6)=8+13=21,$ $f(7)=13+21=34,$ $f(8)=21+34=55,$ $f(9)=34+55=89,$ $f(10)=55+89=144,$ $f(11)=89+144=233,$ $f(12)=144+233=377,$ $f(13)=233+377=610,$ $f(14)=377+610=987$ . Hence the answer is $987$ for $n=14$ , as desired. Q.E.D.

We extend our analysis to a set containing the first $n$ natural numbers. Denote $P(n)$ to be the number of subsets of the set $\{1,2,3, \ldots, n\}$ containing no pair of consecutive integers. If $n=1$ , the solution is $\emptyset$ and $\{1\}$ , so $P(1)=2$ . If $n=2$ , $P(2)=3$ . Interestingly, it shows that $P(3)=5=3+2=P(2)+P(1)$ . We may have a hunch that $P(n)=P(n-1)+P(n-2)$ . However, we need to prove this. What follows is a logical proof. $P(n)$ is the sum of the number of subsets containing $n$ and those that do not. The first case is given by $P(n-2)$ (we append the number $n$ to each subset) since no subset shall contain the term $n-1$ . The second one is given by $P(n-1)$ . The two cases are obviously disjoint. Thus, the recursion relation is proved. $P(1)=2, P(2)=3, \ldots, P(12)=`377, P(13)=610$ and $P(14)=987$ .

Let f(n) define the number of subsets of the natural numbers 1 to n that do not contain consecutive numbers.

Writing out the subsets for n=1,2,3,4,5, reveals that: f(1)=2, f(2)=3, f(3)=5, f(4)=8, f(5)=13.

This suggests that the number of subsets is a Fibonacci number.

Let's prove this relationship.

Let us call the number of satisfying subsets found in the set of integers 1 to n, set A, and the number of subsets will be f(n). A is made up of two mutually exclusive groups: those which contain n (set B), and those which do not contain n (set C).

Set C (which does not contain n) is equivalent to the complete set for 1 to (n-1). So the number of members of set C is f(n-1).

Set B (which contains n), must be mutually exclusive to set C, and so it cannot contain (n-1); otherwise it would be the complete set A. Hence the consecutive integers (n-1) and n cannot be members of this group. That is, the number of members will be equivalent to f(n-2).

Therefore, Set A = Set B + Set C, implies that f(n)=f(n-1)+f(n-2).

However, looking at our test values, they are shifted by two fibonacci numbers, eg.

f(1) = F {3} f(2) = F {4} f(3) = F_{5}

and so on.

Thus the number of subsets in {1, 2, 3, 4, ... , n} that contain no pair of consecutive integers is F_{n+2}.

In this case f(14) = F_{16} = 987

Suppose a subset contains no pair of consecutive integers. By forming the pairs $(1,2),(3,4),\cdots,(13,14)$ and applying the Pigeonhole Principle, we see that such a subset contains at most $7$ elements. For each $0\leq i\leq 7$ , we count the number of such subsets with $i$ elements.

Let $S=\{s_1,s_2,\cdots,s_i\}$ be a subset without consecutives. Form an associated subset $T=\{s_1,s_2-1,s_3-2,\cdots,s_i-(i-1)\}$ . $T$ is a subset of the set $U=\{1,2,\cdots,15-i\}$ . Moreover, the association $S\to T$ is a bijection mapping size- $i$ nonconsecutive subsets of $\{1,\cdots,14\}$ onto size- $i$ subsets of $U$ .

There are ${15-i \choose i}$ subsets of the latter form. Thus, the total number of nonconsecutive subsets is $\sum_{i=0}^{i=7}{15-i\choose i}=987$ .

In the set {1,2,3,..., n}, there are two types of subsets: (1) those which contain n, and (2) those which do not contain n.

Let f(n) = number of subsets of {1,2,3,...,n} not containing consecutive numbers. For brevity, we call such subsets 'special'.

If a subset contains n, then it must not contain n-1. There are f(n-2) such subsets since for every special subset of {1,2,...,n-2} we can add n and still obtain a special subset. On the other hand, there are f(n-1) special subsets of {1,2,3,...,n-1} which do not contain n.

Hence, f(n) = f(n-1)+f(n-2) Note that the special subsets of {1} are {} and {1}. Hence, f(1)=2 Similarly, the special subsets of {1,2} are {}, {1}, and {2}. Hence, f(2)=3.

The value of f(14) can thus be obtained by using the recursion repeatedly. That is,

f(3) = f(2) + f(1) = 3 + 2 = 5 f(4) = f(3) + f(2) = 5 + 3 = 8 f(5) = f(4) + f(3) = 8 + 5 = 13 ... f(14) = f(13) + f(12) = 610 + 377 = 987

Let f(x) denote the number of subsets of {1,2,3,...x} that satisfy the condition. We do smaller cases: f(0)=1 f(1)=2 f(2)=3 f(3)=5 We notice that the recurrence formula is: f(n+1)=f(n)+f(n-1). There is an actual explanation for the recurrence formula. For each of the subsets in f(n-1), we can add number (n+1) to the subsets and satisfy the condition. Thus, f(n-1) is the number of subsets containing (n+1) that satisfies the condition in f(n+1). Also, the subsets of f(n) are all of the subsets not containing (n+1) that satisfies the condition in f(n+1). We continue the sequence to obtain: f(4)=8 f(5)=13 f(6)=21 f(7)=34 f(8)=55 f(9)=89 f(10)=144 f(11)=233 f(12)=377 f(13)=610 f(14)=987

Let $A(n)$ be the number of subsets of ${1,2,3...,n}$ that contains no pair of consecutive integers. We claim that $A(n) = A(n-1)+A(n-2)$ . For all $n\ge3$ . Proof: Obviously, the number of subsets of ${1,2,3...,n}$ that does not contain n that contain no pair of consecutive integers is equal to the number of subsets from ${1,2,3...,n-1}$ that contain no pair of consecutive integers equals $A(n-1)$ . The number of subsets from ${1,2,3...,n}$ that contains n that contains no pair of consecutive integers is equal to $A(n-2)$ . So $A(n)=A(n-1)+A(n-2)$ . So $A(14)$ equals to 14th Fibonacci number which is 987.

Let the number of subsets with no pair of consecutive integers of ${1, 2, 3, ..., n }$ be $P_n$ . Then notice that $P_1=2, P_2=3$ .

If the last integer is not chosen , then there are $P_{n-1}$ subsets possible; if it is chosen, then there are $P_{n-2}$ subsets possible, so

$P_n=P_{n-1}+P_{n-2}$

Thus it is the Fibonacci Sequence, and $P_{14}=\boxed{987}$ .

Let $f(n) =$ the number of subsets of $\left\{1,2,...,n\right\}$ without consecutive integers.

If a valid subset contains $n$ , it cannot contain $(n-1)$ by definition. Then the number of valid subsets is $f(n-2)$ .

If a valid subset does not contain $n$ , then the number of valid subsets is $f(n-1)$ .

Then, $f(n)=f(n-1)+f(n-2)$ , $n\ge 3$

$f(1)=2$

$f(2)=3$

$f(3)=5$

$...$

$f(14)=987$

Let $a_n$ be the number of subsets of $\{1,2,3\cdots n\}$ that contain no pair of consecutive integers. If we include $n$ in our subset, then we have $a_{n-2}$ ways to choose the first $n-2$ numbers because we cannot include $n-1$ . If we do not include $n$ , then we have $a_{n-1}$ ways to choose the first $n-1$ numbers. This means $a_n=a_{n-1}+a_{n-2}$ . Observe that $a_0=1=F_2$ and $a_1=2=F_3$ , where $F_n$ denotes the $n$ th Fibonacci number. Hence $a_n=F_{n+2}$ . ( $F_n=F_{n-1}+F_{n-2}$ as well.) Therefore our answer is $a_14=F_{16}=987$ .

The number c of size -k subsets of [n] that contain no consecutive integers is given by c=c(n,k) = ( n+1-k ) ( k ) There is 1 empty set. There are 14 sets with 1 element. Applying the theorem for the next number of sets we have c(14,2) = 13 2 =13!/(2! * 11!) , so there are 78 sets with 2 elements

c(14,3) = 12 = 12!/3!9! = 220 sets with 3 elements 3

c(14,4) = 11 = 11!/4!7! = 330 sets with 4 elements 4

c(14,5) = 10 = 10!/5!5! = 252 sets with 5 elements 5

c(14,6) = 9 = 9!/3!6! = 84 sets with 6 elements 6

c(14,7) = 8 = 8!/1!7! = 8 sets with 7 elements 7

There are no more sets overs 7 elements, so total number of subsets = 987

suppose we want to count subsets of, say, 3 #s that satisfy the stipulation. consider the 14 #s as unnumbered balls and take out 3. 11 are left (shown as 0's) with 12 "spaces" (shown as x's) where the 3 #s we took out can be placed. x 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0 x

place the 3 #s in 12c3 ways, and then number the 14. so we can have 12c3 subsets of 3.

the same procedure will apply for other sizes of subsets from 0 to a max of 7, so we get ans = 15c0 + 14c1 + ....... + 8c7 = 987

There are 2^14 = 16384 subsets of {1, 2, 3, ..., 13, 14}. All the subsets having more than 14/2 = 7 elements would have at least one pair of consecutive integers. Therefore, our scope of consideration is limited to all the subsets having number of elements from 0 to 7.

The number c of size-k subsets of [n] that contain no consecutive integers is given by c = c(n, k) = Combination(n + 1 - k, k). You may find a proof given in http://capone.mtsu.edu/dwalsh/NOCONSC3.pdf.

The answer, therefore, is = C(15, 0) + C(14, 1) + C(13, 2) + C(12, 3) + C(11, 4) + C(10, 5) + C(9, 6) + C(8, 7) = 1 + 14 + 78 + 220 + 330 + 252 + 84 + 8 = 987

If the subset has 0 terms, there is 1 way to choose it. If the subset has 1 term, there are 14C1 = 14 ways to choose it. If the subset has 1 term, there are 13C2 = 78 ways to choose it. If the subset has 1 term, there are 12C3 = 220 ways to choose it. If the subset has 1 term, there are 11C4 = 330 ways to choose it. If the subset has 1 term, there are 10C5 = 252 ways to choose it. If the subset has 1 term, there are 9C6 = 84 ways to choose it. If the subset has 1 term, there are 8C7 = 8 ways to choose it. So the total is 987.

There is one empty set, and fourteen sets of one integer, which all work.

Next, consider a valid subset of two integers. Take out an integer in between, and what remains is a unique choosing of two integers from thirteen without restrictions. There are $\binom{13}{2}$ such subsets.

For a subset of length $n$ , we remove $n-1$ integers from the set, and then can count without restrictions. We then add $\binom{12}{3}$ , $\binom{11}{4}$ , $\binom{10}{5}$ , $\binom{9}{6}$ , and $\binom{8}{7}$ , which is choosing a subset of length seven, which is the max length allowed (every other integer has to be left out of the subset in order for it not to have consecutive integers). We add our starting fifteen subsets and the ones obtained from the combinatorics to get 987.

For subsets of $8$ to $14$ elements there are no solutions (for the pigeonhole principle ). The empty set is a solution (there are no elements between the elements. well really there are not elements at all).

For subsets with $1$ to $7$ rephrase the problem as "count the number of distributions of spaces between two consecutive elements in a subset of k elements". The numbers we do not include in the subset will be considered as spaces. Between two elements we include in the subset there will always be at least one space. This is equal to count the numer of anagrams of a word with $k$ " $n$ "(as n umber ) and $14-k$ " $s$ "(as s pace ), which is ${14-k+1 \choose k}$ , therefore there are ${14 \choose 1}$ + ${13 \choose 2}$ + ${12 \choose 3}$ + ${11 \choose 4}$ + ${10 \choose 5}$ + ${9 \choose 6}$ = = $14+78+220+330+252+84+8=986$ subsets which are solutions, plus the one with $0$ elements. Total: $987$ elements.

Let $a_n$ denote the number of subsets of $\{1, 2, 3, ..., n\}$ that contain no pair of consecutive integers. For all $n \ge 2$ , divide the subsets into two cases: subsets that use the element $n$ and subsets that don't use the element $n$ .

The subsets that don't use the element $n$ are just the $a_{n-1}$ subsets of $\{1, 2, 3, ..., n-1\}$ that contain no pair of consecutive integers.

The subsets that use the element $n$ cannot use the element $n-1$ . Then, these subsets are just the $a_{n-2}$ subsets of $\{1, 2, ..., n-2\}$ that contain no pair of consecutive integers, with the extra element $n$ . Then we have the recursion $a_n = a_{n-1} + a_{n-2}$ . From $a_0=1$ and $a_1=2$ , we get that $a_{14} = \boxed{987}$ .

In below i consider all the subsets which have no pair of consecutive integers

{ } have subset { } total=1

{1} have subset { }{1} total=2

{1,2} have subset {0} {1} {2} total=3

{1,2,3} have subset {0}{1} {2} {3} {1,3} total=5

{1,2,3,4} have subset {0} {1} {2} {3} {4} {1,3} {1,4} {2,4} total=8 ...

... so on

here i find the series

1, 2, 3, 5, 8.......

this is a Fibonacci series. so the 14th numbers in this series is 987

ans: 987

We can represent each subset of $\{1,\dots,14\}$ as a $14$ -tuple of Yes and No-s, representing whether $k$ is included in the subset or not. Alternatively, we can view this as a binary string of size $14$ , and in the natural order, the problem is equivalent to counting the number of bit strings of length 14 with no runs (consecutive occurrences of ones) whatsoever. This problem is well studied, and I will present two solutions, one that is combinatorial in nature, and the other that employs the use of OGFs to simplify the algebra (using combinatorial constructions in the spirit of "combinatorial species")

In the typical approach, imagine that we have a tape of $n$ cells that we can fill out from left to right with zero and ones $\boxed{?} \boxed{?} \boxed{?} \cdots$

Now, suppose that we look at the left-most cell (called cell one) and decide whether to place a zero or a one there: if we place a zero there, then we can just fill out the rest of the n-1 cells unhindered, but if we fill in a one, then we know that the next cell MUST be a 0, so we fix our first cell with a 1 and the next cell with a 0 and have the liberty of filling out the remaining n-2 cells however we like (using the same restricting however). This seems to suggest that we can represent this problem with the recurrence $W_n = \underbrace{W_{n-1}}_{\text{if we put a zero in cell one}} + \underbrace{W_{n-2}}_{\text{if we put a 10 in cell one and two}}$ with the condition that $W_0 = 1, W_1 = 2$ , which is just the shifted fibonacci sequence! So $W_k = f_{k+2}$ , and $W_{14} = f_{16} = \boxed{987}$ !

We start with induction:

Suppose that the number element of set without consecutive integer as $|A_i|$ .

for $i=1$ , $A_1=2$

for $i=2$ , $A_2=3$

for $i=3$ , $A_3=5$

and Claim:

$|A_{i+2}|=|A_{i+1}|+|A_i|$ , for $A_1=2$ , and $A_2=3$

Prove claim by induction:

Asumption true for $i=k$ elemen, hipotesis induction. $|A_k+2|=|A_{k+1}|+|A_k|$ ,

we will prove true for $i=k+1$ $|A_{k+3}|=|A_{k+2}|+|A_{k+1}|$

If there are set $i=k+1$ , suppose that: A_{k+3}={1,2,3,...,k+3).

We can partition this set become two part:

$A_{k+3}=(1,2,...,k+2) \cup (k+3)$ .

For ${1,2,...,k+2}$ there are $|A_{k+2}|$ subset.

if we adding $k+3$ in subset there are not consecutive integer,

subset contain $k+2$ not count and we obtain $|A_{k+1}|$

So, $|A_{k+3}|=|A_{k+2}|+|A_{k+1}$

And, we get $|A_{14}|=\fbox{987}$

The problem focuses on "choosing" numbers in the set.

First we will make a mask for them. The mask can be considered as a 14-digits binary number, each digit indicates "the state of chosen" of each element in set. For example, a set like $\{2, 5, 7, 9, 12, 13\}$ can be illustrated by this mask: $01001010100110$

Then, the new problem is counting the number of binary masks in which there're no two consecutive 1s. We could do this by using the Markov chain. In particular, if the current digit is 0, the next can be 1 or 0, otherwise, it can only be 0. Therefore, we have this stochastic matrix: $P = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$

The result will be the sum of $P^{14}_{0, 0}$ and $P^{14}_{0, 1}$ because we don't care which digits at the end and the beginning (so we could assume that there is one more 0 before the first digit). From here we could power it with the index of 14 and sum $P^14_{0, 0}$ and $P^14_{0, 1}$ to get the final result. Or expand it a little more:

$P^n_{0, 0} = 1 \times P^{n-1}_{0, 0} + 1 \times P^{n-1}_{0, 1}$ $P^n_{0, 1} = 1 \times P^{n-1}_{0, 0} + 0 \times P^{n-1}_{0, 1}$ $\Rightarrow P^n_{0, 0} = P^{n-1}_{0, 0} + P^{n-2}_{0, 0}$

This formula is similar to the Fibonarci series. We also have:

$P_{0, 0} = 1 = F(2)$ and $P^2_{0, 0} = 2 = F(3)$

So the result is:

$P^{14}_{0, 0} + P^{14}_{0, 1} = P^{15}_{0, 0} = F(16) = 987$

The final result of the problem is $987$ .

C(15,0)+C(14,1)+C(13,2)+C(12,3)+C(11,4)+C(10,5)+C(9,6)+C(8,7)=987