OFFSET
0,2
COMMENTS
a(n) is the number of compositions of n+5 into parts 1, 6, 8, 9, 12, 15, 18, 21, ...
Other sequences related to restricted combinations along with the sets of disallowed differences between subset elements: A000045 {1}, A011973 {1}, A006498 {2}, A006500 {3}, A031923 {4}, A000930 {1,2}, A102547 {1,2}, A130137 {1,3}, A263710 {1,4}, A374737 {1,5}, A079972 {2,3}, A224809 {2,4}, A351873 {3,4}, A224810 {3,6}, A224815 {4,8}, A003269 {1,2,3}, A180184 {1,2,3}, A317669 {1,2,4}, A351874 {1,3,4}, A177485 {1,3,5}, A121832 {2,3,4}, A375982 {2,3,5}, A375983 {2,4,5}, A224808 {2,4,6}, A224814 {3,6,9}, A003520 {1,2,3,4}, A375185 {1,2,3,5}, A375186 {1,2,4,5}, A259278 {2,3,4,5}, A224811 {2,4,6,8}, A005708 {1,2,3,4,5}, A276106 {2,3,4,5,6}, A224812 {2,4,6,8,10}, A005709 {1,2,3,4,5,6}, A322405 {2,3,4,5,6,7}, A224813 {2,4,6,8,10,12}, A005710 {1,2,3,4,5,6,7}, A368244 {2,3,4,5,6,7,8}, A000027 {1,2,..}, A269445 {1,2,..}\{12,25,..}, A008730 {1,2,..}\{11,23,..}, A008729 {1,2,..}\{10,21,..}, A008728 {1,2,..}\{9,19,..}, A008727 {1,2,..}\{8,17,..}, A008726 {1,2,..}\{7,15,..}, A008725 {1,2,..}\{6,13,..}, A038718 {1,..,5,7,..}, A008724 {1,2,..}\{5,11,..}, A008732 {1,2,..}\{4,9,..}, A179999 {1,2,3,5,7,..}, A001972 {1,2,..}\{3,7,..}, A001840 {1,2,..}\{2,5,..}, A052955 {1,3,..}, A004277 {2,3,..}, A186384 {1,2,..}\{1,6,..}, A186347 {1,2,..}\{1,5,..}, A339573 {1,2,..}\{1,4,..}, A002620 {2,4,..}, A019442 {3,4,..}, A006501 {3,6,..}, A008233 {4,8,..}, A008382 {5,10,..}, A008881 {6,12,..}, A009641 {7,14,..}, A009694 {8,16,..}, A009714 {9,18,..}, A354600 {10,20,..}.
LINKS
Michael A. Allen, Combinations without specified separations, Communications in Combinatorics and Optimization (in press).
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,0,1,0,1,0,0,-1).
FORMULA
a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) + a(n-8) - a(n-11) for n >= 11.
G.f.: (1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 - x^8 - x^9 - x^10)/(1 - x - x^3 + x^4 - x^6 - x^8 + x^11).
EXAMPLE
For n = 6, the 14 subsets are {}, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}, {5}, {2,5}, {3,5}, {6}, {3,6}, {4,6}.
The a(4) = 8 compositions of 9 into parts 1, 6, 8, 9, ... are 1+1+1+1+1+1+1+1+1, 1+1+1+6, 1+1+6+1, 1+6+1+1, 6+1+1+1, 1+8, 8+1, 9.
MATHEMATICA
CoefficientList[Series[(1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 - x^8 - x^9 - x^10)/(1 - x - x^3 + x^4 - x^6 - x^8 + x^11), {x, 0, 42}], x]
LinearRecurrence[{1, 0, 1, -1, 0, 1, 0, 1, 0, 0, -1}, {1, 2, 3, 5, 8, 11, 14, 19, 25, 34, 49}, 42]
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Michael A. Allen, Sep 04 2024
STATUS
approved