For a positive integer $n$ let $t_n$ be the number of unordered triples of non-empty and pairwise disjoint subsets of a given set with $n$ elements. For example, $t_3 = 1$. Find a closed form formula for $t_n$ and determine the last digit of $t_{2022}$. (I also give here that $t_4 = 10$, for a reader to check his/her understanding of the problem statement.)
Problem
Source: Bulgaria JBMO 2022 TST Day 1 Problem 3
Tags: combinatorics, counting, Inclusion-exclusion
Marwanshtine
14.05.2022 17:20
the answer is $t_n=(4^n-3^{n+1}+3\times2^n-1)/6$ and the last digit of $t_{2022}$ is 0
P2nisic
14.05.2022 18:15
Marwanshtine wrote: the answer is $t_n=(4^n-3^{n+1}+3\times2^n-1)/6$ and the last digit of $t_{2022}$ is 0
Attachments:
Iora
14.05.2022 23:45
Marwanshtine wrote: the answer is $t_n=(4^n-3^{n+1}+3\times2^n-1)/6$ and the last digit of $t_{2022}$ is 0 Can someone explain how to derive and prove the formula? Thanks @below
Assassino9931
15.05.2022 00:02
Yep, here goes. We will use an inclusion-exclusion strategy. Let us count the ordered triples (then for the final answer just divide by $3!=6$, as in each triple there are no two identical sets). Each element in the $n$-th element set can be either in the first group, or in the second or in the third or in none of them - $4^n$ ways. Now we have to exclude the cases with at least one empty group - there are three choices for it and then each element can be in one of the other two group or in none of them - so $3\cdot 3^n = 3^{n+1}$ ways. Now we have to include the cases with at least two empty groups - there are three choices for which ones and then each element is either in the third group or not - so $3\cdot 2^n$ ways. Finally, we exclude the unique case where all three groups are empty. Remark. I invite the others to try on their own to solve the problem with recursion The calculations are more tedious for a junior, but certainly doable.
Assassino9931
05.12.2022 23:57
Just found out that this problem is very related to Putnam 1985 A1.