Question 28 — UTC Tryout #2 OSN-K 2025 B1c

Bearcu sedang bermain RPG. Pada game ini, setiap lawan memiliki kelemahan terhadap satu elemen. Elemen-elemen ini dilambangkan dengan bilangan dari 1 sampai n. Bearcu perlu membentuk party yang terdiri sejumlah karakter. Masing-masing karakter dapat mengalahkan lawan dengan elemen tertentu, yang dinotasikan sebagai himpunan bagian dari {1, 2, ... n}. Sebagai contoh, jika n = 5, karakter dengan himpunan {1, 3, 4} bisa mengalahkan lawan dengan kelemahan elemen 1, 3, atau 4.

Suatu party dikatakan seimbang jika untuk semua lawan yang mungkin, terdapat setidaknya satu karakter dalam party yang bisa mengalahkan lawan itu. Sebagai contoh, jika n = 5, party yang terdiri atas dua karakter {1, 3, 4} dan {2, 3, 5} seimbang. Akan tetapi, party dengan karakter {1, 2, 3} dan {2, 5} tidak seimbang, karena tidak memiliki elemen 4. Urutan karakter di dalam party tidak mempengaruhi.

Misalkan n = 4 dan tersedia 15 karakter berikut untuk direkrut. Semua karakter berbeda.

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

Ada berapa cara membentuk party seimbang tanpa memedulikan banyaknya karakter yang direkrut?