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 (5)

2
votes
3answers
82 views

Combinatorics question about choosing non consecutive integers

The problem is as follows: How many ways are there to pick $6$ of the first $20$ positive integers such that no $2$ of them are consecutive? At first glance, this seems like a fairly ...
2
votes
1answer
35 views

What does “The closure of the shift-orbit of the Fibonacci word” mean?

Im trying to translate an article about rauzy fractal. But since my English is not good enough I cant understand this paragraph: ...
0
votes
1answer
17 views

Coloring 4 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself).

Coloring 4 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself). I don't think this is possible, I have done a fair bit ...
0
votes
2answers
65 views

Books on the shelf problem

The questions are: a) There are $5$ comic books, $3$ cooking books, $2$ grammar books. In how many ways can these books be arranged on a shelf if no two of the $3$ cooking books are together? b) ...
1
vote
1answer
17 views

Coloring 3 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself).

Coloring 3 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself). I don't think this is possible, I have done a fair bit ...
0
votes
1answer
36 views

Permutation (inclusion-exclusion)

2 corrected exams are being returned to each of n students. How many ways can the teacher give those 2 exams back to each student such that everyone receives at least 1 exam that is not his. I know ...
3
votes
3answers
113 views

factorials vs nCr: Does order matter in this probability problem?

The figure above shows 5 walkways, R,S,T,U, and V, leading to and from a momument. Carlos will take one walkway to the mounment and will leave by a different walkway. From how many different pairs ...
0
votes
2answers
18 views

Using algebra to solve the number of different designs can a handkerchief with 16 squares have?

Supposed we have a handkerchief of size 4x4 = 16 squares. How many different designs of handkerchiefs can we obtain using 4 different colours. I think it is just 4^16 since every square can be ...
0
votes
2answers
23 views

Generating a new password using each of (A-E) and (0-9) only one time randomly

Suppose you generate a password by randomly mixing 5 letters (A-E) and 10 numbers (0-9) in any order without replacement, producing a 15 character password. If all distinct passwords are equally ...
1
vote
1answer
19 views

What can you say about two independent events A and B in a Sample space S

If we assume that A and B are disjoint example P(A∩B) = 0, what can I say about P(A) and P(B)
0
votes
1answer
31 views

How to generalize the solution of the problem? [closed]

We have 8 boxes. Each box holds a maximum of 4 balls. We randomly place 15 balls into the boxes. What is the probability that the balls are distributed in 6 boxes?
0
votes
0answers
25 views

General solution for N apples?

Of 6000 apples, every 3rd is too small, every 4th is too green, every 10th is too bruised, and the rest are perfect. how many are too small, green, bruised, and perfect. what if there were N apples? ...
0
votes
2answers
51 views

Why do we count in two ways?

To prove combinatorial identities, I've always been taught to count in two ways. Why do we do this, rather than just use algebraic manipulations to go from one side to the other?
0
votes
1answer
52 views

Number of arrangement of six LEGO bricks

I came across a very interesting question on how many different combinations there are when you have six eight-stud LEGO bricks (with the same color). I found this article saying that there are 915 ...
2
votes
3answers
610 views

How many 90 ball bingo cards are there?

In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three ...
0
votes
1answer
39 views

Combinatorial proof (multi choose)

I'm struggling to explain why these two sides are equal in a non algebraic way. Basically I'm looking for a combinatorial proof of why these sides are equal. I know they are equal by algebra. N ...
2
votes
1answer
113 views

Permutations and number of permitted combinations three percentages which must add up to 100%

is there a simple way to find the number of combinations of three percentage values with discrete step sizes which add up to 100%? Example: ...
0
votes
0answers
19 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
2
votes
1answer
135 views

Applying derangement principle to drunken postman problem.

Two letters need to be delivered to each of n houses. How many ways can a postman deliver two letters to each house such that each house receives at least one incorrect letter? I got stuck and ...
1
vote
1answer
45 views

Evaluating a Combinatorial summation

