login
Base-2 generalized Pascal triangle P_2 read by rows (see Comments for precise definition).
4

%I #46 Aug 26 2018 19:30:32

%S 1,1,1,1,1,1,1,2,0,1,1,1,2,0,1,1,2,1,1,0,1,1,2,2,1,0,0,1,1,3,0,3,0,0,

%T 0,1,1,1,3,0,3,0,0,0,1,1,2,2,1,1,2,0,0,0,1,1,2,3,1,1,1,1,0,0,0,1,1,3,

%U 1,3,0,2,0,1,0,0,0,1,1,2,4,1,2,0,2,0,0

%N Base-2 generalized Pascal triangle P_2 read by rows (see Comments for precise definition).

%C List the binary numbers in their natural order as binary strings, beginning with the empty string epsilon, which represents 0. Row n of the triangle gives the number of times the k-th string occurs as a (scattered) substring of the n-th string.

%C Row n has sum n+1.

%H Lars Blomberg, <a href="/A282714/b282714.txt">Table of n, a(n) for n = 0..10000</a>

%H Julien Leroy, Michel Rigo, Manon Stipulanti, <a href="http://dx.doi.org/10.1016/j.disc.2017.01.003">Counting the number of non-zero coefficients in rows of generalized Pascal triangles</a>, Discrete Mathematics 340 (2017), 862-881.

%H Julien Leroy, Michel Rigo, Manon Stipulanti, <a href="https://arxiv.org/abs/1705.10065">Counting Subwords Occurrences in Base-b Expansions</a>, arXiv:1705.10065 [math.CO], 2017.

%H Julien Leroy, Michel Rigo, Manon Stipulanti, <a href="http://math.colgate.edu/~integers/sjs13/sjs13.Abstract.html">Counting Subwords Occurrences in Base-b Expansions</a>, Integers, Electronic Journal of Combinatorial Number Theory 18A (2018), #A13.

%H Manon Stipulanti, <a href="https://arxiv.org/abs/1801.03287">Convergence of Pascal-Like Triangles in Parry-Bertrand Numeration Systems</a>, arXiv:1801.03287 [math.CO], 2018.

%e Triangle begins:

%e 1,

%e 1,1,

%e 1,1,1,

%e 1,2,0,1,

%e 1,1,2,0,1,

%e 1,2,1,1,0,1,

%e 1,2,2,1,0,0,1,

%e 1,3,0,3,0,0,0,1,

%e 1,1,3,0,3,0,0,0,1

%e 1,2,2,1,1,2,0,0,0,1

%e 1,2,3,1,1,1,1,0,0,0,1

%e 1,3,1,3,0,2,0,1,0,0,0,1

%e 1,2,4,1,2,0,2,0,0,0,0,0,1

%e ...

%e The binary numbers are epsilon, 1, 10, 11, 100, 101, 110, 111, 1000, ...

%e The fifth number 101 contains

%e eps 1 10 11 100 101 respectively

%e .1..2..1..1...0...1 times, which is row 5 of the triangle.

%p Nscatsub := proc(subw,w)

%p local lsubw,lw,N,wri,wr,i ;

%p lsubw := nops(subw) ;

%p lw := nops(w) ;

%p N := 0 ;

%p if lsubw = 0 then

%p return 1 ;

%p elif lsubw > lw then

%p return 0 ;

%p else

%p for wri in combinat[choose](lw,lsubw) do

%p wr := [] ;

%p for i in wri do

%p wr := [op(wr),op(i,w)] ;

%p end do:

%p if verify(subw,wr,'sublist') then

%p N := N+1 ;

%p end if;

%p end do:

%p end if;

%p return N ;

%p end proc:

%p P := proc(n,k,b)

%p local n3,k3 ;

%p n3 := convert(n,base,b) ;

%p k3 := convert(k,base,b) ;

%p Nscatsub(k3,n3) ;

%p end proc:

%p A282714 := proc(n,k)

%p P(n,k,2) ;

%p end proc: # _R. J. Mathar_, Mar 03 2017

%t nmax = 12;

%t row[n_] := Module[{bb, ss}, bb = Table[IntegerDigits[k, 2], {k, 0, n}]; ss = Subsets[Last[bb]]; Prepend[Count[ss, #]& /@ bb // Rest, 1]];

%t Table[row[n], {n, 0, nmax}] // Flatten (* _Jean-François Alcover_, Dec 14 2017 *)

%Y A007306 gives (essentially) the number of nonzero entries in the rows.

%K nonn,tabl

%O 0,8

%A _N. J. A. Sloane_, Mar 02 2017

%E More terms from _Lars Blomberg_, Mar 03 2017