Combinatorics problems, I

This worksheet will explore some of the things MAPLE can do in combinatorics. The purpose is just to get accustomed to some combinatorics notions which MAPLE can do.

Each command has at least one example/ Question and a Problem associated to it. Solve each problem using maple.

>

> with(combinat);

[Chi, bell, binomial, cartprod, character, choose, ...
[Chi, bell, binomial, cartprod, character, choose, ...

>

Question : How many ways can 30 be factored?

Answer: 5 ways (2*3*5, 5*6, 2*15, 3*10, 30). In fact, bell(2)=5 (see below).

bell computes the nth Bell number if the argument n is an integer

The nth Bell number has several interesting interpretations, including

the number of rhyming schemes in a stanza of n lines
the number of ways n unlike objects can be placed in n like boxes
the number of ways a product of n distinct primes may be factored

Problem : How many ways can 330 be factored?

Here's how to solve the first question in MAPLE:

> factors_30:=ifactor(30);
num_factors:=nops(factors_30);
ans:=bell(num_factors);

factors_30 := ``(2)*``(3)*``(5)

num_factors := 3

ans := 5

Other facts about Bell numbers.

> Bell_numbers:=seq(bell(n),n=0..10);
series(exp(exp(x)-1),x,10);
# exp(exp(x)-1) is the "generating function" for
# the Bell numbers
add(bell(n)/n!*x^n, n=0..10);

Bell_numbers := 1, 1, 2, 5, 15, 52, 203, 877, 4140,...

series(1+1*x+1*x^2+5/6*x^3+5/8*x^4+13/30*x^5+203/72...

1+x+x^2+5/6*x^3+5/8*x^4+13/30*x^5+203/720*x^6+877/5...

>

>

Question : How many ways can you choose two numbers from {1,2,3,4}?

Answer: 6 ({1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}).

Question : What is the coefficient of x^4*y^5 in (x+y)^9?

Answer: 126. Using the binomial theorem, we must compute the binomial coefficient binomial(9,4), which is equal to 126.

binomial computes the binomial coefficients.

If the arguments are both positive integers with 0 <= r <= n, then binomial(n, r) = n!/r!/(n-r)!

which is the number of ways of choosing r objects from n distinct objects . I

If n and r are integers which do not satisfy 0 <= r <= n, or n and r are rationals or floating point numbers,

then the more general definition is used, namely

binomial(n, r) = limit(GAMMA(N+1)/GAMMA(R+1)/GAMMA(N-R+1),R=r,N=n).

Problem : How many ways can you select 10 mids from a class of 25?

Here's how to solve the first question in MAPLE:

> ans:=binomial(4, 2);

ans := 6

Here's how to solve the second question in MAPLE:

> ans:=binomial(9, 4);

ans := 126

Remember: If you have any two numbers in a row of Rascal's triangle then their sum is the number below and between them. (For example, 56+70 = 126.) You can check this down to the 9th row using MAPLE's output below:

> for n from 0 to 10 do
seq(binomial(n, i),i=0..n);
od;
Pascal's triangle :

1

1, 1

1, 2, 1

1, 3, 3, 1

1, 4, 6, 4, 1

1, 5, 10, 10, 5, 1

1, 6, 15, 20, 15, 6, 1

1, 7, 21, 35, 35, 21, 7, 1

1, 8, 28, 56, 70, 56, 28, 8, 1

1, 9, 36, 84, 126, 126, 84, 36, 9, 1

1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1

The following MAPLE command replaces each even number in Pascal's triangle by a 0 and each odd number by a 1.

> for n from 0 to 40 do
seq(`mod`(binomial(n, i),2),i=0..n);
od;
Problem : What patterns do you see?

(Nothing deep is intended here. The deeper answer is related to Gray codes, the Tower of Hanoi, ... .)

1

1, 1

1, 0, 1

1, 1, 1, 1

1, 0, 0, 0, 1

1, 1, 0, 0, 1, 1

1, 0, 1, 0, 1, 0, 1

1, 1, 1, 1, 1, 1, 1, 1

1, 0, 0, 0, 0, 0, 0, 0, 1

1, 1, 0, 0, 0, 0, 0, 0, 1, 1

1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1

1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1

1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1

1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1

1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ...

1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ...

1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ...

1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ...

1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ...

1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ...

1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, ...

1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, ...

1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, ...

1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, ...

1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, ...

1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, ...

1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, ...

1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

> binomial(12,10);

66

Question : Can you list all the ways you can choose two numbers from {1,2,3,4}?

Answer: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}.

choose returns a list/set of the combinations of the list elements. If a second argument

m is given, then only combinations of size m are generated; otherwise, all combinations are generated.

Problem : Can you list all the ways you can select 10 mids from a class of 12?

Here's how to solve the first question in MAPLE:

> ans:=choose({1,2,3,4}, 2);

{{2, 4}, {3, 4}, {1, 3}, {1, 4}, {2, 3}, {1, 2}}

>

>

>

Question : Which sum of three integers adding to 20 has the largest product? What is the value of the product?

composition computes and returns a list containing all distinct ordered k-tuples of positive integers whose elements sum to n. These are known as the compositions of n.

Problem : Which sum of four integers adding to 21 has the largest product? What is the value of the product?

Here's how to solve the first question in MAPLE:

> triples:=composition(20, 3);
L:=[]:
for x in triples do
L:=[op(L),[x,x[1]*x[2]*x[3]]]:
od:
L;
products:=seq(L[i][2],i=1..nops(L));
ans:=max(products);

triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...
triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...
triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...
triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...
triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...
triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...
triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...
triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...
triples := {[17, 2, 1], [18, 1, 1], [8, 11, 1], [7,...

[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...
[[[17, 2, 1], 34], [[18, 1, 1], 18], [[8, 11, 1], 8...

products := 34, 18, 88, 84, 78, 70, 60, 48, 34, 18,...
products := 34, 18, 88, 84, 78, 70, 60, 48, 34, 18,...
products := 34, 18, 88, 84, 78, 70, 60, 48, 34, 18,...
products := 34, 18, 88, 84, 78, 70, 60, 48, 34, 18,...

ans := 294

>

Question : How many pairs of rabbits arise from one pair in twelve months? (It is assumed that each month the female of a pair gives birth to a new pair of rabbits of opposite sexes. After its second month of life, each new pair also gives birth to a pair of rabbits each month.)

fibonacci(n) computes the nth Fibonacci number F(n), which is the number of pairs of rabbits arise from one pair in n months. The Fibonacci numbers are defined by the linear recurrence
F(n) = F(n-1) + F(n-2) where F(0) = 0 and F(1) = 1

Problem : Is the 20th Fibonacci number prime?

Here's how to solve the first question in MAPLE:

> ans:=fibonacci(12);

ans := 144

>

>

Question : What is a Gray code of length 3?

Answer: 000,001,011,010,110,111,101,100. (Note each codeword differs from the previous one by a single bit and each possible 3-tuple of 0,s and 1's occur. These properties characterize a Gray code of length 3.)

Problem : Can you find another Gray code of length 3?

Problem : What is a Gray code of length 4?

graycode computes and returns a list containing all 2^n n bit integers in a graycode order starting at zero. A graycode order is such that each successive pair of integers differ in only one bit in their binary representations.

Here's how to solve the first question in MAPLE:

> C:=graycode(3);
[seq(convert(x,binary),x=C)];

C := [0, 1, 3, 2, 6, 7, 5, 4]

[0, 1, 11, 10, 110, 111, 101, 100]

>


Last updated 5-1-2003 by wdj