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, 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

Author

Leo Crabbe, Nov 22 2021

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (1).

Formula

G.f.: x^4*(2 - x - x^2 + x^3)/(1 - x). - Stefano Spezia, Dec 08 2021