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
2answers
24 views

How many combinations in this 4 digit pin

The pin code is 4 digits between 0-9 Can be entered in any order e.g 1234 4231 1324 will all work has no repeating numbers writing them all out i have 194 codes to try. however the math gives me ...
0
votes
1answer
14 views

Finding number of quadruples in an array whose XOR is 0

If an array of n elements is given and I need to find the number of quadruples whose XOR = 0. I need to do this in very efficient way. Please help.
3
votes
2answers
27 views

A club has 14 members. In how many ways can a president, vp, and treasurer be chosen if two specified club members refuse to serve together.

What I have so far. There are ${14 \choose 2}$ ways to choose a pair that will not serve together. If two members refuse to serve together, then there are 12 remaining club members to place into 3 ...
6
votes
0answers
49 views
+100

Integer Partition Refinement in Sage

A partition of an integer $n$ is a non-decreasing list of positive integers summing to $n$. For example, $3$ can be partitioned as $1 + 1 + 1$, $1 + 2$ or just $3$, but $2 + 1$ is indistinct from $1 + ...
0
votes
1answer
25 views

How many non-repetitive instances can a $1$ to $14$ cars park in $14$ park spaces.

Here are the $14$ park spaces. 1 car has 14 possible spaces now how many possibilities does $2,3,4,5,6,7,8,9,10,11,12,13,14$ cars have.
1
vote
3answers
32 views

Probability of reaching net 4 heads when tossing coin 8 times

This problem is #19 from the AMC 12 2016A, and goes as follows: Jerry starts at $0$ on the real number line. He tosses a fair coin $8$ times. When he gets heads, he moves $1$ unit in the positive ...
4
votes
1answer
240 views

Number of solutions to $a_1 + a_2 + \dots + a_k = n$ where $n \gt 0$ and $0 \lt a_1 \leq a_2 \leq \dots \leq a_k$ are integers.

I know how to find the number of solutions to the equation: $$a_1 + a_2 + \dots + a_k = n$$ where $n$ is a given positive integer and $a_1$, $a_2$, $\dots$, $a_n$ are positive integers. The number ...
1
vote
1answer
53 views

Number of integer solutions to $a_1\ge a_2\ge\ldots\ge a_i\gt 0$ such that $a_1+a_2+\ldots+a_i=n$

What is the number of (positive) integer solutions of: $$a_1+a_2+\ldots+a_i=n$$ where $a_1 \ge a_2 \ge \ldots\ge a_i\gt 0$ ? Also, the order of summands does not matter.
1
vote
0answers
4 views

Show that there is a STS(n) if exist one 1-Error-Correcting Code.

STS(n) is 2-(n, 3, 1) design that every two elements appear in exact one block. and the size of every block in STS(n) is 3. if you are not familier with Error corectiong codes you could see also: ...
0
votes
1answer
38 views

How many sequences $a_1,a_2,…,a_n$ in length $k$ so $a_i \in \{1,2,3,4…,n\}$ satisfy

I have the follow two questions : How many sequences $a_1,a_2,...,a_n$ in length $k$ so $a_i \in \{1,2,3,4....,n\}$ satisfy : 1) $a_1<a_2<....<a_k$ while $(a_{i+1} \neq a_i+1)$ 2) $a_1 ...
0
votes
1answer
12 views

prove that the minimum number of trails in an odd graph is n/2

