This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

0
votes
0answers
16 views

Combinations - picking from groups of (different) identical items

First of all, I apologize if a similar question has been asked before. I did some searching and couldn't find anything here, but there might be an answer floating around somewhere. Basically, this ...
0
votes
2answers
26 views

How many sequences of $k$ elements in ascending order from a set $S$?

Suppose I have a set $S = \{1,2,\ldots,n\}$. How many sequence $r$ contains $k$ elements from set $S$ in ascending order if: $r$ contains repetition, i.e. an element in $S$ can appear several time ...
1
vote
0answers
15 views

Number of combinations of length

Basically I have a urn with balls in different colors. For example $urn = \{r, r, r, b, b, y\}$ How many different outputs (order matters) if I take 3 balls. The answer is $\#\{rrr, rrb, rry, rbr, ...
2
votes
2answers
30 views

The Number of Increasing Vectors $(x_1,…,x_k)$ Satisfying $1 \leq x_i \leq n$ and $x_1 < x_2 <…<x_k$

I want to find the number of increasing vectors $(x_1,...,x_k)$ satisfying $1 \leq x_i \leq n$ and $x_1 < x_2 <...<x_k$. Examples of vectors satisfying these conditions Let $n =5$ and ...
0
votes
0answers
9 views

Trying to prove that the poset of partitions ordered by refinement is a lattice

I am brand new to lattices/partitions. Given that the set of all partitions of a finite set is a poset ordered by refinement, how does one prove that it is a lattice? I know you have to prove that the ...
0
votes
1answer
28 views

computing length of integer partitions

This is a two-part question. (no pun intended) Part 1 I need to compute the length of each possible partition of an integer $n$. One possible way is to first compute all the partitions and the just ...
0
votes
0answers
11 views

Counting the exact number of sets in the Borel Field generated by a collection of “unrelated” sets

Prove: The B.F. generated by n given sets "without relations among them" has $2^{(2^n)}$ members. To be perfectly clear, "without relations among them" means that no set in the generating ...
0
votes
1answer
25 views

Giving a closed expression to $\sum_{i=0}^b (-1)^{b-i} \binom{b}{i}\frac{1}{a+b-i}$

I want to prove $\sum_{i=0}^b (-1)^{b-i} \binom{b}{i}\frac{1}{a+b-i} = \frac{(a-1)! b!}{(a+b)!}$ yet I feel like I don't know how to even approach this problem. Any hints are welcome.
1
vote
0answers
6 views

If there is a subset with sum divisible by n, then take out an integer of the subset. How many moves?

Fix an integer $n \ge 2$. A finite set $A \subset \mathbb{N} $ is given. Define $ s(X) = \sum_X x $, where $ X $ is a finite set. We know that $n \mid s(A)$. We can do just one move: if there is a ...
5
votes
4answers
64 views

Calculate the binomial sum $ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i} $

