cp's OEIS Frontend

A330509 Triangle read by rows: T(n,k) is the number of 4-ary strings of length n with k indispensable digits, with 0 <= k <= n.

%I A330509 #27 Jul 20 2020 13:00:55
%S A330509 1,1,3,1,9,6,1,19,34,10,1,34,115,91,15,1,55,301,445,201,21,1,83,672,
%T A330509 1582,1338,392,28,1,119,1344,4600,6174,3410,700,36,1,164,2478,11623,
%U A330509 22548,19784,7723,1170,45,1,219,4290,26452,69834,88428,55009,15999,1857,55
%N A330509 Triangle read by rows: T(n,k) is the number of 4-ary strings of length n with k indispensable digits, with 0 <= k <= n.
%C A330509 A digit in a string is called indispensable if it is greater than the following digit or equal to the following digits which are eventually greater than the following digit.  We also assume that there is an invisible digit 0 at the end of any string.  For example, in 7233355548, the digits 7, 5, 5, 5, and 8 are indispensable.
%C A330509 T(n, k) is also the number of integers m where the length of the base-4 representation of m is n and the digit sum of the base-4 representation of 3m is 3k.
%H A330509 J. Y. Choi, <a href="https://doi.org/10.7546/nntdm.2019.25.2.40-48">Indispensable digits for digit sums</a>, Notes Number Theory Discrete Math 25 (2019), pp. 40-48.
%H A330509 J. Y. Choi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL22/Choi/choi15.html">Digit sums generalizing binomial coefficients</a>, J. Integer Seq. 22 (2019), Article 19.8.3.
%F A330509 T(n, k) = A008287(n, 3k-2) + A008287(n, 3k-1) + A008287(n, 3k).
%e A330509 Triangle begins
%e A330509   1;
%e A330509   1,   3;
%e A330509   1,   9,   6;
%e A330509   1,  19,  34,  10;
%e A330509   1,  34, 115,  91,  15;
%e A330509   1,  55, 301, 445, 201,  21;
%e A330509   ...
%e A330509 There is 1 string (00) of length 2 with 0 indispensable digits.
%e A330509 There are 9 strings (01, 02, 03, 10, 12, 13, 20, 23, 30) of length 2 with 1 indispensable digit.
%e A330509 There are 6 strings (11, 21, 22, 31, 32, 33) of length 2 with 2 indispensable digits.
%e A330509 Hence T(2,0)=1, T(2,1)=9, T(2,2)=6.
%t A330509 Table[Total@ Map[Sum[Binomial[n, i] Binomial[n, # - 2 i], {i, 0, #/2}] &, 3 k + {-2, -1, 0}], {n, 0, 9}, {k, 0, n}] // Flatten (* _Michael De Vlieger_, Dec 23 2019, after _Jean-François Alcover_ at A008287 *)
%o A330509 (PARI) A008287(n, k) = if(n<0, 0, polcoeff((1 + x + x^2 + x^3)^n, k));
%o A330509 T(n, k) = A008287(n, 3*k-2)+A008287(n, 3*k-1) + A008287(n, 3*k);
%Y A330509 Cf. A008287, A330381.
%K A330509 nonn,tabl,base
%O A330509 0,3
%A A330509 _Ji Young Choi_, Dec 16 2019