A278987 Array read by antidiagonals downwards: T(b,n) = number of words of length n over an alphabet of size b that are in standard order and which have the property that every letter that appears in the word is repeated.
0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 4, 1, 1, 0, 1, 11, 4, 1, 1, 0, 1, 26, 11, 4, 1, 1, 0, 1, 57, 41, 11, 4, 1, 1, 0, 1, 120, 162, 41, 11, 4, 1, 1, 0, 1, 247, 610, 162, 41, 11, 4, 1, 1, 0, 1, 502, 2165, 715, 162, 41, 11, 4, 1, 1, 0, 1, 1013, 7327, 3425, 715, 162, 41, 11, 4, 1, 1, 0
Offset: 1
Examples
The array begins: 0,.1,..1,...1,...1,...1,...1,....1..; b=1, 0,.1,..4,...8,..16,..32,..64,..128..; b=2, 0,.1,..4,..14,..41,.122,.365,.1094..; b=3, 0,.1,..4,..14,..51,.187,.715,.2795..; b=4, 0,.1,..4,..14,..51,.202,.855,.3845..; b=5, 0,.1,..4,..14,..51,.202,.876,.4111..; b=6, ... Rows b=1 through b=4 of the array are A000012, A000295 (or A130103), A278988, A278989.
Links
- Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Crossrefs
The words for b=9 are listed in A273978.
Programs
-
Maple
with(combinat); A008299 := proc(n,k) local i,j,t1; if k<1 or k>floor(n/2) then t1:=0; else t1 := add( (-1)^i*binomial(n, i)*add( (-1)^j*(k - i - j)^(n - i)/(j!*(k - i - j)!), j = 0..k - i), i = 0..k); fi; t1; end; f3:=proc(L,b) global A008299; local i; add(A008299(L,i),i=1..b); end; Q3:=b->[seq(f3(L,b),L=1..40)]; for b from 1 to 6 do lprint(Q3(b)); od:
Formula
The number of words of length n over an alphabet of size b that are in standard order and in which every symbol that appears in a word is repeated is Sum_{j = 1..b} A008299(n,j).
Comments