login
A349595
Number of self-counting sequences of length n (sequences indexed from 0 to (n-1) where a(i) is the number of times i appears in the sequence).
0
0, 0, 0, 2, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
OFFSET
1,4
COMMENTS
There is exactly one self-counting sequence for any n > 6 and it will always be of the form [n-4, 2, 1, ..., 1, ...], where the second "1" is at the (n-4)th index, and the "..."s are filled with the appropriate number of zeros. For example, the only self-counting sequence of length 7 is [3, 2, 1, 1, 0, 0, 0], and the only self-counting sequence of length 15 is [11, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0].
Proof:
Let a be a self-counting sequence of finite length. Firstly, observe that for all such sequences, the sum of a(i) - 1 over all i must equal 0. The contributions to this sum from those i for which a(i) = 0 will be some number of -1s. How many such -1s? a(0). The contribution from the i=0 case will be a(0)-1 (note that a(0) cannot be equal to 0, so these two contribution cases are disjoint). Thus, if we sum a(i) - 1 over just those nonzero i for which a(i) is nonzero, we will get a(0) - (a(0) - 1) = 1. These a(i) - 1 values are all whole numbers >= 0, so for them to sum to 1 is precisely for one of them to be 1 and the rest to be 0. And thus, we have precisely one nonzero i at which a(i) is 2, and at the other nonzero i, we have a(i) is either 1 or 0, and the only configuration of these ones and zeros that works is to have a(1) = 2, a(2) = 1, a(a(0)) = 1 and a(i) = 0 for all other nonzero i.
FORMULA
G.f.: x^4*(2 - x - x^2 + x^3)/(1 - x). - Stefano Spezia, Dec 08 2021
EXAMPLE
n = 4 is the smallest length that a self-counting sequence can have (without considering the empty sequence of length 0, which could be self-counting or not, depending on the definition). There are two self-counting sequences of length 4, namely [1, 2, 1, 0] and [2, 0, 2, 0]. We can verify the first one by counting the times each number appears: 0 appears once, 1 appears twice, 2 appears once and 3 appears zero times.
CROSSREFS
Sequence in context: A203947 A081396 A194293 * A298941 A317146 A194297
KEYWORD
nonn,easy
AUTHOR
Leo Crabbe, Nov 22 2021
STATUS
approved