$$aC_0bC_0 + 2aC_1bC_1 + 3 aC_2bC_2 + 4 aC_3bC_3+\cdots+a\cdot aC_abC_a$$ How to go about evaluating this? I know the basic result $$aC_0bC_a + aC_1bC_{a-1} + aC_2bC_{a-2} + ...
2
votes
2answers
52 views

Task about dice - combinatorics

We have $27$ dice. We throw them all. What is the probability to have eight $6$s, nine $5$s and four $4s$ after throwing them? ($6$s means side of the die, which has$ 6$ dots; $5$s - same but $5$ ...
2
votes
0answers
33 views

A fair game with triangular numbers?

Definition 1 A ball game is a state where you have $n$ white balls and $m$ black balls. The rule is that you remove first one ball from the cup. And without returning the first ball, you ...
0
votes
0answers
8 views

Combinations based on (2) types of an item and (3) places to obtain each of those (2) items

I am trying to validate a total number of combinations based on the following (I have placed into a hypothetical) What is know: There are (2) types of prescriptions (call them categories) and there ...
0
votes
1answer
22 views

Dimension of the set of algebraic k-forms

The number of distinct k-tuples where the indices $j_r$ are in strictly ascending order is the number of ways of choosing k distinct things from n things, so $\binom nk$. How is this true? Surely ...
0
votes
1answer
35 views

Q binomial identity

$\sum^n_{j=0 }$ $q^{n^2}$ ${n\brack j}^2$ = ${2n\brack n}$ I have been trying a few things and working with the q binomial theorem but to no avail. I found the q-Vandermonde identity that looks ...
1
vote
0answers
26 views

Does this sequence of integer products have a name?

Suppose that I have a product of, say, $n=4$ integers starting with one and ending with four $1234=4!=24$. Now I construct all products of four positive integers $1,2,3$ and $4$ with repetition such ...
1
vote
1answer
21 views

Jacobi's Four square problem using Ramanujans Summation formula

Prove that $r_4$(n) = 8$\sum_{d|n,4|d}$ d using Ramanujan's1 $\psi$1 formula. I am a little stuck here and as just wondering if I could get some advice. My work with Jacobis triple product is a ...
5
votes
0answers
46 views

Degree distribution of a graph of integer partitions

Consider a graph whose nodes are the integer partitions of $n$, connected by an edge if you can get from one partition to the other by ‘sliding one square of its Young diagram’ – that is, if one ...
4
votes
3answers
703 views

A Combinatorics question whose solution I can't understand.

The question is "For a natural number $n$, let $T(n)$ denote the number of ways we can place $n$ objects of weights $1,2,...,n$ on a balance such that the sum of the weights in each pan is the same. ...
11
votes
1answer
251 views

Upper bound for the widest matrix with no two subsets of columns with the same vector sum

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...
0
votes
3answers
21 views

Divisibility induction proof - question about fractions

I have a question about the example of divisibilty induction proof. Here's the problem [the expression must be divisible by 8]: $5^{n+1} + 2*3^n + 1 = 8*k$ I know that probably I have to proceed ...
0
votes
1answer
16 views

Running time for algorithms

Suppose i have a set $\{1,2,...,n\}$ and i know that the solution to my problem is a subset $S \subseteq \{1,2,...,n\}$. Clearly trying out all subsets in an exhaustive approach is far too time ...
0
votes
0answers
29 views

The coefficient of $t^n$ in $\left(\sum_{k=1}^{n-1} t^k\right)^r$

I'm trying to count the number of ways of writing a general natural number $n\geq 2$ as the sum of $r$ smaller numbers where each of these numbers is at least $2$ - that is, I want to count the number ...
0
votes
0answers
20 views

Solving a combinatorial problem using inclusion-exclusion

we have to make n with k integers.k integers will have to be choosen from k ranges.Every range has a minimum value and a maximum value.In how many ways we can make n according to the conditions.For ...
4
votes
1answer
72 views

Choosing subset of vertices connected to whole graph

Consider a simple graph $G$ with $n$ vertices. For any two vertices, either they are connected by an edge, or there is a third vertex which is connected to both of them by an edge. (It is possible ...
2
votes
3answers
3k views

probability of drawing different balls-combinatorics

1) Suppose that a box contains r red balls, w white balls, and b blue balls. Suppose also that balls are drawn from the box one at a time, at random, without replacement. What is the probability ...
0
votes
0answers
29 views

Algorithm Generate all labeled graphs

I'm trying to find an algorithm which will generate all labeled graphs with $n$ nodes and $n-1$ edges. It must cover trees and graphs with cycles with one unconnected node, but without multigraphs. ...
0
votes
1answer
17 views

Married couple problem for circular table, not exactly menage problem

In how many ways can we arrange n married couples around a circular table so that no person is next to her (his) spouse and no person sits next to a person of the same sex? As i see the solution of ...
1
vote
2answers
39 views

Cartesian product sets

I'm preparing a lesson on the Cartesian product of two sets and I have run into the following confusion: I understand that the Cartesian product is not a commutative operation. Generally speaking, ...
0
votes
0answers
37 views

Mathematical proof to find the length of each side of a square filled with Regular Hexagons

I have to prove or disprove that in a square box if there are full regular hexagons( whose distance from center to every corner is r) inside it, then the centers of those hexagons should lie inside ...
0
votes
0answers
5 views

Form Poset from (Non-zeta) Matrix

I have a matrix (well, really a table) of values that are the results of various indicator systems. Naturally, each system is slightly discordant, so no one true ranking exists. I'm looking to form ...
0
votes
3answers
948 views

How many positive, three-digit integers contain at least one $3$

How many positive, three-digit integers contain at least one $3$ as a digit but do not contain $5$ as a digit? I have an answer for that which is $215$ ,is that right ? If its wrong then ,how to ...
0
votes
1answer
26 views

A question about the elementary symmetric polynomial

I have asked this question and have come up with a possible answer $$ \frac{d^j}{dx^j}[\frac{(x)_c}{j!}] = e_{c-j}(x,x-1, \cdots ,x-c+1) $$ My first question is, how can I prove this? It seems trivial ...
-1
votes
1answer
42 views

Average number of tries to reach 5 successes.

So, I have a somewhat non-trivial probability question. The situation is as follows: You start off with 5 blank spots in order. In order to fill this spot, you flip a coin/any other event with a ...
3
votes
3answers
99 views

What's the probability of a straight in $5$ card poker given $5$ and $7$ of hearts?

Using a standard $52$ card deck, if you are given the $5$ and $7$ of hearts from it, what is the probability that you end up with a straight if $3$ additional cards from that same deck are given to ...
2
votes
3answers
56 views

Find all possible combinations of $A, A, A, B, B$

10 year old daughter has this problem. She knows that all possible combinations of $A,B,C,D$ are $4! = 24 $ She figured it like this: If I write down $A$ first, it has $4$ possible places. If I ...
0
votes
1answer
9 views

One more recurrence relation degree 3 problem.

If you can answer one I would be forever thankful. I'm doing them right now and I just want to check my work on here. I know you start with getting the characteristic equation x^3=6x^2-12x+8 for the ...
1
vote
2answers
59 views

Number of ways to distribute 100 identical chairs among 4 different rooms

In how many ways can 100 identical chairs be divided among 4 different rooms so that each room will have 10,20,30,40 or 50 chairs? I'm having problems coming up with the generating function for this ...
0
votes
1answer
31 views

How to solve this recurrence relation of degree 3?

I'm just wondering how to do this problem. I know I have to make the characteristic equation. Thanks
1
vote
1answer
38 views

Strategy for number of non-negative integers solutions such that $x_1+x_2+\frac{\enspace\enspace\enspace}{}+x_5 = 50$

I'm trying to figure out the number of solutions to the following problems, although I'm not entirely sure what strategy I should use to solve these. Combinations of non-negative integers ...