In my HW assignments I was asked to prove that If a graph G consists of only odd degree vertices, then the minimum number of trails that decompose it (without having any common edge between each two ...
1
vote
1answer
37 views

how many numbers drawn more than once

There are 100 numbered balls in an urn. We make 100 random draws with replacement. Of course, we can not expect to draw every number exactly once, there will be multiples. What is the expected value ...
0
votes
1answer
58 views

Proof using the product lemma

Let $S$ be the set of all finite subsets of $\mathbb N = \{1,2,3,...\}. $ We define a weight function $w$ where for a subset $X$ of $\mathbb N, w(X)$ is the sum of all the elements in $X$, with ...
0
votes
0answers
8 views

An extemal combinatorial design question. “Weak” steiner stystems.

A Steiner system $S(t,k,\nu)$ is a collection $X$ of $\nu$ points and a collection of subsets of $X$ of size $k$ (frequently called blocks) such that each $t$ element subset of $X$ occurs in exactly ...
4
votes
1answer
34 views

A subset of the set of numbers of seven non zero digits

Someone visits me knowing that I'm indisposed for now. Courteously, brings me a problem without imagining it is on my “bête noir”, Combinatorics. I post it with its solution, 151200, I think am ...
7
votes
3answers
276 views

Combinatorial formulas and interpretations

I found that $$ \sum_{j=0}^{s}(n-s+j)!\binom{s}{j}(s-j)! =s! \sum_{j=0}^{s} \frac{(n-s+j)!}{j!} = \frac{(n+1)!}{n+1-s}$$ I proved this formula with induction, but I was wondering if there is a ...
3
votes
1answer
29 views

Smallest number of $n$-simplices in a triangulation of the sphere

Let $X$ be a simplicial complex homeomorphic to $S^n$. I proved that there must be at least $(n+2)$ vertices in $X$ and that there must be at least one $n$-simplex in $X$. Now I want to prove that ...
-1
votes
0answers
41 views

Combinatorics :: In how many ways can ten boys and four girls sit in a row? [on hold]

(1) (a) In how many ways can ten boys and four girls sit in a row? $$= 14!$$ (b) In how many ways can they sit in a row if the boys are to sit together and the girls are to sit together? ...
1
vote
2answers
29 views

What is the name of this (possibly classical) combinatorial optimization problem?

I have a finite number of sets $S_i$, each of the sets costing $p_i$ and containing some elements. Given the budget $b$ I want to select number of those sets to maximize $|S_{k_1} \cup S_{k_2} \dots|$ ...
0
votes
0answers
9 views

Equality of Quotients of Probabilities from Combinatorics

Sorry the title is so vague - I don't know how else to ask this. Essentially, what is a real-life example showing why: $\frac{_aC_k}{_nC_k}=\frac{_aP_k}{_nP_k}, where \ a<n$ is true?
0
votes
0answers
26 views

Number of integer squares in finite arithmetic progression.

How many square values can $u+vb$ take where $u,v\in\Bbb N$ are fixed and $u\approx v^2$ and $b$ varies from $0$ to $v$?
1
vote
0answers
35 views

$(x_1+\cdots +x_n)^{k}=\sum\limits_{|\beta|=k}\binom{k}{\beta}x^{\beta}$

$(x_1+\cdots + x_n)^{k}=\sum\limits_{|\beta|=k}\binom{k}{\beta}x^{\beta}$ I have to prove this by induction on $k$, not on $n$. Do you have a proof without much text, I mean an algebraic proof ...
7
votes
2answers
230 views

Who conjectured that there are only finitely many biplanes, and why?

This question on MathOverflow motivates me to ask what the reasoning is behind the conjecture that there are only finitely many biplanes. More generally, it has been conjectured that for fixed ...
3
votes
1answer
30 views

Prove we can remove two objects from each set still keeping the two sets of equal weight

Let 100 objects of different weights from 1 to 100. We split the object set in two sets of equal weight. Prove we can remove two objects from each set still keeping the two sets of equal ...
1
vote
1answer
26 views

Calculating probability of obtaining exactly two $20$'s in $40$ rolls of a fair $20$-sided die

I have a question: On a fair 20-sided die, the number $20$ comes up once every $20$ rolls. In forty rolls, it's expected that about two rolls of $20$ will happen. What are the actual odds that, ...
1
vote
1answer
17 views

Clarifying an old question on Combinations.

So there is already a question here and I just want to clarify something in this. Link:Meaning of the question Now the accepted answer says that the answer is a power of 2.And there is an ...
6
votes
1answer
1k views

How many different chess-board situations can occur?

If you play a standard chess game on a normal $8 \cdot 8$ chess board with the usual rules: How many different "board representations" can exist? Upper bound: Well, you have 16+16 = 32 chess pieces ...
7
votes
4answers
240 views

Prove $\sum_{k=0}^{n}\frac{n!}{k!}(n-k)n^k=n^{n+1}$ for any $n\in\mathbb N$.

I want to prove the following: $$\sum_{k=0}^{n}\frac{n!}{k!}(n-k)n^k=n^{n+1}\quad\text{for any $n\in\mathbb N$.}$$ I tried induction and invoking the binomial theorem, to little avail. I’m looking ...
1
vote
1answer
19 views

Find the number of different magmas that have $A$ as its underlying set

I have a problem involving algebraic structures. Any help I can get here would be amazing. Problem: We have a set $A$, $\text{card} A = n$, $n \in \Bbb N$. Find the number of different magmas that ...
-1
votes
0answers
27 views

How can I know this problem talk about conditional probability , permutation, or combination ,Do you have any techniques for this . [on hold]

How can I know this problem talk about conditional probability , permutation, or combination ,Do you have any techniques for this . always my teacher gives us problem , and it does not have any ...
3
votes
2answers
87 views

$(C_2 )^3$ is not a subgroup of $S_4$

Prove $(C_2)^3$ is not a subgroup of $S_4$. (Using group actions.) I could think of a permutation argument that $(C_2)^3$ is not a subgroup of $S_4$. But I would like to argue it by considering ...
7
votes
1answer
188 views
+50

How many partial derivatives does a multivariate polynomial have?

My motivation for this question is from the following toy example; define the (nondeterministic) finite state machine generated by the polynomial $f(x_0 , \dots , x_n) \in \mathbb{Z} [x_0 , x_1 , ...
5
votes
3answers
263 views

How many 6 digit numbers are possible with no digit appearing more than thrice?

How many 6 digit numbers are possible with at most three digits repeated? My attempt: The possibilities are: A)(3,2,1) One set of three repeated digit, another set of two repeated digit and ...
0
votes
1answer
39 views

Possible number of codes..?

A combination lock consisting of 0-100 So 101 digits, and the Combination lock has 3 number turn dial safe lock codes. What are the number of possible codes.? Including repeat numbers. Examples: ...
0
votes
1answer
43 views

How many integer numbers from 0 to 100000 contain 2 or more digits 5?

How many integer numbers from 0 to 100000 contain 2 or more digits 5? I know that I need to apply some kind of formula to this problem, but I can't choose which one. Can you please help me?
0
votes
2answers
43 views

Denote $X = {1, 2,…, 100}$. $B$ is a $8$-element subset of $X$

Denote $X = \{1, 2,..., 100\}$. $B$ is a $8$-element subset of $X$. Prove that there are two subsets of $B$ such that sum of all elements are equal. Is there a simple way?
1
vote
3answers
28 views

proof about hall's theorem in graph theory

Prove that a k regular bipartite graph has a perfect matching by using hall's theorem. Approach Let S be any subset of the left side of the graph The only thing I know is the number of things ...
1
vote
1answer
159 views

Can we get general computational complexity of finding factors of two almost prime number N if it is not divisible by 2,3,5?

What is computational complexity of finding factors of two almost prime number N, which is not divisible by 2 and 3 and 5? Can we help our selfs with knowledge that we know digit sum of that number ...
0
votes
0answers
7 views

Introductory text on partitions, matroids, geometric lattices

Can anyone recommend a text which explains matroids, lattices of subsets, and how they are related? Possibly motivated with examples from different applications or areas of math.
1
vote
0answers
16 views

HM question- the graph K4,3

We've been asked to prove the following: Prove that you can place K4,3 on the plane with exactly two intersects. then, prove that you can't do it with less intersections. someone?
0
votes
1answer
38 views

Number of ways to arrange the alphabet, A is not in first position, B is not in second, and so on.

My first answer was 25! as The first letter has 25 possibilities, second letter 24 possibilities, and so on. However, I realised that it is actually more than that. There is a possibility that the ...
2
votes
1answer
88 views

Numbers which are writable as a sum of permutation pairs

We say that $N$ is writable as a sum of permutation pair $\{a,b\}$ if $a+b=N$, $a\neq b$ and $a$ and $b$ are permutations of each other (e.g. $321 = 156 + 165 = 147 + 174 = ... $). Looking at 3-digit ...
1
vote
3answers
567 views

Meaning of the question

There is a question that goes like this : The supreme court has given a 6 to 3 decisions upholding a lower court; the number of ways it can give a majority decision reversing the lower court is : ...
13
votes
2answers
453 views

Dividing books between two couples

Two couples of boys and girls, $(b_1,g_1)$ and $(b_2,g_2)$, are dividing a pile of books. Every book will go to one of the couples, and they'll read it together. Each person has a (nonnegative) value ...
0
votes
1answer
12 views

Number of functions preserving a partition

Let $X$ be a disjoint union of $A_i (1 \leq i \leq n)$ and let $Y$ be a disjoint union of $B_j (1 \leq j \leq m)$. How many functions $f$ from $X$ into $Y$ satisfies the condition: if $a,b$ are in ...
1
vote
3answers
30 views

Candies withdrawal probability for a particular subsequence

You are taking out candies one by one from a jar that has 10 red candies, 20 blue candies, and 30 green candies in it. What is the probability that there are at least 1 blue candy and 1 green candy ...
2
votes
5answers
148 views

proving that $\frac{(n^2)!}{(n!)^n}$ is an integer

How to prove that $$\frac{(n^2)!}{(n!)^n}$$ is always a positive integer when n is also a positive integer. NOTE i want to prove it without induction. I just cancelled $n!$ and split term which are ...
2
votes
0answers
23 views

$A_n=\{\{k_1,…,k_n\}|\sum\limits_{I=1}^{n}\frac{1}{k_i}=1, k_i\in Z^+\}$, finding a formula for $|A_n|$

I am sure this is like some super classic combinatorics problem, but as I have not been able to find it, I decided to post. Given the set : ...
4
votes
0answers
56 views

Expected length of longest arithmetic sequence

Given a natural number $n$, we define the vector valued random variable $\vec Y_n := (X_1, \ldots X_n)$ where all $X_i$ are independently uniformely distributed on $S_n := \{1, \ldots, n\}$. Further ...
2
votes
1answer
53 views

Counting the numnber of (labelled and unlabelled) rooted trees on $n$ vertices with height $h$

As far as I know, the number of labelled rooted trees on $n$ vertices is $n^{n-1}$. Is there a known result for counting the number of (labelled and unlabelled) rooted trees on $n$ vertices having ...