Now I’m intrigued with this sequence, what’s the significance?
1,9,45,165,495,1287,
That is from an early attempt of mine to solve a discrete mathematics and combinatorics problem that I thought about several years ago in connection with an advertisement I heard. I still have my notes on it.
Circa 2010 in Canada, there was a Dairy Queen commercial that said one can have pairs, triples, or quadruples from a choice of nine items. The claim was this number exceeded 20,000 possibilities. I thought this to be a gross overestimate and tried to come up with a systematic way of tallying the actual numbers in the sequence.
Say there are nine possible side items to choose from. Order of selection does not matter, repetition matters (we can select the same combo item repeatedly).
First element in the sequence: Say one has no choice in the matter. "You may select nothing." There is one possibility of zero items selected.
Second element in the sequence: Say one has one choice. There are nine possibilities.
Third element in the sequence: Say one has two choices. These are the possible pairs, of which there are forty-five possibilities:
11 22 33 44 55 66 77 88 99
12 23 34 45 56 67 78 89
13 24 35 46 57 68 79
14 25 36 47 58 59
15 26 37 48 59
16 27 38 49
17 28 39
18 29
19.
(2+9-1)! / (2!(9-2)!) = 45 (n=9, r=2).
Fourth element in the sequence: triples. Say one has three possibilities. Then: 165.
Fifth element in the sequence: quadruples. Say one has four possible selections. Then: 495.
Sixth element in the sequence: quintuples. So there are five selections we can make in this case. Then: 1287.
The triangular pattern when I tried to count it by brute force is interesting, and the formula corroborates the entries. It is actually an infinite sequence.
In short, the Dairy Queen commercial was far off, and that was false advertising. 45+165+495=705. This is far shy of "over 20,000 possibilities".