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.

learn more… | top users | synonyms (4)

0
votes
0answers
3 views

How many ways to get at least one pair in a seven card hand?

This was the question and answer I saw: How many different seven-card hands are there that contain two or more cards of the same rank? Solution: There are C(52,7) total hands. To subtract the ones ...
0
votes
0answers
12 views

Pattern Inventory of Tetrahedron

Determine the pattern inventory of the 3 colorings of a floating tetrahedron. Workings: \begin{array}{c|c} \text{cycles} & \text{cycle structure}\\ \hline (1)(2)(3)(4) & x_1^4\\ (1)(234) ...
0
votes
2answers
21 views

Solution to safe with six keys, largest number of people with 3 different keys each.

A safe has six locks. A group of people each receive a different set of three keys to the safe. Any two people should not be able to open the safe, due to missing at least one key. What is the largest ...
1
vote
0answers
20 views

Combinatorics with some kind of encryption

so I got this complicated question: I have a got a safe, and a group of 8 people. To every person in my group I give equal amount of keys (not necessarily the same keys tho), I want that every sub ...
2
votes
3answers
35 views

$x_1 + x_2 + x_3 \le 50$ solutions

The book shows the answer as attached. Their equation, $$x_1 + x_2 + x_3 + y = 50 \implies x_1 + x_2 + x_3 = 50 - y$$ How is that the same as solving, $$x_1 + x_2 + x_3 \le 50$$ ???
1
vote
1answer
23 views

Intriguing everyday question but can it have a mathematical answer?

Suppose we have a group of five teams playing on a soccer competition. As you know the victory is rewarded with three points, a draw with one point and a defeat with zero points. The matches are in ...
2
votes
0answers
43 views

“short” way to this combinatorics problem

I just started to learn combinatorics,i bump into this question. how many $n\in\Bbb N $ numbers that are $>65000$ and have different digits. my answer: first of we can see that we cant have a ...
0
votes
0answers
9 views

Multiplying three factorials with three binomials in polynomial identity

I have checked the following identity (1) below for $n\leq 40$ with a computer. Let $(n)_k$ denote the falling factorial $n(n-1)\ldots (n-k+1)$, let $Z_n=\sum_{k=0}^n (n)_k x^{n-k}$, and finally let ...
0
votes
2answers
28 views

Probability of equilateral and right triangle built in a cube

Having a standard cube: Show that the triangle created by any three vertices can only be equilateral or right. Calculate the probability that $3$ vertices forms a right triangle. Excluding $3$ ...
1
vote
1answer
18 views

exclusion principle / combinations problem

In a word game there are $26$ letter tiles, each one with a different letter. How many ways are there of choosing seven tiles so that at least two are vowels?
2
votes
0answers
14 views

Self-avoiding walk on lattice with minimum walk distance to adjacent cells

I have a 2-dimensional square lattice with rectangular bounds, an array if you will. I would like to find the self-avoiding walk over the whole lattice that minimizes the walk distance between cells ...
1
vote
0answers
21 views

What is the status on questions related to Bhargava's factorial function? [migrated]

In Manjul Bhargava's The Factorial Function and Generalizations he motivates a new type of factorial $n!_S$ using by generalizing a few theorems like: For $k, l \in \mathbb{Z}$, we have $k! \times ...
-2
votes
1answer
17 views

Distributing the balls to boxes.

I have a number of balls of $K$ different colors (there may be more than one ball of each color) and I want to distribute them to $N$ number of people so that each person can get at most $1$ ball. Can ...
1
vote
1answer
25 views

Determining the size of an automorphism group for a given design

I'm trying to wrap my head around the idea of automorphisms, and I'm having a lot of issues. One of the questions I've been given as an exercise is thus; Let $\mathbb{V} = \{1, 2, 3, 4, 5, 6\}$ ...
0
votes
0answers
31 views

Arranging four applicants for two supervisors

Four applicants for a job are to be interviewed for 30 minutes each: 15 minutes with each of two supervisors. (The interviews are in separate rooms, and interviewing starts at 9:00 A.M.) (a) ...
0
votes
0answers
32 views

Using Hall's Theorem to show something.

Suppose that there are five young women and five young men on an island. Each man is willing to marry some of the women on the island and each woman is willing to marry any man who is willing to marry ...
1
vote
2answers
23 views

How many different sets of 6 and 7 different numbers can we list out from 11,13,18,19,19,20,23,25? [duplicate]

How many different sets of 6 and 7 different numbers can we list out from 11,13,18,19,19,20,23,25? Please no repeating in any case, if the numbers appeared in a set are exactly the same as ...
2
votes
0answers
16 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
0
votes
1answer
23 views