I need any hint with calculating of the sum $$ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i}. $$ Maple give the strange unsimplified result $$ I_n={\frac {1/12\,i\sqrt {3} \left( - \left( \left( ...
0
votes
1answer
14 views

Number of sequences with n digits, even number of 1's (Continued question)

Some guy asked a very interesting question here before. He was trying to figure out a formula to calculate $a_n$ number of sequences with n digits from $\{1,2,3,4\}$ and an even number of 1's. Which ...
0
votes
0answers
17 views

The Number of Binary Vectors Who's s Sum is Greater Than $k$

I want to determine the number of vectors $(x_1,...,x_k)$, such that each $x_i$ is either $0$ or $1$ and $$\sum\limits_{i=1}^n x_i \geq k$$ My Approach The number of $1$'s range from a minimum of ...
0
votes
0answers
35 views

Combinations of dots in a circle excluding neighbors [duplicate]

How many subsets with $k$ elements do $n$ dots put in the shape of a circle have, which do not include any neighbouring dots?
1
vote
2answers
28 views

A committee of four people, containing at least one man and one woman, must be chosen from four men and three women.

A committee of four people, containing at least one man and one woman, must be chosen from four men and three women. How many different committees are possible? I dont really now how to solve this. I ...
0
votes
3answers
47 views

Inclusion exclusion to solve $x_1+x_2+x_3=15$ with conditions

How to do this using inclusion/exclusion? Number of integers solutions to the equation $x_1+x_2+x_3=15$ with $x_1,x_2\leq 5$ and $x_3\leq 7$ for non negative integers $x_1,x_2,x_3$ I can do this ...
1
vote
3answers
29 views

How to find the total number of drinks possible

If I sold coffee in 4 sizes (small, medium, large, and extra large) and 4 varieties (Kenyan, Sumatran, Kona, and Columbian). Customers can choose to add one or more syrups that come in 5 flavors ...
0
votes
1answer
28 views

General Problems, Combinatorics. [on hold]

What is the most important class of combinations problems one can be asked at a Mathematics Olympiad? Also, here's one question I've encountered. How many parallelograms can be found in a equilateral ...
0
votes
3answers
57 views

Probabilities related to the sum of four dice

Suppose we have 4 fair six-sided dice of different colours and faces numbered 1,2,...,6 are rolled independently. (a) How many ways can a total of i. 4 ii. 5 iii. 6 be obtained? (b) Compute (to ...
1
vote
2answers
33 views

Generating function for number of integer solutions, no computer

How do you solve a Generating function for the number of integer solutions with no computer? Use a generating function to solve the number of integer solutions for $$x_1+x_2+x_3=17$$ Where ...
1
vote
0answers
18 views

Number of distinguishable arrangements of the word INDOOROOPILLY with three different conditions

I have the following three questions on a past final exam, I wanted to ask if I have done everything correctly. Thank you! How many distinguishable arrangements are there for the letters of the ...
1
vote
1answer
44 views

Question concerning a sequence in GAP

I would like to know, what's the best (fastest) way to programm the following in GAP (perhaps using some functionality from the QPA package): Input: $n\geq 2$ Output: A list of all sequences ...
0
votes
1answer
16 views

We are given a 15 bit string which must contain exactly 9 0's and 6 1's. Every 1 to be followed by a 0. # of possibilities to place the remaining 0s?

We are given a 15 bit string which must contain exactly 9 0's and 6 1's. Every 1 to be followed by a 0. # of possibilities to place the remaining 0s? I believe the answer is (3+7-1) choose 3 as I set ...
0
votes
0answers
28 views

Generating function to calculate number of ways of distributing $10$ or less items to $3$ people.

There is a container of 10 identical chocolate frogs and three students, Adam, Bob, and Charles, are to be given some of these chocolate frogs, but not necessarily all of the chocolate frogs. ...
0
votes
1answer
35 views

Counting in two ways

I've been having trouble proving the following equivalence. I suspect a two-way counting method is sufficient. Could anyone shed some light? $$\sum_{i=0}^{m}{ \binom{n-i}{m-i} \binom{k+i}{i}} ...
2
votes
0answers
30 views

Geometric Generating Functions

Let $p(t) = t^3 + Ft^2 + Et + V$, where $F,E,V$ are the number of faces, edges, and vertices of a cube, respectively. Factor $p(t)$ and explain your results in terms of generating functions. A hint ...
0
votes
1answer
33 views

How many elements does $\mathcal{P}(A)$ have?

Let $A$ be a set of size fifteen. Let $\mathcal{P}(A)$ denote the power set of $A$, that is the set of all the subsets of $A$. How many elements does $\mathcal{P}(A)$ contain? This is the same as ...
-1
votes
0answers
28 views

Is there a binary [10,6,4] code?

Using the sphere padding bound formula I can conclude that 1 + 12 + 66 $\ge$ $2^{6}$ which indicates that there MAY be a binary [10,6,4] code, however I cannot prove that there is. How can I come to ...
0
votes
1answer
24 views

Sum of products of binomial coefficients is equal to another binomial coefficient [duplicate]

Need help in proving (by induction or by combinatorics) the following statement Is it possible to do it by induction? there are 3 veriables and I think I cannot easily do it by induction. Correct? ...
0
votes
0answers
15 views

Finding a parity check matrix of a binary code

I'm supposed to find a parity check matrix of a binary [6,3,3] code. Given a generator matrix G i can find a parity check matrix by row reducing until I get the identity matrix, then take -A^{\top} | ...
0
votes
1answer
34 views

Intuition behind $t(t+1)(t+2)\cdots(t+n-1)$

We have the following formula: Let $t$ be indeterminate and fix $n\geq 0$. Then \begin{equation} \sum_{k=0}^n c(n,k)t^k = t(t+1)(t+2)\cdots(t+n-1) \end{equation} where $c(n,k) = \#$ of permutations ...
0
votes
1answer
18 views

Paths in rectangular grid. Need some help with the logic behind it.

Suppose I have a an ixj grid (i rows, j columns) From the bottom left, to the top right, you may only move UP or RIGHT, how many paths are there from A to Z. In this case, you must go up twice, ...
2
votes
1answer
28 views

Combinatorial Analysis: Fermat's Combinatorial Identity

I was looking through practice questions and need some guidance/assistance in Fermat's combinatorial identity. I read through this on the stack exchange, but the question was modified in the latest ...
-3
votes
1answer
29 views

Alphabets Problem [on hold]

in the English alphabets of capital letters there are 15 stick letters which contain no curved lines, and 11 round letters which contain at least some curved segment. How many different 3 letters ...
5
votes
0answers
41 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
1
vote
1answer
28 views

Intuition behind combinatorics problems?

I have a hard time understanding when a problem is a combination or permutation. Especially when using the multinomial theorem. For example: three boxes numbered 1,2 and 3 for k = 1 2 and 3, box k ...
0
votes
0answers
8 views

Proof: Generalized Version Of The Basic Counting Principle

The Generalized Basic Principle Of Counting If $r$ experiments that are to be performed are such that the first one may result in any of $n_1$ possible outcomes; and if, for each of these ...
6
votes
1answer
57 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
0
votes
1answer
76 views

Cut squares from sheet

A rectangular paper sheet of M*N is to be cut down into squares. ...
1
vote
1answer
39 views

How can I calculate $ \sum_{j=0}^{49}\binom{100}{2j+1}p^{100-(2j+1)} q^{(2j+1)} $?

I got the following formula when I tried an exercise in probability: $$ \sum_{j=0}^{49}\binom{100}{2j+1}p^{100-(2j+1)} q^{(2j+1)} $$ where $p+q=1$. These are the "odd" terms in the expansion of ...
0
votes
0answers
3 views

Graphing ratios; non-common denominators for different data series in the same category?

I'm developing custom graphing software for a client and they have a need that doesn't make sense to me mathematically and I was hoping someone could help. They will be graphing the ratio of scrapped ...
1
vote
1answer
42 views

Finding maximum no of $1$'s

We are given a matrix $A \in M_n (F)$ such that all its entires are either $1$ or $0$. I need to find the maximum number of $1$'s that can be in matrix $A$ so that it is still invertible. My try : ...
0
votes
0answers
30 views

Distributing balls in boxes.

In how many ways can $n$ identical balls be distributed amongst $m$ different boxes given that a box can have any number of balls(from $0$ to $n$)? What I've tried is using multinomial theorem to ...
0
votes
0answers
23 views

Permutation Inversion Question [on hold]

Show that the number of permutations of {1,...,n} with k inversions is equal to the number of permutations of {1,...,n} with (n choose 2)-k inversions.
2
votes
1answer
44 views

More Generating Functions problems

(a) For this problem, define a nonstandard die as a 6-sided die that is equally likely to come up on each side, but has a different set of numbers than the usual 1,2,3,4,5,6 on its sides. A standard ...
3
votes
0answers
25 views

placing chess knights in a numbered chessboard.

Suppose you have a square board where the number on the square in column $i$ and row $j$ is $(j-1)8+i$ you have to place knights on the board so no two knights threaten each other and the sum of the ...
1
vote
1answer
19 views

Simpler formula for number of ways to pair up (or not ) $2n$ objects?

We can see that the number of ways to pair up $2n$ people is $(2n-1)!!$. But I want to calculate the number of ways to pair up those people where not necessarily all the people are paired. By summing ...
2
votes
1answer
44 views

How can I simplify $ \sum_{r=0}^{m-1}r^3\frac{\binom{m}{r}(m-r)!\begin{Bmatrix} n\\ m-r \end{Bmatrix}}{m^n}$?

Let $N$ and $M$ be sets with $n$ and $m$ elements respectively with $n>m$. Randomly assign a function $f:N\to M$. Suppose that the probability of each element in $N$ being assigned to any ...
-4
votes
0answers
25 views

Points on the sides of an equilateral triangle are colored in two colors. [on hold]

Do there exist on the perimeter of the triangle three monochromatic vertices of a right-angled triangle?
1
vote
1answer
24 views

raBinomial distribution with dependent trials?

I need your help with following problem: String with n characters is given. For each character in string there is probability p that it is wrong. Now you take a sliding window of length k, k<= n, ...
-2
votes
0answers
22 views

36 play in groups of 4 each day. No two play together more than once in a 5 day tournament. [on hold]

I have 36 golfers broken down into 9 groups of 4 golfers each. All 36 golfers are playing a round of golf each day over 5 consecutive days. How do I calculate combinations that ensures no 2 players ...