Items tagged with combinatorics

HI MaplePrimes.com and other watchers,

Please enjoy the attaced files about combinatorics.
You may already know what '4 choose 3' is.

an_excercise_in_combinatorics.mw

an_excercise_in_combinatorics.pdf

Hopefully this can be useful to the casual mathematical observer.

Regards,

Matt

 

Let us denote the cardinality of the subsets of {1,..,n} without two consequent numbers
(e.g. {..,4,5,..} is not allowed) by A[n]. What is the asymptotics of A[n] as n approaches infinity?
The same question for the case of three consequent numbers.
Here is my math experiment.
restart; L := combinat:-powerset({seq(i, i = 1 .. 11)}):#n = 11
nops(%);
2048
M := selectremove(c-> min([seq(c[k+1]-c[k], k = 1 .. nops(c)-1)]) = 1, L)[2]:
nops(M);
233
The other results are [11, 233], [15, 1597], [20, 17711], [21, 28657], [22, 46368].
These points are very close to some straight line in logarithmic scale as
plot([[11, 233], [15, 1597], [20, 17711], [21, 28657], [22, 46368]], axis[2] = [mode = log]);
shows. However, the ones do not exactly belong to a straight line:
evalf(ln(46368)-ln(28657), 15);
0.4812118247230
evalf(ln(28657)-ln(17711), 15);
0.48121182594077
eval(exp(.4812118247230*n), n = 15);
1364.000725  .
These results suggest that A[n] is asymptotically equal to exp(c*n) with c about 0.481.
I have not succeeded to find out the nature of the constant c.

question_on_asymptotics.mw

Greetings to all. I am writing today to share a personal story / exploration using Maple of an algorithm from the history of combinatorics. The problem here is to count the number of strings over a certain alphabet which consist of some number of letters and avoid a set of patterns (these patterns are strings as opposed to regular expressions.) This counting operation is carried out using rational generating functions that encode the number of admissible strings of length n in the coefficients of their series expansions. The modern approach to this problem uses the Goulden-Jackson method which is discussed, including a landmark Maple implementation from a paper by D. Zeilberger and J. Noonan, at the following link at math.stackexchange.com (Goulden-Jackson has its own website, all the remaining software described in the following discussion is available at the MSE link.) The motivation for this work was a question at the MSE link about the number of strings over a two-letter alphabet that avoid the pattern ABBA.

As far as I know before Goulden-Jackson was invented there was the DFA-Method (Deterministic Finite Automaton also known as FSM, Finite State Machine.) My goal in this contribution was to study and implement this algorithm in order to gain insight about its features and how it influenced its powerful successor. It goes as follows for the case of a single pattern string: compute a DFA whose states represent the longest prefix of the pattern seen at the current position in the string as it is being scanned by the DFA, with the state for the complete pattern doubling as a final absorbing state, since the pattern has been seen. Translate the transitions of the DFA into a system of equations in the generating functions representing strings ending with a given maximal prefix of the pattern, very much like Markov chains. Finally solve the system of equations for the generating functions and thus obtain the sequence of values of strings of length n over the given alphabet that avoid the given pattern.

I have also implemented the DFA method for sets of patterns as opposed to just one pattern. The algorithm is the same except that the DFA does not consist of a chain with backlinks as in the case of a single pattern but a tree of prefixes with backlinks to nodes higher up in the tree. The nodes in the tree represent all prefixes that need to be tracked where obviously a common prefix between two or more patterns is shared i.e. only represented once. The DFA transitions emanating from nodes that are leaves represent absorbing states indicating that one of the patterns has been seen. We run this algorithm once it has been verified that the set of patterns does not contain pairs of patterns where one pattern is contained in another, which causes the longer pattern to be eliminated at the start. (Obviously if the shorter pattern is forbidden the so is the longer.) The number of states of the DFA here is bounded above by the sum of the lengths of the patterns with subpatterns eliminated. The uniqueness property of shared common prefixes holds for subtrees of the main tree i.e. recursively. (The DFA method also copes easily with patterns that have to occur in a certain order.)

I believe the Maple code that I provide here showcases many useful tricks and techniques and can help the reader advance in their Maple studies, which is why I am alerting you to the web link at MSE. I have deliberately aimed to keep it compatible with older versions of Maple as many of these are still in use in various places. The algorithm really showcases the power of Maple in combinatorics computing and exploits many different aspects of the software from the solution of systems of equations in rational generating functions to the implementation of data structures from computer science like trees. Did you know that Maple permits nested procedures as known to those who have met Lisp and Scheme during their studies? The program also illustrates the use of unit testing to detect newly introduced flaws in the code as it evolves in the software life cycle.

