Counting Fat Sets

We start with the set $\mathbb{N}_{n}=\{1,2,\ldots,n\}$. A subset $A\subset \mathbb{N}_{n}$ is said to be fat if, for every $x\in A$, $x\ge |A|$, where $|A|$ is the cardinality of, i.e., the number of elements in, $A$. (Fat sets have been introduced by George Andrews.)

As an example, with $n=4$, the sets $\emptyset$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{2,3\}$, $\{2,4\}$, $\{3,4\}$ are fat subsets of $\mathbb{N}_{n}$, while the sets $\{1,2\}$, $\{1,3\}$, $\{1,4\}$, $\{1,2,3\}$, $\{1,2,4\}$, $\{1,3,4\}$, $\{2,3,4\}$, and $\{1,2,3,4\}$ are not.

How many fat subsets are there in $\mathbb{N}_{n}$? Let's denote that number $f_n$. We shall prove a recursive formula:

The number $f_n$ of fat subsets of $\mathbb{N}_{n}$ satisfies the recurrence

$f_{n+1}$ = $f_n$ + $f_{n-1}$, $n\ge 2$,

with $f_{1}=2$ and $f_{2}=3$.

Proof

Let $A\subset\mathbb{N}_{n}$ is fat. There are two possibilities: $n\in A$ and $n\notin A$. In the latter case, $A$ is a fat subset of $\mathbb{N}_{n-1}$ and counts in $f_{n-1}$. Assume, $n\in A$. In that case, $1\notin A$, because, otherwise, we would have $|A|\ge 2\gt 1$, making $A$ non-fat. Define $B=A\setminus\{n\}$, and $C=\{x-1:\space x\in B\}$. $C$ is then a fat subset of $\mathbb{N}_{n-2}$. We see that any fat subset $A$ of $\mathbb{N}_{n}$ is either a fat subset of $\mathbb{N}_{n-1}$ or uniquely corresponds to a fat subset of $\mathbb{N}_{n-2}$. The converse is also true, thus proving the recurrence. In addition, $A\subset\mathbb{N}_{1}$ has only two fat subset, $\emptyset$ and $\{1\}$, while $A\subset\mathbb{N}_{2}$ has three, $\emptyset$, $\{1\}$, and $\{2\}$.

Obviously, $\{f_n\}$ is a "shifted" Fibonacci sequence $\{F_n\}$, where $F_0=F_1=1$: $f_n=F_{n+2}$.

There is another way to count the fat subsets of $A\subset\mathbb{N}_{n}$.

There is only one way to pick the empty set. There are ${n \choose 1}$ ways to select a one-element subset. Since $1$ couldn't be included in fat subsets of more than $1$ element, there are ${n-1 \choose 2}$ $2$-element fat subsets. For a similar reason, $2$ is excluded from fat subsets with more than $2$ elements so that there are ${n-2 \choose 3}$ $3$-element subsets, and so on. The question is where do we stop? This depends on the parity of $n$:

$f_{n}= \begin{cases} {n+1 \choose 0}+{n \choose 1}+{n-1 \choose 2}+\ldots+{(n+1)/2 \choose (n+1)/2},& \text{if}\space n\space \text{is odd} \\ {n+1 \choose 0}+{n \choose 1}+{n-1 \choose 2}+\ldots+{(n+2)/2 \choose n/2},& \text{if}\space n\space \text{is even} \end{cases}$

Remarkably, sums like these appear in the diagonals of the Pascal triangle: Using the shorthand, $\displaystyle f_{n}=\sum_{k=0}^{N}{n+1-k \choose k}$, where $N=(n+1)/2$ if $n$ is odd and $N=n/2$ if $n$ is even.

It could be shown that such sums satisfy the Fibonacci recurrence. Vladimir Nikolin came up with a proof without words of the latter fact: References

1. V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995
2. A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
3. R. Grimaldi, Fibonacci and Catalan Numbers: an Introduction, Wiley, 2012 Pascal's Triangle and the Binomial Coefficients Combinatorial Proofs 