cp's OEIS Frontend

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).

%I A349595 #19 Dec 13 2021 17:28:47
%S A349595 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,
%T A349595 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,
%U A349595 1,1,1,1,1,1,1,1,1,1
%N 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).
%C A349595 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].
%C A349595 Proof:
%C A349595 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.
%H A349595 <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (1).
%F A349595 G.f.: x^4*(2 - x - x^2 + x^3)/(1 - x). - _Stefano Spezia_, Dec 08 2021
%e A349595 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.
%K A349595 nonn,easy
%O A349595 1,4
%A A349595 _Leo Crabbe_, Nov 22 2021