Enjoy and may your Maple skills profit from the experience!

Best regards,

Marko Riedel

The software is also available here: dfam-mult.txt

I am working on a problem that involves a great deal of combinatorics, and I have broken the problem into several procedures.  I am trying to create a first procedure that creates a list output, a second procedure which takes the list and other input and cycles over combinations of two elements from the list and calls a third procedure to perform the calculus needed for each pair.  A simplified example follows:

f1:=proc(a1, a2, ..., an)
(various if-then statements)

return [b1, b2,...,bn];

end:

 

f2:=proc(alpha, beta,...,L::list)

A:=0;
for i from 1 to n-1 do
     for j from i+1 to n do
     A:= A+ f2(alpha, beta, ..., L[i], L[j])
     end do;
end do;

return A;

end:

 

f3:=proc(alpha, beta, ..., bi, bj)

(various mathematical manipulations)
return x;

end:

 

When I first use f1 to get [b1, b2, ..., bn] and then invoke f2 as f2(alpha, beta, ..., [b1, b2, ..., bn]) everything works fine.

However, f1 needs to be invoked by yet a larger function as follows:
...

L0:=[0,0,0,...,0]:
L0:=f1(a1, a2, ..., an):
B:=f2(alpha, beta,...,L0):

...
When I do this, L0 still gets assigned the correct value according the program trace, yet it fails to invoke f3 correctly.  What could the problem be?

hello all!

Pascal := proc (n::posint)

local x, y, i;

 for i from 0 to n do print(coeffs(expand((x+y)^i)))

end do end proc;
Pascal(4);

   

1
1, 1
1, 2, 1
1, 3, 3, 1
1, 4, 6, 4, 1

 How to create 

         

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1

 

Let four straight lines in general position be given. Their complement consists of  11 domains. One can choose four (PS. different) points belonging to the pieces s.t. exactly two points lie astride everyone of these lines. Here is an example.

 

restart; with(geometry)``

line(L1, [point(A, 1, 1/2), point(B, 2, 1)]):

geometry:-line(L2, [geometry:-point(C, 1, -1/2), geometry:-point(E, 2, -1)]):

geometry:-line(L3, [geometry:-point(F, 1/2+1, 1), geometry:-point(G, 1+1, 2)]):

geometry:-line(L4, [geometry:-point(H, -1/2+2, 1+2), geometry:-point(K, (-1)+2, 2+2)]):

geometry:-point(P1, [-6, 0]):``

geometry:-point(P2, [2, 6]):

geometry:-point(P3, [8, -6]):

geometry:-draw([L1, L2, L3, L4, P1(color = blue, symbol = solidcircle, symbolsize = 15), P2(color = blue, symbol = solidcircle, symbolsize = 15), P3(color = blue, symbol = solidcircle, symbolsize = 15), P4(color = blue, symbol = solidcircle, symbolsize = 15)])

 

``

``

 

Download four_points.mw




How many are such configurations (If the points belong to the same pieces, two configurations are equivalent. PS. I.e. one may move points in the  pieces.)?
How to determine it with Maple? Robert Israel used GraphTheory, having answered that.

How many numbers exist which are: less than 1000, multiple of 18 and also multiple of 10? Use Maple to find the answer 

Social Golfer Problem

So we have 8 golfers : 2 golfers per group and 4 groups.Over several golfing days, how can they be arranged so no golfer plays with the same player twice.

turns out they can play for 7 days.

So my attempt in maple....golfing.mw

For 3 players per group and 4 groups this is the arrangement over 4 days:

(these was done in wolfram demonstrations project but the code appears to be obfuscated)

I want to write a procedure which recieves a natural N and print all the possible 2ˆN sequences of zeros and ones with size N.

 

 For instance, if I set N = 3; my procedure returns a set with 8 lists of zeros and ones: [[0,0,0],[1,0,0],[0,1,0],[0,0,1][1,0,1],[0,1,1],[1,1,1]] ;

 

Many thanks!

Dear friends,

some time ago I shared a story here on the use of Maple to compute the cycle index of the induced action on the edges of an ordinary graph of the symmetric group permuting the vertices and the use of the Polya Enumeration Theorem to count non-isomorphic graphs by the number of edges. It can be found at the following Mapleprimes link.

I am writing today to alert you to another simple Maple program that is closely related and demonstrates Maple's capability to implement concepts from group theory and Polya enumeration. This link at Math.Stackexchange.com shows how to use the cycle index of the induced action by the symmetric group permuting vertices on the edges of a multigraph that includes loops to count set partitions of multisets containing two instances of n distinct types of items. The sequence that corresponds to these set partitions is OEIS A020555 where it is pointed out that we can equivalently count multigraphs with n labeled i.e. distinct edges where the vertices of the graph represent the multisets of the multiset partition and are connected by an edge k if the two instances of the value k are included in the sets represented by the two vertices that constitute the edge. The problem then reduces to a simple substitution into the aforementioned cycle index of a polynomial representing the set of labels on an edge including no labels on an edge that is not included.