Prove that for all n exist order in which will not any average

Prove that for all $n \in \mathbb N $ from $1$ to $n$ exist order in which will not any average of two numbers. For example $2,3,5,1,4,6$ is incorrect because between $6$ and $2$ is their average $4$, ...
1
vote
0answers
17 views

distribution of areas of random closed loops on a lattice

Consider a planar square lattice, i.e. ${Z}^2$. I consider the set of the closed paths on this lattice, starting and ending at some fixed base point (imposing a base point is just to avoid considering ...
1
vote
1answer
11 views

Uniform sample space confusions.

Suppose I have a box containing 3 red balls, 5 yellow ones, 2 green ones and 1 white. Suppose I take 5 balls out of the box with no putting back. Being asked about probabilities of events of specified ...
1
vote
2answers
45 views

show that at least 3 balls have same weight

You are given 49 balls of colour red, black and white. It is known that, for any 5 balls of the same colour, there exist at least two among them possessing the same weight. The 49 balls are ...
1
vote
4answers
56 views

The identity with sum of binomial coefficients

Is this formula true? $$ \sum_{m=k}^n {m \choose k}={n+1 \choose k+1} $$ If yes how to prove it?
0
votes
1answer
21 views

Number of elements of the set

Let $m$ and $M$ be positive integer numbers, $m<M$, and let $$ A=\{(\alpha_1, \alpha_2, \ldots, \alpha_k) \mid m \leq \alpha_1 < \alpha_2 < \cdots < \alpha_k \leq M\}. $$ Find the number ...
2
votes
1answer
29 views

Recursive equation with limit

Find $\alpha, \beta, \gamma$ for recursive equation: $$ \alpha a_{n+3}-3a_{n+1}+\beta a_n = 18n$$ $$a_0=0,a_1=\gamma, a_2=3 $$ $$\lim_{n\rightarrow\infty}\frac{3a_n+(-2)^{n}}{n^3}=3$$ Hey guys, ...
2
votes
1answer
27 views

Combinatorial sum inequality

Prove the following inequality: $$ \forall k\in\left\{4n+5:n\in\mathbb{N}\right\},\qquad\sum_{m=0}^{\frac{k-1}{2}}{\left( -1 \right) }^{m}\binom{k}{2m}2^{2m}\neq 1. $$ I'm particularly interested ...
1
vote
0answers
22 views

Q Pochammer Symbol Product Identities

Consider the expression $$G(x,a) = \frac{1}{((1-a)x;a)_{\infty}}$$ Based on: Infinite sum involving ascending powers It follows that in the limit as $a \rightarrow 1$ ...
3
votes
4answers
24 views

Number of sequences formed of $k$ pairwise disjoint subsets of a set of $n$ elements is $(k+1)^n$.

Let $S=\{1,2,\dots,n\}$ and $P(S)$ the family of the $2^n$ subsets of $S$. Prove that the number of sequences $(S_1,S_2, \dots, S_k )$ formed by the subsets of $S$ that verify that $S_i \cap S_j = ...
1
vote
1answer
48 views

How many 3 digit numbers can be made using the digits 1, 1, 2, 3, and 5? [on hold]

The answer is 33. But I don't know how to get there.
2
votes
0answers
46 views

Birthday problem, I'm confused by this formula

I've given the following statement (n is given, and equals 100) : Now, I'm quite confused by the second binomial coefficient: how can that represent the days for the birthdays of the remaining 98 ...
2
votes
1answer
45 views

Transcendence Degree of a field extension over $\mathbb C$

Consider the $2 \times n$ matrix $\begin{bmatrix} x_{11} & x_{12} & x_{13} & \dots & x_{1n} \\ x_{21} & x_{22} & x_{23} & \dots & x_{2n} ...
-1
votes
0answers
26 views

What's the equation for possible 2 step sequences on a 3x3 grid?

I'm starting to learn combinatorics and am having trouble with the basics. If I have a 3x3 grid, and want to calculate all the possible 2 step sequences, what's the equation? And then to build on ...
-4
votes
0answers
17 views

Probability theorem of total numbers surjective function [duplicate]

Let $A,B \subset S$ with $|A|=n ,|B|=m$ , find the number of all surjective functions from $A$ to $B$. i.e. find $|\{f: A \to B \mid f \text{ is surjective}\}|$.
2
votes
2answers
63 views

Complicated factorial expression simplification

I have $$\binom{n}{k}\binom{n-k}{j}\binom{n-k-j}{i}$$ I have it now simplified to $$\frac{n!}{i!j!k!(n-k-j-i)!}$$ I was under the impression that the multinomial number was ...
0
votes
4answers
85 views

How many ways to arrange numbers $1,\dots,n$ such that

All number left to number in place $k$ is smaller than the number in place $k$. I have started by selecting for a certain k the permutations for $1,\dots,k-1$ and multiplied it by the number of ...
-1
votes
3answers
64 views

Numbers and their magic [on hold]

How to get the possible combination of numbers to get a sum of fixed number? like $$\begin{align} 4+3+6&=13\\ 8+1+4&=13\\ 6+5+2&=13\\ 9+1+3&=13 \end{align}$$ ....and so on with $N$ ...
3
votes
6answers
96 views

Show that $\dbinom{2^{n}-1}{2^{n-1}}$ is an odd number

I would appreciate if somebody could help me with the following problem Show that $$\dbinom{2^{n}-1}{2^{n-1}}$$ is an odd number, where $n$ is a positive integer. I tried to solve this ...
0
votes
1answer
31 views

Understanding Dilworth's theorem

One formulation of Dilworth's theorem(for finite partially ordered sets) states that : There exists an antichain A, and a partition of the order into a family P of chains, such that the number of ...
0
votes
1answer
30 views

Ramsey numbers: if $s_1 \leq s_2$ then $R(s_1,t)\leq R(s_2,t)$

I'm doing this little homework assignment on Ramsey numbers, the question is: Show that $$s_1 \leq s_2 \Rightarrow R(s_1,t)\leq R(s_2,t).$$ I've tried classifying it into these four cases: The ...
2
votes
1answer
58 views

Notions of consistency / heterogeneity in sets of vector values

The problem Let us consider a row vector u of size $n\in\mathbb{N}$, containing only binary values (0,1): $$u=(u_1,...,u_n), n\in\mathbb{N}$$ $$\forall i \in \{1...n\}, u_i \in\{0,1\}$$ I would like ...
2
votes
2answers
76 views

Count the A's in a sequence

We define a sequence of words as follows: Let $S_0=a$, and for $n≥1$, to obtain $S_n$, we replace each instance of $a, b,$ and $c$ in $S_{n−1}$ simultaneously with $ab, ac,$ and $a$, respectively. The ...
0
votes
2answers
37 views

Ways to arrange 4 different colour balls with no two of the same colour next to each other

I have n green balls, n blue balls, m red balls, m yellow balls. How many ways are there to arrange this such that we don't have an sequence with 2 of the same colour next to each other? I don't ...
-1
votes
0answers
26 views

If X is Describe what the Chebyshev inequality says about… [on hold]

If X is a random variable with E(X) = 367 and V ar(X) = 25, then describe what the Chebyshev inequality says about a. P(|X − 367| ≥ 10). b. P(|X − 367| ≥ 50).
1
vote
0answers
47 views

Question about inclusion exclusion and gcd

For $d_1,\ldots,d_k\in\mathbb{N}$ define $$ L(d_1,\ldots,d_k) = \sum_{j=1}^k (-1)^{j+1}\sum_{1\leq i_1<\ldots<i_j\leq k} gcd(d_{i_1},\ldots,d_{i_j}). $$ Given two integers $n,m$ let $[n,m]$ ...
3
votes
0answers
31 views

Maximum number of points you can put on grid $ n\times m$ with no equidistant?

Assume we have a grid of $n\times m$ points. and the distance between two rows or two columns is 1 ( unit ). I have a couple of questions related to this grid:- What is the list of possible length ...
1
vote
3answers
31 views

Prove that any finite non-empty set X has the same number of subsets of even size as it has subsets of odd size?

I'm trying to prove that any finite non-empty set X has the same number of subsets of even size as it has subsets of odd size but finding it quite difficult to form a rigorous argument. I have come ...
7
votes
0answers
35 views

Solution to $x(128)x=(12365)(479)$ in $A_9$, the alternating group

This isn't homework. I'm wondering if anyone knows techniques besides trial and error to find $x$ or show there is no solution, to problems like this, or worse, say $xpx^2rx^{-4}=s$, where $p$, $q$, ...
3
votes
0answers
44 views

Number of subgraphs in the ladder graph

Assume you have the usual (in both directions infinite) ladder graph. I can try to provide a picture if needed. Further assume the vertices are labelled and I have one distinct vertex (call it the ...
1
vote
1answer
28 views

Pascals Identity

Let there be a group of n boxers and we want to select k people out of it, suppose one of the persons name is ‘Prem’ , so no of ways to choose k people = (combinations in which Prem is present + ...
2
votes
0answers
23 views

Proof about the size of a particular given set.

Okay so I'm working on this question: I have done the first bit and parts i) and ii) getting answers $20 \choose 10$, $10!$ and $10 \choose 2$ as my answers respectively. I'm stuck on the part iii) ...