For 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. Combinatorics is a ...

learn more… | top users | synonyms (4)

0
votes
1answer
30 views

What is the expression for the set of all nonduplicate subsets for k-many elements?

For k-many elements, is the power set, ℘, 2^k? If so, it would seem that the power set would included ordered pairs that, if unordered, would be duplicates (e.g., {3,1}; {1,3}. What then would be the ...
0
votes
1answer
78 views

Combination problem involving multiple conditions

From a group of 12 students, 8 are to be chosen for an excursion. There are 3 students who decide that either of them will join or none of them will join. In how many ways can the 8 be chosen? Here ...
2
votes
1answer
45 views

Relations counting in two sets

I have two sets $A=\{1,2,3, 4\}, \ B=\{5,6,7,8,9\}$. I wanted to count the relations from $A$ to $B$ that didn't include $1$ in their domain. First i did it like this: $2^{20} - 2^5 + 1 = ...
2
votes
3answers
69 views

In how many options can one cast 10 game cubes in different colors so that all the digits 1,2,3,4,5,6 will apear?

I study discrete and I missed some lessons. Can you help? The problem: We have 10 game cubes, each in a different color. The question is what is the number of options to throw all the 10 cubes and ...
14
votes
3answers
2k views

How many knight's tours are there?

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, ...
3
votes
1answer
64 views

Are there $4$ sets such that the sum of the two numbers are equal?

For each set of $117$ different $3-$ digit natural numbers,can we choose $4$ disjoint sets with $2$ elements $A,B,C,D$ with the identity:the sums of the two numbers of each set are equal? How can I ...
0
votes
1answer
67 views

Pigeonhole principle in practice?

Does one have an example of how to calculate stuff using the Pigeonhole principle? Lets say I have 200 students that are doing a test(with a grade from 0-100) how can I know how many(minimum) will ...
0
votes
2answers
45 views

Improving an algorithm for defining a matrix

I am making a program of combinatorics. There is a step where I give an integer n and I want n positive or zero integers $a_i$ so that $\sum \limits_{i=0}^{n-1} a_i=\frac{n(n-1)}{2}$. I would like ...
2
votes
3answers
143 views

Constrained combinations of balls in jars

Not sure how to solve the following problem. Imagine we have balls of $n$ different colors. There are $m$ balls of each color, so in total we have $nm$ number of balls. The question is how many ...
1
vote
1answer
177 views

Number of binary strings containing at least n consecutive 1

Let $Z_{m, n, q}$ be the number of binary strings (ordered lists of 0's and 1's) of length $m$, containing exactly $q$ 1's and at least $n$ consecutive 1's at any part of the string. I'm trying to ...
3
votes
1answer
61 views

Ranking between two strings

For the word "BOOKKEEPER". It's sorted representation is "BEEEKKOOPR" How can I find the different permutations of the word between "BEEEKKOOPR" and "BOOKKEEPER"? similar example: For "BBAA" ...
2
votes
3answers
45 views

Permutations with repetitions - which is k and which is n?

I am learning permutations with repetitions, and working with the formula that $P(n,k)=n^k$. I understand the logic that with repetitions, we multiply $n$ by itself $k$ times. But in different ...
4
votes
2answers
188 views

Sum of Stirling numbers of both kinds

Let $a_k$ be the number of ways to partition a set of $n$ elements $orderly$,which means that order of subsets matters, but order of elements in each subset does not. My task: Prove, ...
5
votes
1answer
105 views

Using Plancherel's Theorem to Prove the Gauss Sum

I'm interested in proving the following: Where $p$ is an odd prime and $z$ is a primitive $p$th root of unity, we let $Q(p)=\sum^{p−1}_{k=0}z^{k^2}$. Prove: $|Q(p)|=\sqrt{p}$. Specifically, I want ...
2
votes
0answers
52 views

Kleitman's Theorem on downsets

So I'm trying to prove Kleitman's Theorems, that if $\mathcal{A}, \mathcal{B} \subset \mathcal{P}(n)$ are downsets, then $|\mathcal{A} \cap \mathcal{B}| \geqslant ...
1
vote
2answers
73 views

Intuitive explanation for Factorial of negative fractional number

How to find out factorial of negative fractional numbers.Does this make any sense..I don't understand..Can Anybody give an intuitive explanation..
1
vote
2answers
75 views

How many relations can we form from A to B?

We have two sets for example: $A = \{1,2,3,4 \}$ , $B = \{5,6,7,8,9\}$. How many relations do we have from $A$ to $B$? (What is the formula?)
0
votes
1answer
27 views

Count relations in a specific domain

I have two groups $A=\{6,7,8,9\}, \ B=\{1,2,3,4,5\}$. I want to count how many relations there are from $A$ to $B$ which obey to the rule: $\{6,7,8\}\subseteq \text{domain}(k)$ * k is the ...
0
votes
1answer
36 views

probability of finding a small sequence within a larger sequence

I'm wondering how to define the probability of a long string LS (using 26 letters alphabet) to contain a smaller string ss. Right know I have something like this. Number of LS containing ss: 26^( ...
0
votes
2answers
56 views

How many rows will we draw in Hasse diagram?

Hi i have a finite group in a size of N and i need to know how many lines can i draw based on N in a Hasse diagram(ordered by inclusion like in the examples). In the first example(N=3) we have 12 ...
1
vote
0answers
52 views

Closed form expression sum-product of binomials

Is it possible to find a closed form expression for $$\sum_{j=1}^a\sum_{i=1}^{b} {i+j-1\choose j} {i+j-1\choose i},$$ where $a \geq 1$, and $b \geq 1$ are integers. I couldn't apply any type of ...
0
votes
1answer
47 views

Random Graphs correlation inequalities

Is there anywhere i can find a proof of the first inequality that $$P(B_{i}| \cap_{j \in J} \bar B_{j}) \leq P(B_{i})$$ It is on page 13 and is the first inequality presented at the start of section 2 ...
-1
votes
1answer
65 views

What is the number of the solution of the following equation a+b+c+d+e = 18? [duplicate]

What is the number of integral solutions to the following equation? $$ a+b+c+d+e = 18 $$ Here, $a,b,c,d,e$ all are variables and can take zero and positive integers values. That means $a,b,c,d,e$ ...
0
votes
4answers
57 views

Counting additive decompositions of $32$ with some restrictions

Does anyone know how to do this following question using a "change of variables"? Q:Determine the number of integer solutions of $x_1 + x_2 + x_3 + x_4 = 32$ where $x_i ≥ -2, 1 ≤ i ≤ 4$. So I've ...
0
votes
2answers
43 views

With how many ways can we arrange the numbers?

With how many ways can we arrange the numbers $1, 2, \dots, 15$ so that at each position that is a multiple of $3$, there is an even number. My idea is the following: $$ \frac{10!}{7! \cdot 2!}$$ ...
1
vote
2answers
39 views

combinations and permutations - choosing when there's a limit

A kid can choose 7 out of 12 donuts to eat. How many ways can he do this if he must choose at exactly 3 of the first 5? Similarly, how many combinations are there if he must choose at least 3 of the ...
0
votes
2answers
54 views

Combinations and permutations when separating into groups

If I have 30 people and I want to form them into 3 groups. One of size 10, one of size 5 and one of size 15. How many ways can I do this? Similarly what if I have 15 boys and 15 girls and the 10 ...
1
vote
2answers
186 views

Generating function for planted planar trees

I need your help to solve this problem : Give a generating function for planted planar trees with all degrees odd. Show that the number of such trees with $2k+1$ non-root vertices is ...
6
votes
2answers
541 views

Stirling Number of the Second Kind Identity

I'm aware of the identity \begin{align} \sum_{i = 0}^{k} i! \binom{n+1}{i + 1} S(k,i) = H_{n,-k}, \end{align} where $H_{n,-k}$ is a generalized Harmonic number defined by $H_{n,m} = \sum_{r = 1}^{n} ...
2
votes
2answers
76 views

Finding the Generating Function for $\sum_{n_1 +n_2 + \ldots + n_k = n} n_1 n_2 \cdot \ldots \cdot n_k$

I'm studying problem 2.6 (p. 65) in Herbert Wilf's generatingfunctionology (released by the author for free online). This problem actually has a solution already written in the back of the book (p. ...
1
vote
1answer
115 views

Deranged Twins: Number of ways to derange n+2 objects where 2 objects are indistinguishable.

This is exercise 12, page 163, Harris, Hirst and Mossinghoff, "Combinatorics and Graph Theory". Suppose n+2 people are seated behind a long table facing an audience to staff a panel discussion. Two ...
2
votes
0answers
72 views

Puzzle with character order

Suppose I have 3 letters a, b, c and I want to find the minimum length of a string that uses all the double combinations of the aforementioned letters. How should I do it or how are such problems ...
1
vote
2answers
207 views

How many subsets has the set $\{ 1, 2 , \dots, n\}$?

How many subsets has the set $\{ 1, 2 , \dots, n\}$ that don't contain two consecutive naturals? My idea is the following: $$\displaystyle{2^{\frac{n}{2}}}$$ because we can't from $n$ numbers, we ...
2
votes
1answer
72 views

Is there a combinatorial explanation for this identity related to Kraft's inequality?

Kraft's inequality involves the quantity: $$\sum_{x \in X} \frac 1 {b^{\ell(x)}} \tag 1$$ Where we are considering a code mapping symbols in the alphabet $X$ to strings in an alphabet of $b$ ...
2
votes
2answers
94 views

With how many different ways can Adriana be dressed…????

Adriana will be examinated in $5$ subjects, one at each day.She has $5$ dresses in different colors: red-blue-green-white-yellow. On Monday she does not want to wear the blue or green one. On ...
1
vote
1answer
37 views

Number of surjections with injective restrictions

Given a partitition of an $n$-element set $N$ into subsets of size $(n_i)_{i=1\ldots,k}$ and an $m$-element set $M$. How many surjections $N\rightarrow M$ are there such that the restriction to each ...
2
votes
1answer
85 views

Probability distribution of the area covered by random circles

Does anybody know of there are any asymptotic results on the probability distribution of the area covered by $n$ random circles in the unit square with radius $r=r(n)$? I believe results on the ...
0
votes
2answers
30 views

How many of these numbers contain the digits $3$ and $5$?

Suppose that repetitions are not allowed. There are $6 \cdot 5 \cdot 4 \cdot 3 $ numbers with $4$ digits , that can be formed from the digits $1,2,3,5,7,8$. How many of them contain the digits $3$ ...
0
votes
0answers
35 views

Counting the 1s in each row of the incidence matrix of a 2-design

Consider the $2 - (4t-1, 2t, t)$ design where $t$ is an odd number and $A$ is the incidence matrix. I suspect that the number of elements with value $1$ in each row of $A$ is equal to $2t$ but I can't ...
1
vote
3answers
123 views

Can we find two mutually orthogonal diagonal latin squares of orders $4$ and $8$?

Can we find two mutually orthogonal diagonal latin squares of orders $4$ and $8$? A diagonal Latin square is a Latin square of order $n$ where the symbols $1$ thru $n$ fil both the forward diagonal ...
1
vote
1answer
38 views

On a pandiagonal Latin square, what is a broken diagonal?

After reading "No pandiagonal latin squares with order divisible by 3?" I didn't understand what a "broken diagonal" is. Thanks
1
vote
1answer
130 views

How large can the internet be?

How many unique URLs can there possibly be on the internet? I read this question on stackoverflow regarding the maximum limit of a URL. The shortest URL would be x://www.x.x/ which is 12 characters ...
0
votes
1answer
80 views

How many permutations of the sequence 1, 2, 3…N where none of the first K numbers in the original sequence is in it's place?

For the sequence 1, 2, 3 ... N there are of-course N! permutations. But for a given K, where 1 < K ≤ N how many permutations are there given none of ...
0
votes
2answers
225 views

combination GRE problem 25

An appliance's model number consists of three alphanumeric characters. The first character must be one of 24 permissible letters of the alphabet. The next character is numeric, a digit from 1 to 9. ...
1
vote
2answers
49 views

Creating two groups where two people can't be in the same group.

If you have a group of $12$ men and $10$ women, and you need to make two groups - one with $6$ people and the other with $9$, the ways to form such groups would be $${22 \choose 6}\cdot {16 \choose ...
2
votes
2answers
299 views

Creating groups with 10 men and 10 women.

I once made a question here: Creating teams with exactly two men and one woman, where the order matters., and the answer worked just fine, although I was still a bit confused. Here is an exercise that ...
1
vote
1answer
43 views

Creating digit sequences that can't begin with $0$, but one digit must repeat exactly once.

Is my reasoning OK here? My doubt is mainly on the second part of this problem. How many 6-digit sequences are there with exactly 1 digit repeated? So, we have 6 slots: $$\_ \ \ \_ \ \ \_ \ ...
3
votes
1answer
64 views

Creating teams with exactly two men and one woman, where the order matters.

Suppose that there are $5$ men and $4$ women. How many ways are there to make a group of three members? Well then $${9 \choose 3}$$ Now, let's say that now you're making teams, and the order does ...
1
vote
1answer
41 views

Choosing two colours of different tones.

You have $5$ tones of orange, $7$ of green and $4$ of purple. You want to choose two colours of different tones. How many choices do you have? Orange and green $$5\cdot7$$ Orange and ...