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)

1
vote
1answer
7 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
229 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
15 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
vote
2answers
23 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
24 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 ...
-1
votes
0answers
25 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
81 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 ...
6
votes
1answer
174 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 , ...
7
votes
2answers
222 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 ...
5
votes
3answers
256 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
38 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
40 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
26 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
6 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
12 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
34 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
87 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
563 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
28 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
22 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
54 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
51 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 ...
0
votes
1answer
39 views

Proof with combinatorics

Prove the following theorem: Theorem: if $k<n$ then $S_{k+1}^{n+1}=S_{k}^{n}+S_{k+1}^{n}$ ($S_{k}^{n}$= n choose k) Proof $Left=S_{k+1}^{n+1}$ what left does is to count all possible subsets ...
2
votes
3answers
17k views

How many one to one and onto functions are there between two finite sets?

Suppose $X$ has $N$ elements and $Y$ has $M$ elements. How many one to one function are there from $X$ to $Y$? How many onto function are there from $X$ to $Y$? The number of one to one functions ...
9
votes
1answer
188 views

$6$ points in the interior of a square of side length $2$.

Prove that having $6$ points in the interior of a square of side length $2$, we can choose $3$ of them so that the sum of distance between them is less than $3\sqrt{2}$. Is there a simple way?
3
votes
3answers
109 views

numbers from $1$ to $2046$

We have randomly taken $21$ integers from $1$ to $2046$. Show that we can take $a$, $b$ and $c$ from the previous $21$ integers in a way such that the following inequality holds \begin{equation} ...
5
votes
1answer
59 views

number of ways to partition an integer.

A partition of a positive integer n is a way of writingn as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 ...
1
vote
1answer
57 views

Sharing pears and bananas

Per has $3$ bananas and $5$ pears. Olav asks if he could have some fruit and Per agrees. What is the probability that he receives half ($1/2$) a pear and three quarters ($3/4$) of a banana? ...
0
votes
0answers
43 views

Stirling number of the second kind. [on hold]

I cannot utilize the hint anywhere.. Please help. Let $S(n,k)$ be the Stirling number of the second kind. Show algebraically and combinatorially that $$S(n,k)=\sum1^{a_1-1}2^{a_2-1}\cdots ...
0
votes
1answer
21 views

How to prove that ${l \choose a_1,…,a_n}\le n^{l-1} $ , when $a_1+…+a_n=l$.

In the proof of (Corollary 8 chap. 3 ) in the book "Sobolev Spaces on Domains" by Burenkov the following inequality is used : given $a_1,...,a_n \in \mathbb{N}$ such that $a_1+...+a_n=l$, then $${l ...
171
votes
17answers
30k views

Do men or women have more brothers?

Do men or women have more brothers? I think women have more as no man can be his own brother. But how one can prove it rigorously? I am going to suggest some reasonable background assumptions: ...
1
vote
2answers
50 views

Finding the smallest composition of a natural number with limited basic set of summands

W.l.o.g. I have a set of natural numbers $$S = \{s_1, \ldots, s_n\}, \quad s_i \in \mathbb N$$ as well as an $x \in \mathbb N$ I would like to express as sum of $s_i$. How do I find the smallest ...
1
vote
1answer
31 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 ...
1
vote
1answer
406 views

How many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads?

I am trying to figure out how many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads. I understand how to do the problem with two colors, but I am struggling to ...
1
vote
2answers
33 views

In how many ways can $5$ students and $3$ teacher sit around a table so that no two teachers are together?

In how many ways can $5$ students and $3$ teacher sit around a table so that no two teachers are together? My attempt: $5$ student can sit $(5-1)!$ in round table. A teacher can sit between ...
0
votes
3answers
33 views

How many numbers of $7$ digits can be formed with the digit $0,1,1,5,6,6,6$.

How many numbers of $7$ digits can be formed with the digit $0,1,1,5,6,6,6$. My attempt: Seventh place, total number of possibility is $=\frac{6!}{2!\times 3!}=60$ ways. Sixth place, total ...
0
votes
0answers
20 views

How long would it take to compose every tweet possible?

Assume that the number of distinct characters available to compose each tweet is $c$, the maximum length of a tweet is $l$, the number of people composing tweets simultaneously is $p$, and that the ...
2
votes
1answer
28 views

How many $3$ digit different number that will be divisible by $5$ can be formed from the digit $0,2,3,4,5,6$ lying between $100$ and $1000$.

How many $3$ digit different number that will be divisible by $5$ can be formed from the digit $0,2,3,4,5,6$ lying between $100$ and $1000$. My attempt: Divisible by $5$ is possible only when ...
6
votes
3answers
2k views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
1
vote
1answer
39 views

Graph with exactly one perfect matching

How do I prove that if $ G $ graph, with $2n$ vertices, has exactly one perfect matching then $ |E(G)| \le n^2 $ ?
-2
votes
1answer
121 views

Tossing counters - Problem Solving [on hold]

Several Students were told to write four different integers from 1 to 9 on the four faces of two counters, with one number on each face. He then asked them to toss both counters at the same time many ...
1
vote
0answers
22 views

Comparing the task complexity of installing three different offenses for American style football in three days

I want to identify the inherent difficulty of installing three separate American rules football offenses by their complexity of practice schedules in three days then relate those offenses back to one ...
1
vote
4answers
69 views

Recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, then find $a_{20}$

Consider the recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, given that $a_0=0, a_1=1$. Let $a_{20}=x\times10^9$, then the value of $x$ is______ . My attempt: $a_r=3-6a_{r-1}-9a_{r-2}$ I ...
1
vote
1answer
20 views

Logic of getting a full-house of cards.

Although I understand the correct solution of finding the total number of full houses in a 52-deck of cards (finding the number of ways of selecting the first value and then finding the amount of ways ...