This computation presents a remarkable simplicity while also implementing a non-trivial application of Polya counting. It is hoped that MaplePrimes users will enjoy reading this program, possibly profit from some of the techniques employed and be motivated to use Maple in their work on combinatorics problems.

Best regards,

Marko Riedel

ma := allstructs(Permutation([1, 1, 1, 2, 2, 2, 3, 3, 3]), size = 3);

above is fast

but below is very slow.
ma2 := allstructs(Permutation(ma), size = 3);

just for all combinations of matrix , replicateM in haskell is the fastest.

in maple, ma2 := allstructs(Permutation(ma), size = 3); is very slow

 

The well-known  combinat[composition]  command computes and returns a list containing all distinct ordered  k-tuples of positive integers whose elements sum to  . These are known as the compositions of  n .  For some applications, additional constraints are required for the elements of these k-tuples, for example, that they are within a certain range.

The  Composition  procedure solves this problem. Required parameters:  n - a nonnegative integer, - a positive integer. The parameter  res  is the optional parameter (by default  res is  ). If  res  is a number, all elements of  k-tuples must be greater than or equal  res .  If  res  is a range  a .. b ,   all elements of  k-tuples must be greater than or equal  a  and  less than or equal  b .  Composition(n,k,1)  is equivalent to  combinat[composition](n,k) .

 

The code of the procedure:

Composition := proc (n::nonnegint, k::posint, res::{range, nonnegint} := 0)

local a, b, It, L0; 

if res::nonnegint then a := res; b := n-(k-1)*a  else a := lhs(res); b := rhs(res) fi;

if b < a or b*k < n then return `No solutions` fi; 

It := proc (L)

local m, j, P, R, i, N;

m := nops(L[1]); j := k-m; N := 0;

for i to nops(L) do

R := n-`+`(op(L[i]));

if R <= b*j and a*j <= R then N := N+1;

P[N] := [seq([op(L[i]), s], s = max(a, R-b*(j-1)) .. min(R, b))] fi;

od;

[seq(op(P[s]), s = 1 .. N)];

end proc;

L0 := [[]];

(It@@k)(L0); 

end proc:

 

Three simple examples:

Composition(10,3); ``;   # All terms greater than or equal 0

Composition(10,3, 2);   # All terms greater than or equal 2

Composition(10,3, 2..4);   # All terms greater than or equal 2 and less than or equal to 4 

 

 

A more complex example. The problem - to find all the numbers in the range  1 .. 99999999  whose digits sum is equal to 21 .

Each number is represented by a list of digits from left to right, replacing missing digits at the left with zeros.

M:=Composition(21,8, 0..9):  

nops(M);  # The number of solutions

[seq(M[1+100000*i], i=0..9)]; # 10 solutions from the list M starting the first one

seq(add(%[i,k]*10^(8-k), k=1..8),i=1..nops(%));  # Conversion into numbers

 

Composition.mws

Greetings to all.

I am writing to alert MaplePrimes users to a Maple package that makes an remarkable contribution to combinatorics and really ought to be part of your discrete math / symbolic combinatorics class if you teach one. The combstruct package was developed at INRIA in Paris, France, by the algorithmics research team of P. Flajolet during the mid 1990s. This software package features a parser for grammars involving combinatorial operators such as sequence, set or multiset and it can derive functional equations from the grammar as well as exponential and ordinary generating functions for labeled and unlabeled enumeration. Coefficients of these generating functions can be computed. All of it easy to use and very powerful. If you are doing research on some type of combinatorial structure definitely check with combstruct first.

My purpose in this message is to advise you of the existence of this package and encourage you to use it in your teaching and research. With this in mind I present five applications of the combstruct package. These are very basic efforts that admit improvement that can perhaps serve as an incentive to deploy combstruct nonetheless. Here they are:

I hope you enjoy reading these and perhaps you might want to feature combstruct as well, which presented the first complete implementation in a computer algebra system of the symbolic method, sometimes called the folklore theorem of combinatorial enumeration, when it initially appeared.

Best regards,

Marko Riedel.

Good morning

 

I request your kind suggestion to my query cited above.

 

With thanks & Regards

 

M.Anand

Assistant Professor in Mathematics

SR International Institute of Technology,

Hyderabad, Andhra Pradesh, INDIA.

From 1 to 1000, how many time we use "5"?

1 2 Page 1 of 2